poj2680 Computer Transformation----简单的递推
#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); }elsep[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]); } }}
