杭电1293大数

这是一题比较综合性的大数，里面涉及到了大数的各种使用方法。我们一定要熟练这些使用方法。在没有模板的情况下15分钟要将之写出来并且运行好。这样你的基本功才是可以的。我通过简单的归纳可以发现这样的关系f[n]=3*f[n-2]+(f[-1]-f[n-2])*2,这一看就知道是大数的形式，上面涉及了乘法，加法，减法，当然出发的使用频率相对来说是比较低的。但是我们平时的时候还是要联系一下，这样的话到了用的时候才不会没有头绪。当然大数的使用已经比较多了，在这里不再叙述怎么写的，只是将需要注意的几点说下：

一个是减法：注意我们做的是f[-1]-f[n-2]，所以我们传的参数之后前面的永远是比后面大的，就不需要在进行比较。还有就是借位的问题这个是不能考虑掉的。

二是乘法：我们不可以直接用a[i]*3因为这时候有可能会超出字符串的范围，所以是不可取的我们需要将之转换成实数相乘，然后再进行a[i]的取值操作。

下面是一个可以AC的代码仅供参考：

#include<iostream> using namespace std; #include<string> const int Max=1005; string a[Max]; string jianfa(string a,string b) { int i,j,i1,j1; i1=a.length(); j1=b.length(); for(i=i1-1,j=j1-1;j>=0;i--,j--) { if(a[i]<b[j]) { a[i]+=10; a[i-1]--; } a[i]=a[i]-b[j]+'0'; } return a; } string chengfa(string a,int n) { ? ? int i,k; int num=0; int sum=0; k=a.length(); for(i=k-1;i>=0;i--) { sum=(a[i]-'0')*n+num; a[i]=sum%10+'0'; num=sum/10; } if(num!=0) { a='1'+a; a[0]+=(num-1); } return a; } string plus(string a,string b) { ? ? int i1,j1,i,j; string c; if(a.length()<b.length()) { c=a; a=b; b=c; } i1=a.length(); j1=b.length(); for(i=i1-1,j=j1-1;j>=0;j--,i--) a[i]+=b[j]-'0'; for(i=i1-1;i>0;i--) if(a[i]>'9') { a[i]-=10; a[i-1]++; } if(a[0]>'9') { a[0]-=10; a='1'+a; } return a; } int main() { ? ?int N; ? ?int i; ? ?a[1]="3"; ? ?a[2]="7"; for(i=3;i<Max;i++) a[i]=plus(chengfa(a[i-2],3),chengfa(jianfa(a[i-1],a[i-2]),2)); ? ?while(cin>>N) ? ?cout<<a[N]<<endl; ? ?return 0; }