Задача 44: Домино
Задание. Написать программу DOMINO, подсчитывающую количество
вариантов покрытия прямоугольника 2хN прямоугольниками 2х1.
Покрытия, которые преобразуются одно в другое симметриями, считать
различными.
Входные данные. Входной файл DOMINO.DAT содержит число N (0 <
N < 65536).
Выходные данные. Выходной файл DOMINO.SOL должен содержать
одно число: количество вариантов.
Примеры ввода и вывода
DOMINO.DAT : 1
DOMINO.SOL : 1
Решение:
Очередная задача, раньше числившаяся в разряде нерешенных.
Попробуем нарисовать все возможные комбинации на листе бумаги и
записать количество возможных вариантов:
0 :: 1
1 :: 1
2 :: 2
3 :: 3
4 :: 5
5 :: 8
6 :: 13
Уфф... уморился. Ну ладно, этого нам вполне достаточно, чтобы
предположить, что количество вариантов расположения n костяшек
домино равно n-му члену последовательности чисел Фибоначчи. Для тех,
кто не знает расскажу, а для тех, кто знает напомню, что каждое
число Фибоначчи (за исключением первых двух членов) представляется
как сумма двух предыдущих.
В этой задаче такое предположение легко доказывается:
Если мы имеем последовательность из n костяшек, то мы можем получить
последовательность из n+1 костяшек прибавлением одной вертикальной
костяшки. Также последовательность из n+1 костяшки можно получить
прибавлением двух горизонтальных костяшек к последовательности из
n-1 костяшки. Других вариантов нет (нарисуйте, и разберитесь почему)
- они будут повторяться с одной из приведенных выше комбинаций.
Теперь перед нами стоит задача посчитать числа Фибоначчи до 65536
члена. Сразу замечу, что я написал программу, которая считает 65536
член Фибоначчи примерно за 30 секунд на 400-ом Селероне. Если
кто-нибудь напишет быстрее, присылайте - буду очень благодарен!
Для подсчета больших чисел Фибоначчи нам понадобится длинная
арифметика, причем очень длинная - около 15000 десятичных знаков.
Заведем три массива длиной 20000(на всякий случай), состоящих из
элементов byte. Один из массивов будет равен F(n-2), другой F(n-1),
третий F(n). Первоначально инициализируем последние элементы
массивов F(n-2) и F(n-1) соответственно 1 и 2. Для ускорения
сложения заведем переменную, указывающую на первую цифру наибольшего
числа. Первоначально эта переменная содержит 20000 (цифра одна).
Теперь перейдем к написанию процедуры сложения двух длинных чисел.
Для этого нам надо идти с конца массива до указателя на первую
цифру(в дальнейшем k), изменяя значение переменной c от 20000 до k.
F(n)[c] := F(n-2)[c] + F(n-1)[c] + flag;
flag := F(n)[c] div 10;
F(n)[c] := F(n)[c] mod 10;
Сложение напоминает сложение столбиком, где переменная flag - это
число "в уме"(первоначально равно нулю). После сложения стоит
производить такие действия:
for c := k to 20000 do begin
F(n-2)[c] := F(n-1)[c];
F(n-1)[c] := F(n)[c];
end;
Мы записываем в F(n-2) число F(n-1), а в число F(n-1) - число F(n),
т.е. увеличиваем n на 1.
В конце нам следует вывести все элементы массива F(n) от k да 20000
- это и будет искомым числом!
Далее
ð
