Условие:
Телефонный номер называется "шахматным”, если его цифры набираются на телефонном кнопочном номеронабирателе ходом шахматного коня. Написать программу, подсчитывающую, сколько можно набрать различных семизначных "шахматных” номеров, начинающихся с заданной цифры.
_____
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. |
