Dominolar (Həll təhlili)

$f(n)$ ilə 2 \times n ölçülü düzbucaqlını 2 \times 1 domino daşları ilə örtmək üsullarının sayını təyin edək. Aydındır ki,

• f(1) = 1, bir vertikal domino;

• f(2) = 2, ya iki vertikal, ya da iki horizontal domino.

$f(n)$ hesablanması üçün aşağıdakı algoritmi nəzərdən keçirək:

• bir domino daşını vertikal yerləşdirə bilərik, sonra qalan uzunluğu n - 1 olan düzbucaqlını f(n - 1) üsulla örtürük,

• ya da iki domino daşını horizontal yerləşdirə bilərik, sonra qalan uzunluğu n - 2 olan düzbucaqlını f(n - 2) üsulla örtürük.

Beləliklə, aşağıdakı rekurent münasibəti əldə edirik:

Beləliklə, $f(n)$ Fibonacci ədədi olur.

Java realizasiyası

Çünki n < 65536, biz uzun arifmetikaya və ya Java proqramlaşdırma dilindən istifadə etməliyik.

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 realizasiyası

Limi gövdərinə (məsələn, $100000$ rəqəm) qədər artırırıq

import sys
sys.set_int_max_str_digits(100000)

Giriş ədədini $n$ oxuyuruq.

n = int(input())

Əsas halları emal edirik.

if n == 1:
  print(1)
elif n == 2:
  print(2)
else:

$n$-ci Fibonacci ədədini hesablayaq.

  f1, f2 = 1, 2
  for i in range(n - 2):
    temp = f1 + f2
    f1, f2 = f2, temp

Cavabı çıxışa veririk.

  print(f2)