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

Позначимо через $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)$ є числом Фібоначчі.

Реалізація алгоритму

Оскільки $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();
    }
}