C - Computer Transformation
HDU - 1041
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
題意：0變成10，1變成01悬垃，初始字符為01奕谭，經(jīng)過n次變化，有幾個(gè)連續(xù)的0
解法：dp贵涵，遞推列肢。最多只可能有兩個(gè)0相連恰画，看字符串先找規(guī)律：
0 1
1 0 0 1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
上面是前四次變化，可以發(fā)現(xiàn)n次變化的后一半為n-1次變化的序列瓷马，前一半在分兩段拴还，前一段是n-2次變化的序列，后一段再分兩段欧聘，前一段為n-3片林，依次類推，我們還發(fā)現(xiàn)怀骤，如果i為偶數(shù)费封，第一個(gè)拼接處還會(huì)出現(xiàn)一個(gè)多0序列，而在其他的拼接出不會(huì)發(fā)生晒喷，因?yàn)槿魏未巫兓蠖紩?huì)以1結(jié)尾孝偎。
所以得到遞推公式：
f(n) = f(n-1)+f(n-2)+······+f(2)+f(1)+(n+1)%2
f(n-1) = f(n-2)+······+f(2)+f(1)+n%2
化簡(jiǎn)得：
f(n) = 2f(n-1)+(n+1)%2-n%2
另外輸出結(jié)果很大遠(yuǎn)超longlong，所以要用到高精度計(jì)算
代碼：
#include<iostream>
using namespace std;
int a[1005][100]={0};
int main()
{
for(int i=2;i<=1000;i++){
int carry=0;
for(int j=0;j<100;j++){
a[i][j]=a[i-1][j]*2+carry;
if(j==0)
a[i][j]+=(i+1)%2-i%2;
carry=a[i][j]/100000;
a[i][j]%=100000;
}
}
int n;
while(cin>>n){
int flag=0;
if(n==1){
cout<<0<<endl;
continue;
}
for(int i=99;i>=0;i--){
if(flag>0){
printf("%05d",a[n][i]);
}
else
if(a[n][i]>0){
cout<<a[n][i];
flag=1;
}
}
cout<<endl;
}
return 0;
}
