Alqoritm Analizi

2 × $n$ ölçülü düzbucaqlının 2 × 1 ölçülü domino parçaları ilə neçə fərqli şəkildə örtülə biləcəyini $f(n)$ ilə işarə edək. Açıqdır ki,

• $f(1)=1$, bir dikey parça;

• $f(2)=2$, iki dikey və ya iki üfüqi parça.

$f(n)$-i hesablamaq üçün alqoritmi nəzərdən keçirək. Bir parçanı dikey yerləşdirərək sonra $n–1$ uzunluğunda düzbucaqlını $f(n–1)$ yollarla örtə bilərik, və ya iki parçanı üfüqi yerləşdirərək sonra $n–2$ uzunluğunda düzbucaqlını $f(n–2)$ yollarla örtə bilərik. Beləliklə, $f(n)=f(n–1)+f(n–2)$.

Beləliklə, $f(n)$ bir Fibonacci rəqəmidir.

Alqoritm Tətbiqi

$n<65536$ olduğundan, uzun arifmetika və ya Java proqramlaşdırma dili istifadə etmək lazımdır.

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();
    }
}