题目：
分析：大整数的乘法与加法 推荐算法分析 ”程序员小灰“微信平台 文章。（关注他微信公众号后，点击右上角「…」，再点击「全部消息」，搜索「大整数」，完成）
说明：定定定 c++编写了一个大整数类来解决这些题。当然，大整数类 并不完善，日后继续学习时，找机会完善。
大整数代码
#include <iostream> #include "cstring" #include <string> #include <stdlib.h> #define N 1000 using namespace std; class bigInteger { private: int *arrayInt;//倒序数组 unsigned int len; public: bigInteger(const string bigNum) { len=bigNum.length(); arrayInt=new int[len]; for(unsigned int i=0; i<bigNum.length(); i++) { arrayInt[i]=bigNum[bigNum.length()-1-i]-'0'; //倒序赋值 } } bigInteger(int bigNUM_len)//单独给result的构造函数 { len=bigNUM_len; arrayInt=new int[len+1](); } bigInteger() { arrayInt=NULL; len=0; } ~bigInteger() { if(arrayInt!=NULL) { delete []arrayInt; arrayInt=NULL; len=0; } } /* 测试代码 void show() { for(unsigned int i=0;i<len;i++) { cout<<arrayInt[i]; } cout<<endl; cout<<len; }*/ bigInteger(const bigInteger &A) { this->len=A.len; if(len!=0) { this->arrayInt=new int[len]; for(unsigned int i=0; i<len; i++) { (this->arrayInt)[i]=(A.arrayInt)[i]; } } } bigInteger& operator=(const bigInteger & A) { this->len=A.len; if(len!=0) { this->arrayInt=new int[len]; for(unsigned int i=0; i<len; i++) { (this->arrayInt)[i]=(A.arrayInt)[i]; } } return *this; } void operator += (const bigInteger &A) { if(A.arrayInt!=NULL && this->arrayInt!=NULL) { unsigned int maxlength=max(this->len,A.len); unsigned int minlength=min(this->len,A.len); bigInteger result(maxlength); result.arrayInt[0]=0; //做加法 for(unsigned int i=0; i<maxlength; i++) { int temp; if(i<minlength) temp=this->arrayInt[i]+A.arrayInt[i]+result.arrayInt[i]; else { if(A.len==minlength) temp=this->arrayInt[i]+result.arrayInt[i]; else if(this->len==minlength) temp=A.arrayInt[i]+result.arrayInt[i]; } result.arrayInt[i]=temp%10; result.arrayInt[i+1]=temp/10; } //程序健壮性 if(result.arrayInt[maxlength]!=0) { result.len++; } else {}//else时，不改变result.len *this=result; } else if(A.arrayInt!=NULL && this->arrayInt==NULL) { *this=A; } } friend istream & operator >>(istream & in,bigInteger &A); friend ostream & operator <<(ostream & out,const bigInteger &A); friend bigInteger operator+(const bigInteger A,const bigInteger B); friend bigInteger operator*(const bigInteger A,const bigInteger B); //适配题目的函数 int *getarrayInt() { return arrayInt; } int getLen() { return len; } }; istream & operator >>(istream & in,bigInteger &A) { string s; in>>s; A=bigInteger(s);//为什么这样不行？？？过了，应该是当时，没重载<< /* if(A.arrayInt!=NULL) { delete []A.arrayInt; } A.len=s.length(); A.arrayInt=new int[A.len]; for(unsigned int i=0; i<s.length(); i++) { (A.arrayInt[i])=s[s.length()-1-i]-'0'; //倒序赋值 }*/ return in; } ostream & operator <<( ostream & out,const bigInteger &A)// cout<<(A+B); { for(unsigned int i=0; i<A.len; i++) out<<A.arrayInt[A.len-1-i]; return out; } bigInteger operator+(const bigInteger A,const bigInteger B) { if(A.arrayInt!=NULL && B.arrayInt!=NULL) { unsigned int maxlength=max(B.len,A.len); unsigned int minlength=min(B.len,A.len); bigInteger result(maxlength); result.arrayInt[0]=0; for(unsigned int i=0; i<maxlength; i++) { int temp; if(i<minlength) temp=B.arrayInt[i]+A.arrayInt[i]+result.arrayInt[i]; else { if(B.len==minlength) temp=A.arrayInt[i]+result.arrayInt[i]; else if(A.len==minlength) temp=B.arrayInt[i]+result.arrayInt[i]; } result.arrayInt[i]=temp%10; result.arrayInt[i+1]=temp/10; } if(result.arrayInt[maxlength]!=0) { result.len++; } else {}//else时，不改变result.len return result; } else { if(A.arrayInt!=NULL) return A; else if(B.arrayInt!=NULL) return B; else if(A.arrayInt==NULL &&B.arrayInt==NULL) return A; } } bigInteger operator*(const bigInteger A,const bigInteger B) { if(A.arrayInt!=NULL && B.arrayInt!=NULL) { bigInteger result(A.len+B.len) ; result.arrayInt[0]=0; for(unsigned int i=0; i<B.len; i++) { for(unsigned int j=0; j<A.len; j++) { result.arrayInt[i+j]+=A.arrayInt[j]*B.arrayInt[i]; if(result.arrayInt[i+j]>=10) { result.arrayInt[i+j+1]+=result.arrayInt[i+j]/10; result.arrayInt[i+j]=result.arrayInt[i+j]%10; } } } //确定result.len int counter=0; for(unsigned int i=result.len-1; i>=(max(A.len,B.len)-1); i--) { if(result.arrayInt[i]==0) { counter++; } else break; } result.len-=counter; return result; } else { if(A.arrayInt!=NULL) return A; else if(B.arrayInt!=NULL) return B; else if(A.arrayInt==NULL &&B.arrayInt==NULL) return A; } }UVA 485 Pascal’s Triangle of Death（主函数部分） 杨辉三角 （注意 把数组a写到全局变量，否则可能会Runtimely Error)
bigInteger a[1500],init("1"); int main() { int k=1; bool flag=true; a[0]=init; while(flag) { bigInteger p,q("0"); if(k!=1) a[k-1]=q; for(int i=0;i<k;++i) { p=a[i]; a[i]=p+q; if(a[i].getLen()>=61) {flag=false;}//当位数为61时，那一行也要输出 q=p; } for(int i=0;i<k;++i) { if(i!=0) cout<<' '; cout<<a[i]; } cout<<endl; k++; } return 0; }UVA 424 Integer Inquiry 整数加法
int main() { bigInteger a,b; while(1) { cin>>b; if(b.getarrayInt()[0]==0&&b.getLen()==1) break; else { a+=b; } } cout<<a<<endl; return 0; }UVA 495 Fibonacci Freeze 斐波那契数列 （注意第一项从0开始）
bigInteger a[5003]={bigInteger("0"),bigInteger("1"),bigInteger("1")}; int main() { for(int j=3;j<=5000;++j) { a[j]=a[j-1]+a[j-2]; } int i; while(scanf("%d",&i) != EOF) { cout<<"The Fibonacci number for "<<i<<" is "<<a[i]<<endl; } return 0; }UVA 324 Factorial Frequencies 阶乘
bigInteger a[366]= {bigInteger("1")}; int main() { for(int i=1; i<366; i++) { stringstream ss; string s; ss<<i+1; ss>>s; bigInteger num(s); a[i]=a[i-1]*s; } int k; while(cin>>k&&k!=0) { int record_count[10]= {0}; for(int i=0; i<a[k-1].getLen(); ++i) { int number; number=(a[k-1].getarrayInt())[i]; switch(number) { case 0: record_count[0]++; break; case 1: record_count[1]++; break; case 2: record_count[2]++; break; case 3: record_count[3]++; break; case 4: record_count[4]++; break; case 5: record_count[5]++; break; case 6: record_count[6]++; break; case 7: record_count[7]++; break; case 8: record_count[8]++; break; case 9: record_count[9]++; break; } } //输出 printf("%d! --\n",k); printf("(0) %d (1) %d (2) %d (3) %d (4) %d\n",record_count[0],record_count[1],record_count[2], record_count[3],record_count[4]); printf("(5) %d (6) %d (7) %d (8) %d (9) %d\n",record_count[5],record_count[6],record_count[7], record_count[8],record_count[9]); } return 0; }查题网站：https://vjudge.net/
分析大整数乘法：
