Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Уважаемый посетитель сайта, к какой категории вы себя относите?
Всего ответов: 5512

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Пятница, 14.08.2020, 08:59
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Шахматный номер
13.02.2012, 09:07

Условие:
Телефонный номер называется "шахматным”, если его цифры набираются на телефонном кнопочном номеронабирателе ходом шахматного коня. Написать программу, подсчитывающую, сколько можно набрать различных семизначных "шахматных” номеров, начинающихся с заданной цифры.
_____
1 2 3
4 5 6
7 8 9
__0__

Технические условия:
Входной файл INPUT.TXT содержит число N [0..9]. Выходной файл OUTPUT.TXT должен содержать единственное число - решение задачи.

Примеры входных и выходных файлов:
Input.txt
1
Output.txt
136

Input.txt
4
Output.txt
168

Input.txt
5
Output.txt
0

Input.txt
8
Output.txt
104

Решение:
---------- cut ----------
Вначале для каждой цифры нужно задать все возможные пути перемещения (конём). Затем, используя рекурсивную процедуру, выполняем поиск всех семизначных номеров, удовлетворяющих условию...
---------- cut ----------

const
mas:array[0..9,1..3] of integer =
((4,6,-1), (6,8,-1), (7,9,-1),
(4,8,-1), (3,9,0), (-1,-1,-1),
(1,7,0), (2,6,-1), (1,3,-1), (2,4,-1));
input = 'input.txt';
output = 'output.txt';

var
N:integer;
Tel:integer;
f1,f2:text;

procedure Find(digit:integer; count: integer);
var i:integer;
begin
if digit=-1 then exit;
if count =7 then begin inc(Tel);exit;end;
for i:=1 to 3 do
Find(mas[digit,i],count+1);
end;

begin
assign(f1,input);
reset(f1);
read(f1,n);
close(f1);

find(N,1);

assign(f2,output);
rewrite(f2);
write(f2,Tel);
close(f2);
end.

Решение: by Алексей Ильичёв <alex_z77@mail.ru>:

---------- cut ----------
Преимущество этого алгоритма в том, что кол-во операций линейно зависит от длины номера, в отличии от приведённого переборного решения.
---------- cut ----------

{$A+,B-,D+,E+,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 16384,0,655360}

const
canmove : array [0..9, 1..3] of shortint =
((4, 6, -1),(6, 8, -1),(7, 9, -1),
(4, 8, -1),(0, 3, 9),(-1, -1, -1),
(0, 1, 7),(2, 6, -1),(1, 3, -1),(2, 4, -1));
{Так мы задаём откуда и куда может ходить конь}

var
n, i, j, k : byte;
res : array[1..7, -1..9] of integer;
{-1 -й элемент массива нужен, чтобы не проверять лишний раз,
не равен ли элемент массива canmove -1}
sum : integer;

begin
assign(input, 'input.txt');
reset(input);
read(n);
close(input);

{применяем метод динамического программирования: }
res[1, n] := 1; {в элементе [x, y] этого массива будем хранить кол-во
номеров длины x, заканчивающихся цифрой y и отвечающих условию}
for i := 1 to 6 do {зная i-ю колонку массива res, можем посчитать i+1-ю}
for j := 0 to 9 do
for k := 1 to 3 do
inc(res[i+1, canmove[j, k]], res[i, j]);

{осталось только просуммировать последнюю колонку и вывести результат}
for i := 0 to 9 do inc(sum, res[7, i]);
assign(output, 'output.txt');
rewrite(output);
writeln(sum);
close(output);
end.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 668 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2020
/td>