Computer Transformation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3845 Accepted Submission(s): 1420
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
2 3
Sample Output
1 1
Source
Recommend
JGShining
先找到规律，推公式。
1->01 , 0->10
而且很容易知道连续的0肯定是两个连续的0.
设f[n]为n步操作后连续0的个数
则连续的0怎么样来呢？只能由上一层的01变成，也就是上一层的01一定可以产生连续00
上一层的01可以由再上一层的1得到。或者由上一层的00也可以产生一个01.
所以递推公式产生了：
f[n]=f[n-2]+2^(n-3).
由这个递推公式很容易产生通项公式：
当n为偶数时，f[n]=(2^(n-1)+1)/3;
当n为奇数时，f[n]=(2^(n-1)-1)/3;
所有用大数公式就得出来了。。
用JAVA写大数写出来的。。
/* f[n]=f[n-2]+2^(n-3); n为奇数时，f[n]=(2^(n-1)-1)/3; n为偶数时，f[n]=(2^(n-1)+1)/3; */import java.util.*;import java.math.*;import java.io.*;public class Main { public static void main(String[] args) { Scanner cin=new Scanner(new BufferedInputStream(System.in)); BigInteger a[]=new BigInteger[1000]; a[0]=BigInteger.valueOf(1); for(int i=1;i<1000;i++) a[i]=a[i-1].multiply(BigInteger.valueOf(2)); int n; BigInteger ans; while(cin.hasNextInt()) { n=cin.nextInt(); if(n%2==0)//偶数 { ans=a[n-1].add(BigInteger.valueOf(1)); ans=ans.divide(BigInteger.valueOf(3)); } else { ans=a[n-1].subtract(BigInteger.valueOf(1)); ans=ans.divide(BigInteger.valueOf(3)); } System.out.println(ans); } }}
import java.util.*;import java.math.*;import java.io.*;public class Main { public static void main(String[] args) { int n; Scanner cin=new Scanner(new BufferedInputStream(System.in)); BigInteger a=BigInteger.valueOf(2); BigInteger ans; while(cin.hasNextInt()) { n=cin.nextInt(); if(n%2==1) ans=a.pow(n-1).subtract(BigInteger.valueOf(1)).divide(BigInteger.valueOf(3)); else ans=a.pow(n-1).add(BigInteger.valueOf(1)).divide(BigInteger.valueOf(3)); System.out.println(ans); } }}
辛辛苦苦C++写了用份string的高精度。。竟然超时了。。。。
效率不高