4469. Домино

Найдите количество способов полностью покрыть прямоугольник размером 2 × n доминошками 2 × 1. Покрытия, которые совпадают с собой при симметриях (повороты или отражения), считаются разными.

Вход. Одно целое число n (0 < n < 65536).

Выход. Выведите количество способов покрытия прямоугольника доминошками.

Пример входа 1	Пример выхода 1
1	1
Пример входа 2	Пример выхода 2
4	5

РЕШЕНИЕ

числа Фибоначчи

Анализ алгоритма

Обозначим через f(n) количество способов покрыть прямоугольник 2 × n доминошками 2 × 1. Очевидно, что

· f(1) = 1, одна вертикальная доминошка;

· f(2) = 2, либо две вертикальные, либо две горизонтальные доминошки.

Рассмотрим алгоритм вычисления f(n):

· можно положить одну доминошку вертикально, после чего оставшийся прямоугольник длины n – 1 покрывается f(n – 1) способом,

· либо положить две доминошки горизонтально, после чего оставшийся прямоугольник длины n – 2 покрывается f(n – 2) способами.

Таким образом, получаем рекуррентное соотношение:

f(n) = f(n – 1) + f(n – 2)

Таким образом, f(n) является числом Фибоначчи.

Java реализация

Поскольку n < 65536, то следует воспользоваться длинной арифметикой или языком программирования Java.

import java.util.*;

import java.math.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

BigInteger a = new BigInteger("1"), b = a;

for(int i = 0; i < n; i++)

{

BigInteger temp = a.add(b);

a = b;

b = temp;

}

System.out.println(a);

con.close();

}

}

Python реализация

Увеличиваем лимит до нужного числа (например, 100000 цифр)

import sys

sys.set_int_max_str_digits(100000)

Читаем входное число n.

n = int(input())

Обрабатываем базовые случаи.

if n == 1:

print(1)

elif n == 2:

print(2)

else:

Вычисляем n-ое число Фибоначчи.

f1, f2 = 1, 2

for i in range(n - 2):

temp = f1 + f2

f1, f2 = f2, temp

Выводим ответ.

print(f2)