大数问题（1002、1042、1133、1250、1297、1715、1753、1865、2100）

1002、A + B Problem II[A+B，大数相加]

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.
Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line is the an equation “A + B = Sum”, Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.
Sample Input

2
1 2
112233445566778899 998877665544332211

Sample Output

Case 1:
1 + 2 = 3Case 2:
112233445566778899 + 998877665544332211 = 1111111111111111110

Code

/* 大数加法： 数字最多1000位，无法用整型数据类型进行存储，考虑使用字符数组进行存储，对每一位分别进行计算，将结果也存储在字符数组中。 注意：若两个数的位数不相同，要在前面进行补0 两个字符串的最前面都要加个0，防止产生进位输出结果时，前面的0不进行输出 */ 
#include<iostream>
#include<string>
using namespace std;//大数相加函数
string addlong(string a,string b){
    //计算a 和 b 的长度int i,j;for(i=0;a[i]!='\0';i++);for(j=0;b[j]!='\0';j++); //对短的字符串进行补0 if(i<j){
    for(int k=0;k<j-i;k++){
    a="0"+a;}i=j;}else if(j<i){
    for(int k=0;k<i-j;k++){
    b="0"+b;}j=i;}//a和b此时的长度均为j(i); //计算a+bchar c[1010];int sum,t=0;//t代表每次的进位，sum表示每次对应位数的和 for(int k=i-1;k>=0;k--){
    sum=(a[k]-'0')+(b[k]-'0')+t;if(sum>=10){
    c[k]=sum-10+'0';t=1;}else{
    c[k]=sum+'0';t=0;}}c[i]='\0';//将第一位的字符0去掉string s="";int flag=0;for(int k=0;c[k]!='\0';k++){
    if(c[k]!='0'||flag==1){
    s=s+c[k];flag=1;}}return s;
}int main(){
    int t,num=0;cin>>t;while(t--){
    num++;string a,b;cin>>a>>b;string str1=a,str2=b;//在a和b的前面加0，防止产生进位a="0"+a;b="0"+b;//输出if(t==0){
    cout<<"Case "<<num<<":"<<endl;cout<<str1<<" + "<<str2<<" = "<<addlong(a,b)<<endl;}else{
    cout<<"Case "<<num<<":"<<endl;cout<<str1<<" + "<<str2<<" = "<<addlong(a,b)<<endl<<endl;    }}
} 

1042、N！[大数乘法]

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
Input
One N in one line, process to the end of file.
Output
For each N, output N! in one line.
Sample Input

1
2
3

Sample Output

1
2
6

Code
方法一 未优化的算法

/* 大数乘法 计算n！,其中n的范围为[0,10000]; 10000！是非常大的数，故而需要用数组模拟乘法运算 */
#include<iostream>
#include<string.h>
using namespace std;
#define max 4000
int a[max]; void multiply(int n){
    int add;//进位a[0]=1;for(int i=2;i<=n;i++){
    //每次要乘以iadd=0;//将每次阶乘的结果存放在a[]数组中for(int j=0;j<max;j++){
    a[j]=a[j]*i+add;add=a[j]/10;//产生进位 a[j]=a[j]%10;} }//从后往前，找到第一个不为0的值的下标 int k; for(k=max-1;a[k]==0;k--);for(int i=k;i>=0;i--){
    cout<<a[i];} cout<<endl;
}
int main(){
    int n;while(cin>>n){
    memset(a,0,sizeof(a));//初始化数组--将a中的前sizeof(a)个字节用0代替 multiply(n);}return 0; 
}

方法二 优化后的

/* 大数乘法 计算n！,其中n的范围为[0,10000]; 10000！是非常大的数，故而需要用数组模拟乘法运算 */
#include<iostream>
#include<cstring>
using namespace std;
#define max 100001
int a[max]; void multiply(int n){
    int add,m=0;//进位a[0]=1;for(int i=1;i<=n;i++){
    //每次要乘以iadd=0;//将每次阶乘的结果存放在a[]数组中,且每一个a[]可以存放五位数 for(int j=0;j<=m;j++){
    a[j]=a[j]*i+add;add=a[j]/100000;//产生进位 a[j]=a[j]%100000;} if(add>0){
    m++;a[m]=add;} }//从后往前，找到第一个不为0的值的下标 cout<<a[m]; for(int i=m-1;i>=0;i--){
    //cout<<a[i];printf("%05d",a[i]);//表示输出的整型宽度至少为5位} cout<<endl;
}
int main(){
    int n;while(cin>>n){
    multiply(n);}return 0; 
}

