Problem Description

A
sequence consisting of one digit, the number 1 is initially written
into a computer. At each successive time step, the computer
simultaneously tranforms each digit 0 into the sequence 1 0 and each
digit 1 into the sequence 0 1. So, after the first time step, the
sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after
the third, the sequence 0 1 1 0 1 0 0 1 and so on.

How many pairs of consequitive zeroes will appear in the sequence after n steps?

 

Input

Every input line contains one natural number n (0 < n ≤1000).

 

Output

For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

 

Sample Input

 

Sample Output

 

Source

Southeastern Europe 2005

 

题意：给定初始值1，然后进行变换，变换的规则是 1->01 ,0->10,问进行n次变换后串中00的个数。

 

题解：

写出前几项：

              1

             01         第1次(项)

           1       第2次（项）

       101001    第3次 （项）

01101001    第4次（项）

....

我们会发现只有当串中存在1001时会出现00

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        BigInteger [] h = new BigInteger[1001];

        h[1] = new BigInteger("0");

        h[2] = new BigInteger("1");

        for(int i=3;i<=1000;i++){

            h[i] = h[i-2].add(pow(i-3));

        }

        Scanner sc =new Scanner (System.in);

        while(sc.hasNext()){

            int n =sc.nextInt();

            System.out.println(h[n]);

        }

    }

    private static BigInteger pow(int v) {

        BigInteger sum = BigInteger.valueOf(1);

        for(int i=0;i<v;i++){

            sum = sum.multiply(BigInteger.valueOf(2));

        }

        //System.out.println(sum);

        return sum;

    }

}