4469. Domino

Find the number of ways to cover a rectangle 2 × n with domino of size 2 × 1. The coverings that turn themselves into symmetries are considered different.

Input. One integer n (0 < n < 65536).

Output. Print the number of coverings of rectangle.

Sample input 1	Sample output 1
1	1
Sample input 2	Sample output 2
4	5

SOLUTION

Fibonacci numbers

Algorithm analysis

Let f(n) be the number of ways to cover the 2 × n rectangle with 2 × 1 dominoes. Obviously, that

· f(1) = 1, one vertical domino;

· f(2) = 2, two vertical or two horizontal dominoes.

Consider an algorithm for computing f(n). You can put one domino vertically and then cover a rectangle of length n – 1 in f(n – 1) ways, or put two dominoes horizontally and then cover a rectangle of length n – 2 in f(n – 2) ways. That is, f(n) = f(n – 1) + f(n – 2).

So f(n) is the Fibonacci number.

Algorithm realization

Since n < 65536, long arithmetic or Java programming language should be used.

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

}

}