1133、Buy the Ticket[大数乘法|大数除法]

The “Harry Potter and the Goblet of Fire” will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?

Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).

Now the problem for you is to calculate the number of different ways of the queue that the buying process won’t be stopped from the first person till the last person.
Note: initially the ticket-office has no money.

The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
Input
The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.
Output
For each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.
Sample Input

3 0
3 1
3 3
0 0

Sample Output

Test #1:
6
Test #2:
18
Test #3:
180

Code

//公式：(m+n)!*(m-n+1)/m+1
//大数乘法和大数除法
#include<iostream>
#include<cstring>
using namespace std;
#define max 1000
int a[max],b[max];
//大数乘法
int multiply(int n,int m,int t){
    int temp,add;a[0]=1;for(int i=2;i<=n;i++){
    add=0;//进位为0 //每个数组单元只存储一位数 for(int j=0;j<max;j++){
    temp=i*a[j]+add;a[j]=temp%10;add=temp/10; }}//a[]中存储n!的值 //m乘以n! add=0;for(int i=0;i<max;i++){
    temp=a[i]*m+add;a[i]=temp%10;add=temp/10;}//a[]数组中的位数int len;for(len=max-1;len>=0;len--){
    if(a[len]!=0){
    break;}}//计算除以t的值——大数除法，转化为减法的例子int c=0,j=0;//c代表余数 for(int i=len;i>=0;i--,j++){
    b[j]=(c*10+a[i])/t;c=(c*10+a[i])%t;//将余数借给下一位 }//将数组b[]输出int flag=0;//注意00034这样的数据 for(int i=0;i<=j-1;i++){
    if(b[i]==0&&flag==0){
    flag=0;}else{
    flag=1;cout<<b[i];}}cout<<endl;return 0;
} 
int main(){
    int m,n,num=0;//[0,100] while(cin>>m>>n){
    if(m==0&&n==0) return 0;//计算(m+n)！大数阶乘memset(a,0,sizeof(a));memset(b,0,sizeof(b));num++;cout<<"Test #"<<num<<":"<<endl;if(m<n){
    cout<<0<<endl;continue;}multiply(m+n,m-n+1,m+1); //multiply(6,1,4)}return 0;
}

1250、Hat’s Fibonacci[大数加法]

A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.
Input
Each line will contain an integers. Process to end of file.
Output
For each case, output the result in a line.
Sample Input

100

Sample Output

4203968145672990846840663646
Note:
No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

Code

/* Fibonacci: F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4) 思路：大数加法，利用二维数组 */ 
#include<iostream>
#include<cstring>
using namespace std;
int a[8000][600];
int main(){
    int n,k;memset(a,0,sizeof(a));a[0][0]=a[1][0]=a[2][0]=a[3][0]=1;//分别表示F(1)=1,F(2)=1,F(3)=1,F(4)=1for(int i=4;i<8000;i++){
    k=0;//进位for(int j=0;j<600;j++){
    a[i][j]=a[i-1][j]+a[i-2][j]+a[i-3][j]+a[i-4][j]+k;k=a[i][j]/10000;//每一个位置存4位数a[i][j]=a[i][j]%10000; } } while(cin>>n){
    int t=590;while(a[n-1][t]==0){
    t--;//从右向左找到第一个不等于0的值 }printf("%d",a[n-1][t]);t--;for(;t>=0;t--){
    printf("%04d",a[n-1][t]);}printf("\n");}return 0;
}

1297、Children’s Queue[大数加法]

There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)
Output
For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.
Sample Input

1
2
3

Sample Output

1
2
4

Code

