1：大菲波数
斐波那契数列是这样定义的：f(1)=1；f(2)=1；f(n)=f(n-1)+f(n-2)（n>=3）。所以1，1，2，3，5，8，13……就是斐波那契数列。输入一个整数n，求斐波那契数列的第n项。
输入格式:
首先输入一个正整数T，表示测试数据的组数，然后输入T组测试数据。每组测试数据输入一个整数n（1≤n≤1000）。
输出格式:
对于每组测试，在一行上输出斐波那契数列的第n项f(n)。
输入样例:
2 105 4
输出样例:
3928413764606871165730 3
出处:
HDOJ 1715
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
解析：用数组模拟大整数的运算，先根据题意预处理所有结果，最后输入数据查表就行
#include <iostream> #include <cstring> #include <vector> using namespace std; const int N = 1010; string f[N]; vector<int> add(vector<int>A, vector<int>B) { vector<int>C; for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i ++ ) { if(i < A.size()) t += A[i]; if(i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { f[1] = f[2] = "1"; for (int i = 3; i < N; i ++ ) { string s1 = f[i - 1]; string s2 = f[i - 2]; vector<int>A, B; for (int i = s1.size() - 1; i >= 0; i -- ) A.push_back(s1[i] - '0'); for (int i = s2.size() - 1; i >= 0; i -- ) B.push_back(s2[i] - '0'); auto C = add(A, B); string s; for (int i = C.size() - 1; i >= 0; i -- ) s += to_string(C[i]); f[i] = s; } int T; cin >> T; while (T -- ) { int x; cin >> x; cout << f[x] << endl; } return 0; }
2：大数的乘法
输入一个大正整数和一个非负整数，求它们的积。
输入格式:
测试数据有多组，处理到文件尾。每组测试输入1个大正整数A（位数不会超过1000）和一个非负整数B（int范围）。
输出格式:
对于每组测试，输出A与B的乘积。
输入样例:
1 1 123 100 12345678910 8 123456789101234567891012345678910 7
输出样例:
1 12300 98765431280 864197523708641975237086419752370
出处:
ZJUTOJ 1027
说明:
原题的B是一位数，本题修改为int范围内的整数
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
解析：由于b的范围是int型，而字符串s的每一位数字的范围都是0~9，可以得出只要b取int类型极限，s[i]取2 ~ 9都会超出int类型，所以我们需要使用long long 类型
#include <iostream> #include <vector> using namespace std; typedef long long LL; vector<LL> mul(vector<LL>A, int b) { vector<LL>C; for (LL i = 0, t = 0; i < A.size() || t; i ++ ) { if(i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string s; int b; while (cin >> s >> b) { vector<LL>A; for (int i = s.size() - 1; i >= 0; i -- ) A.push_back(s[i] - '0'); auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; } return 0; }
3：大数和
给定一些大整数，请计算其和。
输入格式:
测试数据有多组。对于每组测试数，首先输入一个整数n（n≤100），接着输入n个大整数（位数不超过200）。若n＝0则表示输入结束。
输出格式:
对于每组测试，输出n个整数之和，每个结果单独占一行。
输入样例:
2 43242342342342 -1234567654321 0
输出样例:
42007774688021
出处:
ZJUTOJ 1214
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
解析：因为一个正数加一个负数不好运算，所以我们可以把加上一个负数的运算转化成减去一个数，所以可以得出此题考察的是高精度的加减法运算
#include <iostream> #include <vector> using namespace std; vector<int> add(vector<int>&A,vector<int>&B)//加法 { vector<int>C; for(int i = 0,t = 0; i < A.size() || i < B.size() || t; i ++ ) { if(i < A.size()) t += A[i]; if(i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } while(C.back() == 0 && C.size() > 1) C.pop_back();//去掉前导的零 return C; } vector<int> sub(vector<int>&A, vector<int>&B)//减法 { vector<int>C; for(int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i]-t; if(i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if(t < 0) t = 1; else t = 0; } while(C.back() == 0 && C.size() > 1) C.pop_back(); return C; } bool cmp(vector<int>&A,vector<int>&B)//比较大小，前面大返回真，否则返回假 { if(A.size() != B.size()) return A.size() > B.size(); for(int i = 0; i < A.size(); i ++ ) if(A[i] != B[i]) return A[i] > B[i]; return true; } int main() { int n; while(cin >> n && n) { int a1 = 1,ans1 = 1;//判断符号 vector<int>ans = {0};//初始化 while(n -- ) { string a; vector<int>A; cin >> a; if(a[0] == '-') { a1 = 0; for(int i = a.size() - 1; i > 0; i -- ) A.push_back(a[i] - '0'); } else { for(int i = a.size() - 1 ; i >= 0; i -- ) A.push_back(a[i] - '0'); a1=1; } if(cmp(ans,A))//前面大 { if(ans1 && a1) ans = add(ans, A),ans1 = 1; else if(ans1 && !a1) ans = sub(ans, A),ans1 = 1; else if(!ans1 && !a1) ans = add(ans, A),ans1 = 0; else ans = sub(ans, A),ans1 = 0; } else { if(ans1 && a1) ans = add(ans, A),ans1 = 1; else if(ans1 && !a1) ans = sub(A, ans), ans1 = 0; else if(!ans1 && !a1) ans=add(ans, A), ans1 = 0; else ans = sub(A, ans),ans1 = 1; } } if(!ans1 && ans[0]) cout << "-";//处理符号和处理负零的情况 for(int i = ans.size() - 1; i >= 0; i -- ) cout << ans[i]; cout << endl; } return 0; }
