题意：初始串为一个1，每一步会将每个0改成10，每个1改成01，因此1会依次变成01,1001,01101001,……输入n(n<=1000)，统计n步之后得到的串中，"00"这样的连续两个0出现了多少次。
分析：找规律，输出n等于20之前所有的结果
得到结论，i为奇数时，a[i] = a[i - 1] * 2 - 1; i为偶数时，a[i] = a[i - 1] * 2 + 1。
import java.util.*;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
BigInteger[] a = new BigInteger[1010];
a[1] = new BigInteger("0");
BigInteger one = new BigInteger("1");
BigInteger two = new BigInteger("2");
for(int i = 2; i <= 1000; ++i){
if(i % 2 == 1){
a[i] = a[i - 1].multiply(two).subtract(one);
}
else{
a[i] = a[i - 1].multiply(two).add(one);
}
}
while(sc.hasNextInt()){
int n = sc.nextInt();
System.out.println(a[n]);
}
}
}
UVA - 1647 Computer Transformation(计算机变换)(找规律)
原文：http://www.cnblogs.com/tyty-Somnuspoppy/p/6382257.html