/* 排序问题： F(0)=1,F(1)=1,F(2)=2,F(3)=4 F(n)=F(n-1)+F(n-2)+F(n-4) */
#include<iostream>
#include<cstring>
using namespace std;
int a[1100][500];
int main(){
    int n;//n[1,1000]memset(a,0,sizeof(a));a[0][0]=1;a[1][0]=1;a[2][0]=2;a[3][0]=4;for(int i=4;i<1100;i++){
    int k=0;for(int j=0;j<500;j++){
    a[i][j]=a[i-1][j]+a[i-2][j]+a[i-4][j]+k;k=a[i][j]/10000;//每四位存一次，产生进位a[i][j]=a[i][j]%10000; }}while(cin>>n){
    //从右向左输出count[n][j]中的数 int t=499;while(a[n][t]==0){
    t--;}printf("%d",a[n][t]);t--;for(;t>=0;t--){
    printf("%04d",a[n][t]);}printf("\n");}return 0;
} 

1715、大菲波数[大数加法]

Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
Input
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
Output
输出为N行，每行为对应的f(Pi)。
Sample Input

5
1
2
3
4
5

Sample Output

1
1
2
3
5

Code

/* f(1)=1,f(2)=1 f(n)=f(n-1)+f(n-2) n>=3; */
#include<iostream>
#include<cstring>
using namespace std;
int a[1100][310];
int main(){
    memset(a,0,sizeof(a));a[0][0]=0;a[1][0]=1;a[2][0]=1;for(int i=3;i<=1000;i++){
    int k=0;for(int j=0;j<=300;j++){
    a[i][j]=a[i-1][j]+a[i-2][j]+k;k=a[i][j]/10000;a[i][j]=a[i][j]%10000;}}int t,n;cin>>t;while(t--){
    cin>>n;//[1,1000];//输出a[n][]int m=300;while(a[n][m]==0){
     m--;} printf("%d",a[n][m]);m--;for(;m>=0;m--){
    printf("%04d",a[n][m]);}printf("\n");}return 0;
}

1753、A+B [小数位数的相加]

现在，给你两个正的小数A和B，你的任务是代表大明计算出A+B的值。
Input
本题目包含多组测试数据，请处理到文件结束。
每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。
Output
请在一行里面输出输出A+B的值，请输出最简形式。详细要求请见Sample Output。
Sample Input

1.1 2.9
1.1111111111 2.3444323343
1 1.1

Sample Output

4
3.4555434454
2.1

Code

/* 给任意两个正的小数A,B，计算A+B的值 如：99999.889 0.1111000.0 10000.0112233.1 333.9123450000 777123400000 777.7000.000 0.0000 */
#include<iostream>
#include<string>
#include<cstring>
using namespace std;int add(string s1,string s2){
    s1="0"+s1;//补一个0,防止产生进位 s2="0"+s2;char s[410];int j=0,k=0,sum;int len=s1.size();for(int i=len-1;i>=0;i--){
    if(s1[i]=='.'){
    s[j++]='.';continue;}sum=(s1[i]-'0')+(s2[i]-'0')+k;k=sum/10; s[j++]=sum%10+'0';//转为字符}//输出准备int flag=0;for(int l=0;l<strlen(s);l++){
    if(s[l]=='.'){
    flag=1;}} //不输出前导0 int i=j-1;while(s[i]=='0'){
    i--;}//小数部分int count=0,m;//有小数 if(flag==1){
    for(m=0;s[m]!='.';m++){
    if(s[m]=='0'){
    count++;}else{
    break;}} if(s[m]=='.'){
    count++;}}//输出 if(i<count){
    cout<<"0"<<endl;return 0;} for(;i>=count;i--){
    cout<<s[i];}cout<<endl;return 0;
}
int main(){
    string s1,s2;while(cin>>s1>>s2){
    //将s1和s2的小数点位置对齐，空余位置用0补齐int len1=s1.size();int len2=s2.size();//寻找s1小数点前有几位，小数点后有几位 int num1=0; for(int i=0;i<len1;i++){
    if(s1[i]=='.'){
    break;}else{
    num1++;}} //s1小数点前num1位，小数点后len1-num1-1位 int n1=len1-num1-1;//寻找s2小数点前有几位，小数点后有几位 int num2=0;for(int i=0;i<len2;i++){
    if(s2[i]=='.'){
    break;}else{
    num2++;}}//s2小数点前num2位，小数点后len2-num2-1位 int n2=len2-num2-1;//小数点前补0 if(num1<num2){
    int t=num2-num1;//需要补t个0,防止进位 for(int i=0;i<t;i++){
    s1="0"+s1;} }else if(num1>num2){
    int t=num1-num2;//需要补t个0for(int i=0;i<t;i++){
    s2="0"+s2;} }//小数点后补0if(n1<n2){
    int t=n2-n1;//需要补t个0 for(int i=0;i<t;i++){
    s1=s1+"0";} }else if(n1>n2){
    int t=n1-n2;//需要补t个0for(int i=0;i<t;i++){
    s2=s2+"0";} }add(s1,s2);}return 0;
}

