{大数模板}

路过http://blog.csdn.net/qq_18661257/article/details/51416202?locationNum=7&fps=1

  1 #include<stdio.h>
  2 #include<string>
  3 #include<string.h>
  4 #include<iostream>
  5 using namespace std;
  6 
  7 //compare比较函数：相等返回0，大于返回1，小于返回-1
  8 int compare(string str1,string str2)
  9 {
 10     if(str1.length()>str2.length()) return 1;
 11     else if(str1.length()<str2.length())  return -1;
 12     else return str1.compare(str2);
 13 }
 14 //高精度加法
 15 //只能是两个正数相加
 16 string add(string str1,string str2)//高精度加法
 17 {
 18     string str;
 19 
 20     int len1=str1.length();
 21     int len2=str2.length();
 22     //前面补0，弄成长度相同
 23     if(len1<len2)
 24     {
 25         for(int i=1;i<=len2-len1;i++)
 26            str1="0"+str1;
 27     }
 28     else
 29     {
 30         for(int i=1;i<=len1-len2;i++)
 31            str2="0"+str2;
 32     }
 33     len1=str1.length();
 34     int cf=0;
 35     int temp;
 36     for(int i=len1-1;i>=0;i--)
 37     {
 38         temp=str1[i]-'0'+str2[i]-'0'+cf;
 39         cf=temp/10;
 40         temp%=10;
 41         str=char(temp+'0')+str;
 42     }
 43     if(cf!=0)  str=char(cf+'0')+str;
 44     return str;
 45 }
 46 //高精度减法
 47 //只能是两个正数相减，而且要大减小
 48 string sub(string str1,string str2)//高精度减法
 49 {
 50     string str;
 51     int tmp=str1.length()-str2.length();
 52     int cf=0;
 53     for(int i=str2.length()-1;i>=0;i--)
 54     {
 55         if(str1[tmp+i]<str2[i]+cf)
 56         {
 57             str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
 58             cf=1;
 59         }
 60         else
 61         {
 62             str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
 63             cf=0;
 64         }
 65     }
 66     for(int i=tmp-1;i>=0;i--)
 67     {
 68         if(str1[i]-cf>='0')
 69         {
 70             str=char(str1[i]-cf)+str;
 71             cf=0;
 72         }
 73         else
 74         {
 75             str=char(str1[i]-cf+10)+str;
 76             cf=1;
 77         }
 78     }
 79     str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
 80     return str;
 81 }
 82 //高精度乘法
 83 //只能是两个正数相乘
 84 string mul(string str1,string str2)
 85 {
 86     string str;
 87     int len1=str1.length();
 88     int len2=str2.length();
 89     string tempstr;
 90     for(int i=len2-1;i>=0;i--)
 91     {
 92         tempstr="";
 93         int temp=str2[i]-'0';
 94         int t=0;
 95         int cf=0;
 96         if(temp!=0)
 97         {
 98             for(int j=1;j<=len2-1-i;j++)
 99               tempstr+="0";
100             for(int j=len1-1;j>=0;j--)
101             {
102                 t=(temp*(str1[j]-'0')+cf)%10;
103                 cf=(temp*(str1[j]-'0')+cf)/10;
104                 tempstr=char(t+'0')+tempstr;
105             }
106             if(cf!=0) tempstr=char(cf+'0')+tempstr;
107         }
108         str=add(str,tempstr);
109     }
110     str.erase(0,str.find_first_not_of('0'));
111     return str;
112 }
113 
114 //高精度除法
115 //两个正数相除，商为quotient,余数为residue
116 //需要高精度减法和乘法
117 void div(string str1,string str2,string "ient,string &residue)
118 {
119     quotient=residue="";//清空
120     if(str2=="0")//判断除数是否为0
121     {
122         quotient=residue="ERROR";
123         return;
124     }
125     if(str1=="0")//判断被除数是否为0
126     {
127         quotient=residue="0";
128         return;
129     }
130     int res=compare(str1,str2);
131     if(res<0)
132     {
133         quotient="0";
134         residue=str1;
135         return;
136     }
137     else if(res==0)
138     {
139         quotient="1";
140         residue="0";
141         return;
142     }
143     else
144     {
145         int len1=str1.length();
146         int len2=str2.length();
147         string tempstr;
148         tempstr.append(str1,0,len2-1);
149         for(int i=len2-1;i<len1;i++)
150         {
151             tempstr=tempstr+str1[i];
152             tempstr.erase(0,tempstr.find_first_not_of('0'));
153             if(tempstr.empty())
154               tempstr="0";
155             for(char ch='9';ch>='0';ch--)//试商
156             {
157                 string str,tmp;
158                 str=str+ch;
159                 tmp=mul(str2,str);
160                 if(compare(tmp,tempstr)<=0)//试商成功
161                 {
162                     quotient=quotient+ch;
163                     tempstr=sub(tempstr,tmp);
164                     break;
165                 }
166             }
167         }
168         residue=tempstr;
169     }
170     quotient.erase(0,quotient.find_first_not_of('0'));
171     if(quotient.empty()) quotient="0";
172 }
173 
174 
175 const int MAXNX = 200 + 5;
176 string C[MAXNX];
177 void init(){
178     C[0] = "0";
179     C[1] = "1";
180     for(int i = 2;i < MAXNX;i ++) C[i] = add(C[i - 1], C[i - 2]);
181 }
182 
183 int N;
184 int main() {
185     init();
186     while(~scanf("%d", &N)){
187         cout << C[N + 1] << endl;
188     }
189     return 0;
190 }

Fib

  1 #include<stdio.h>
  2 #include<string>
  3 #include<string.h>
  4 #include<iostream>
  5 using namespace std;
  6 
  7 //compare比较函数：相等返回0，大于返回1，小于返回-1
  8 int compare(string str1,string str2)
  9 {
 10     if(str1.length()>str2.length()) return 1;
 11     else if(str1.length()<str2.length())  return -1;
 12     else return str1.compare(str2);
 13 }
 14 //高精度加法
 15 //只能是两个正数相加
 16 string add(string str1,string str2)//高精度加法
 17 {
 18     string str;
 19 
 20     int len1=str1.length();
 21     int len2=str2.length();
 22     //前面补0，弄成长度相同
 23     if(len1<len2)
 24     {
 25         for(int i=1;i<=len2-len1;i++)
 26            str1="0"+str1;
 27     }
 28     else
 29     {
 30         for(int i=1;i<=len1-len2;i++)
 31            str2="0"+str2;
 32     }
 33     len1=str1.length();
 34     int cf=0;
 35     int temp;
 36     for(int i=len1-1;i>=0;i--)
 37     {
 38         temp=str1[i]-'0'+str2[i]-'0'+cf;
 39         cf=temp/10;
 40         temp%=10;
 41         str=char(temp+'0')+str;
 42     }
 43     if(cf!=0)  str=char(cf+'0')+str;
 44     return str;
 45 }
 46 //高精度减法
 47 //只能是两个正数相减，而且要大减小
 48 string sub(string str1,string str2)//高精度减法
 49 {
 50     string str;
 51     int tmp=str1.length()-str2.length();
 52     int cf=0;
 53     for(int i=str2.length()-1;i>=0;i--)
 54     {
 55         if(str1[tmp+i]<str2[i]+cf)
 56         {
 57             str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
 58             cf=1;
 59         }
 60         else
 61         {
 62             str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
 63             cf=0;
 64         }
 65     }
 66     for(int i=tmp-1;i>=0;i--)
 67     {
 68         if(str1[i]-cf>='0')
 69         {
 70             str=char(str1[i]-cf)+str;
 71             cf=0;
 72         }
 73         else
 74         {
 75             str=char(str1[i]-cf+10)+str;
 76             cf=1;
 77         }
 78     }
 79     str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
 80     return str;
 81 }
 82 //高精度乘法
 83 //只能是两个正数相乘
 84 string mul(string str1,string str2)
 85 {
 86     string str;
 87     int len1=str1.length();
 88     int len2=str2.length();
 89     string tempstr;
 90     for(int i=len2-1;i>=0;i--)
 91     {
 92         tempstr="";
 93         int temp=str2[i]-'0';
 94         int t=0;
 95         int cf=0;
 96         if(temp!=0)
 97         {
 98             for(int j=1;j<=len2-1-i;j++)
 99               tempstr+="0";
100             for(int j=len1-1;j>=0;j--)
101             {
102                 t=(temp*(str1[j]-'0')+cf)%10;
103                 cf=(temp*(str1[j]-'0')+cf)/10;
104                 tempstr=char(t+'0')+tempstr;
105             }
106             if(cf!=0) tempstr=char(cf+'0')+tempstr;
107         }
108         str=add(str,tempstr);
109     }
110     str.erase(0,str.find_first_not_of('0'));
111     return str;
112 }
113 
114 //高精度除法
115 //两个正数相除，商为quotient,余数为residue
116 //需要高精度减法和乘法
117 void div(string str1,string str2,string "ient,string &residue)
118 {
119     quotient=residue="";//清空
120     if(str2=="0")//判断除数是否为0
121     {
122         quotient=residue="ERROR";
123         return;
124     }
125     if(str1=="0")//判断被除数是否为0
126     {
127         quotient=residue="0";
128         return;
129     }
130     int res=compare(str1,str2);
131     if(res<0)
132     {
133         quotient="0";
134         residue=str1;
135         return;
136     }
137     else if(res==0)
138     {
139         quotient="1";
140         residue="0";
141         return;
142     }
143     else
144     {
145         int len1=str1.length();
146         int len2=str2.length();
147         string tempstr;
148         tempstr.append(str1,0,len2-1);
149         for(int i=len2-1;i<len1;i++)
150         {
151             tempstr=tempstr+str1[i];
152             tempstr.erase(0,tempstr.find_first_not_of('0'));
153             if(tempstr.empty())
154               tempstr="0";
155             for(char ch='9';ch>='0';ch--)//试商
156             {
157                 string str,tmp;
158                 str=str+ch;
159                 tmp=mul(str2,str);
160                 if(compare(tmp,tempstr)<=0)//试商成功
161                 {
162                     quotient=quotient+ch;
163                     tempstr=sub(tempstr,tmp);
164                     break;
165                 }
166             }
167         }
168         residue=tempstr;
169     }
170     quotient.erase(0,quotient.find_first_not_of('0'));
171     if(quotient.empty()) quotient="0";
172 }
173 
174 
175 const int MAXNX = 200 + 5;
176 string C[MAXNX][MAXNX];
177 void init(){
178     for(int i = 0;i < MAXNX;i ++){
179         for(int j = 0;j < MAXNX;j ++){
180             C[i][j] = "0";
181         }
182     }
183     for(int i = 1;i < MAXNX;i ++){
184         for(int j = 0;j <= i;j ++){
185             if(j == 0) C[i][0] = "1";
186             else{
187                 C[i][j] = add(C[i - 1][j - 1],C[i - 1][j]);
188             }
189         }
190     }
191 }
192 
193 int N;
194 int main() {
195     init();
196     while(~scanf("%d", &N)){
197         string res = "0";
198         for(int i = 0;i <= (N + 1)/ 2;i ++){
199             res = add(res,C[N - i + 1][i]);
200         }
201         cout << res << endl;
202     }
203     return 0;
204 }

ComB