导图社区 高精度计算
数位1000位加法?数位1000位减法?数位1000位乘法?这些听起来无法完成的题目,编程却能做到。快来看一看,挑战一下吧!
编辑于2022-07-01 13:15:59高精度计算
3.大数乘法
题目:给你两个十进制数,数位最多有1000位,求他们的积。
输入输出描述:第一行输入一个整数,第二行输入一个整数,输出一个整数,表示它们的差。
样例: 输入: 12312312312142343254354354 4124354364565765456 输出: 50780339022481084579975969090509171076395424
思路:和减法一样,定义void函数来求解,其实乘法比减法简单: change:转化,把char类型数组转化成int数组。 print:输出,输出答案。 这里有一个优化程序的办法,先把每一位数的乘积算出来,最后再处理进位问题。
代码演示: #include <bits/stdc++.h> using namespace std; const int N = 2010; char s1[N],s2[N]; int a[N],b[N],c[N]; void change(char *sum,int num[]) //把char类型转化成int类型 { int len = strlen(sum); for (int i = 0;i < len;i++) num[len-1-i] = sum[i] - '0'; } void print(int num[]) //输出 { int len = N - 1; while (num[len] == 0 && len >= 1) len--; for (int i = len;i >= 0;i--) printf("%d",num[i]); } int main(){ scanf("%s%s",s1,s2); change(s1,a); //转化 change(s2,b); for (int i = 0;s1[i];i++) { for (int j = 0;s2[j];j++) { c[i + j] += a[i] * b[j]; //计算 } } for (int i = 0;i < N-1;i++) //处理进位问题 { c[i+1] += c[i] / 10; c[i] %= 10; } print(c); //输出 return 0; }
4.斐波那切数列
题目: f[1]=1 f[2]=1 f[i]=f[i−1]+f[i−2](i>=3) 求f[n](1<=n<=200)
输入输出描述:输入一个整数n,输出一个整数,表示f[n]。
样例:输入:3 输出:2
思路:其实就是加法的进阶版——多次加法。定义两个void函数,add和print.add表示加法,来便利我们多次做加法的。print是输出,来输出答案。整个过程除了多了点加法,其他地方没什么差别。
代码演示: #include <bits/stdc++.h> using namespace std; const int N = 2010; int a[N],b[N],c[N]; void add(int a[],int b[],int c[]) //加法 { for (int i = 0;i < N;i++) { c[i] = 0; } for (int i = 0;i < N - 1;i++) { c[i] += a[i] + b[i]; c[i + 1] += c[i] / 10; c[i] %= 10; } } void print(int num[]) //输出 { int len = N - 1; while (num[len] == 0 && len >= 1) len--; for (int i = len;i >= 0;i--) printf("%d",num[i]); } int main(){ int n; scanf("%d",&n); if (n <= 2) printf("1"); //特判 else { a[0] = 1; b[0] = 1; for (int i = 3;i <= n;i++) { add(a,b,c); //做加法 memcpy(a,b,sizeof(b)); //相当于数里面的a=b,b=c memcpy(b,c,sizeof(c)); } print(c); } return 0; }
2.大数减法
题目:给你两个十进制数,数位最多有1000位,求他们的差。
输入输出描述:第一行输入一个整数,第二行输入一个整数,输出一个整数,表示它们的差。
样例: 输入: 12312312312142343254354354 4124354364565765456 输出: 12312308187787978688588898
思路:定义void函数bool函数: sub:减法,其中注意退位。 change:转换,把char类型转化成int类型。 print:输出,输出答案。 binixiao:判断被减数是否比减数小。 函数名称可以自己起。
代码演示: #include<bits/stdc++.h> using namespace std; const int N = 1010; char s1[N],s2[N],tmp[N]; int a[N],b[N],c[N]; void sub(int a[],int b[],int c[])//减法 { int jie = 0;//借 for (int i = 0;i < N-1;i++) { if (jie)//如果需要借位 { c[i] = a[i] - b[i] - 1; jie = 0; } else { c[i] = a[i] - b[i]; } if (c[i] < 0) { c[i] += 10; jie = 1; } } } void change(char *s,int num[])//转化 { int len = strlen(s); for (int i = 0;i < len;i++) { num[len-i-1]=s[i]- '0'; } } void print(int num[])//输出 { int len = N - 1; while (len >= 1 && num[len] == 0) len--; for (int i=len;i>=0;i--) printf("%d",num[i]); } bool binixiao(char s[],char t[])//比你小 { int len1 = strlen(s),len2 = strlen(t); if (len1 != len2) return len1 < len2;//比较位数 for (int i = 0;i < len1;i++) { if(s[i] != t[i])//数字比较 return s[i] < t[i]; } return false; } int main() { scanf("%s%s",s1,s2); if (binixiao(s1,s2))//判断答案是否为负数 { printf("-"); strcpy(tmp,s1); strcpy(s1,s2); strcpy(s2,tmp); //转换,如果为负数就是减数减被减数的相反数 } change(s1,a);//转化成int类型 change(s2,b); sub(a,b,c);//减法 print(c);//输出 return 0; }
1.大数加法
题目:给你两个十进制数,数位最多有1000位,求他们的和。
输入输出描述:第一行输入一个整数,第二行输入一个整数,输出一个整数,表示它们的和。
样例: 输入: 12312312312142343254354354 4124354364565765456 输出: 12312316436496707820119810
思路:一位数一位数的加,如果有进位,就向下一位加一。注意,不能用int数组存,这样会导致系统认为你输入的是一个数,要先用char数组存,再转化成int类型。
代码演示: #include <bits/stdc++.h> using namespace std; const int N = 1010; char a1[N],b1[N]; int a[N],b[N],c[N];//c数组是答案 int main() { scanf("%s%s",a1,b1); int n = strlen(a1),m = strlen(b1); for (int i = 0;i < n;i++) { a[n-1-i] = a1[i] - '0';//转化 } for (int i = 0;i < m;i++) { b[m-1-i] = b1[i] - '0';//转化 } for (int i = 0;i < N - 1;i++) { c[i] += (a[i] + b[i]); if (c[i] >= 10) { c[i+1]++;//进位 } c[i] = c[i] % 10; } int len = N - 1; while (len >= 1 && c[len] == 0) len--; //获取答案是几位数 for (int i = len;i >= 0;i--) printf("%d",c[i]); return 0; }