1865、1sting[大数加法]

You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get.
Input
The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.
Output
The output contain n lines, each line output the number of result you can get .
Sample Input

3
1
11
11111

Sample Output

1
2
8

Code

/* 斐波那契数列：f(1)=1,f(2)=2 f(n)=f(n-1)+f(n-2) */ 
#include<iostream>
#include<cstring>
using namespace std;
int a[210][620];
int main(){
    memset(a,0,sizeof(a));a[1][0]=1;a[2][0]=2;for(int i=3;i<=200;i++){
    int k=0;for(int j=0;j<=600;j++){
    a[i][j]=a[i-1][j]+a[i-2][j]+k;k=a[i][j]/10000;a[i][j]=a[i][j]%10000;}} int t;cin>>t;while(t--){
    char c[210];cin>>c;int len=strlen(c);//输出a[len][]int t=600;while(a[len][t]==0){
    t--;} printf("%d",a[len][t]);t--;for(;t>=0;t--){
    printf("%04d",a[len][t]);}printf("\n");}return 0;
}

2100、Lovekey[大数加法]

XYZ-26进制数是一个每位都是大写字母的数字。 A、B、C、…、X、Y、Z 分别依次代表一个0 ~ 25 的数字，一个 n 位的26进制数转化成是10进制的规则如下
A0A1A2A3…An-1 的每一位代表的数字为a0a1a2a3…an-1 ，则该XYZ-26进制数的10进制值就为

m ＝ a0 * 26^(n-1) + a1 * 26^(n-2) + … + an-3* 26^2 + an-2*26 + an-1

一天vivi忽然玩起了浪漫，要躲在学校的一个教室，让枫冰叶子去找，当然，她也知道枫冰叶子可不是路痴，于是找到了XYZ的小虾和水域浪子帮忙，他们会在vivi藏的教室的门口，分别写上一个XYZ-26进制数，分别为 a 和 b，并且在门锁上设置了密码。显然，只有找到密码才能打开锁，顺利进入教室。这组密码被XYZ的成员称为lovekey。庆幸的是，枫冰叶子知道lovekey是 a的10进制值与b的10进制值的和的XYZ-26进制形式。当然小虾和水域浪子也不想难为枫冰叶子，所以a 和 b 的位数都不会超过200位。
例如第一组测试数据
a = 0 * 26^5+0* 26^4+ 0* 26^3+ 0 26^2 + 326 + 7 = 85
b = 126^2 + 226 + 4 = 732
则 a + b = 817 = BFL
Input
题目有多组测试数据。
每组测试数据包含两个值均为的XYZ－26进制数，每个数字的每位只包含大写字母，并且每个数字不超过200位。
Output
输出XYZ的lovekey，每组输出占一行。
Sample Input

AAAADH  BCE
DRW  UHD
D  AAAAA

Sample Output

BFL
XYZ
D

Code

/* 直接进行26进制相加 不需要先转10进制再相加再转26进制 */
#include<iostream>
#include<string>
using namespace std;void add(string a,string b){
    //补一个0,防止产生进位a="A"+a;b="A"+b;char s[220];memset(s,'A',sizeof(s));int j=0,k=0,sum;int len=a.size();for(int i=len-1;i>=0;i--){
    sum=(a[i]-'A')+(b[i]-'A')+k;k=sum/26;s[j]=sum%26+'A';j++;}int t=j-1;while(s[t]=='A'){
    t--;}for(;t>=0;t--){
    cout<<s[t];}cout<<endl;
}
int main(){
    string a,b;while(cin>>a>>b){
    int lena=a.size();int lenb=b.size();//补齐位数if(lena<lenb){
    int t=lenb-lena;for(int i=0;i<t;i++){
    a="A"+a; }} else if(lenb<lena){
    int t=lena-lenb;for(int i=0;i<t;i++){
    b="A"+b; }} add(a,b);}
}