poj2680 Computer Transformation-简略的递推_电脑整机及配件

poj2680 Computer Transformation----简单的递推

Computer Transformation

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4120		Accepted: 1592

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 consequitive 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步后，有多少对连续的0，即多少对00.

打表很容易发现规律。

要用高精。

打表的代码：

#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>using namespace std;int s1[1000];int s2[1000];int main(){    int i=0;    memset(s1,-1,sizeof(s1));    memset(s2,-1,sizeof(s2));    s1[0]=1;    while(i<10)    {        i++;        int cc=0;        for(int j=0;;j++)        {            if(s1[j]!=-1)            {                if(s1[j]==0) {s2[cc++]=1;s2[cc++]=0;}                else {s2[cc++]=0;s2[cc++]=1;}            }            else break;        }        /*for(int j=0;j<cc;j++)        cout<<s2[j];        cout<<"*"<<endl;*/        int count=0;        for(int j=0;j<cc-1;j++)        {            if(s2[j]==0&&s2[j+1]==0)            count++;        }        cout<<i<<" "<<count<<endl;        for(int j=0;j<cc;j++)        s1[j]=s2[j];    }}

最后实现的代码：

import java.util.*;import java.math.*;public class Main{public static BigInteger[] p=new BigInteger[1010];public static BigInteger[] s=new BigInteger[1010];public static void init(){	BigInteger a=BigInteger.valueOf(0);	BigInteger b=BigInteger.valueOf(1);	p[1]=a;p[2]=b;s[2]=b;	for(int i=3;i<=1000;i++)	{		if(i%2==0)	    {			p[i]=s[i-1];			p[i]=p[i].add(b);	    }		else		p[i]=s[i-1];		s[i]=s[i-1];		//BigInteger ss=p[i];		s[i]=s[i].add(p[i]);	}} public static void main(String[] args) {	 init(); Scanner cin  = new Scanner(System.in);  while(cin.hasNext())  {	  int n=cin.nextInt();	  System.out.println(p[n]);  }  }}