经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
高精度加减乘除小数详解
来源:cnblogs  作者:typerxiaozhu  时间:2023/8/16 9:14:18  对本文有异议

高精度

简介

众所周知,在计算机中,每个数据类型都是有存储上限的,那么当数字特别大时应该怎么办呢?这时高精度就产生了。高精度的主要思想就是模拟手算,然后将结果存储到数组中去,相同的,小数也有精度问题,也可以使用相同的思路

存储

这里使用vector 来进行存储,因为这样不需要去管结果有多少位,直接使用push_back() 函数就行了,虽然和数组比起来会慢一些,不过差别也仅仅是常数而已

输入:定义一个字符串,然后将字符串的每位转数字存储起来就行了

  1. string a; vector <int> A;
  2. cin>>a;
  3. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');

输出:请注意,输入的时候我是反过来的,这样做是为了添加元素比较方便,那么输出的时候也要注意倒着输出

  1. for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

高精度加法

上文中已经提到,在进行高精度运算是模拟手算的,那么接下来就来回忆一下,我们是怎么手动做加法的

图为用竖式做加法的示例,我们可以发现主要组成部分有两个加数、结果、还有进位,于是我们的变量就可以呼之欲出了

  1. vector <int> A; vector <int> B; vector <int> C; int t;

然后我们再使用循环遍历(从0开始)来进行计算,循环位数较大的那个加数的每一位,然后加到 \(t\) 里面就行了

那么 \(C_i\) 就等于 \(A_i+B_i\)\(mod~10\),进位 \(t\) 就等于 \((A_i+B_i)/10\)

注意在循环完之后,如果 \(t\neq 0\) 的话,还要加上一位

代码模板

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. vector<int> add(vector<int>& A,vector<int>& B)
  6. {
  7. vector<int> C;
  8. int t=0;
  9. for(int i=0;i<max(A.size(),B.size());i++)
  10. {
  11. if(i<A.size()) t+=A[i];
  12. if(i<B.size()) t+=B[i];
  13. C.push_back(t%10);
  14. t/=10;
  15. }
  16. if(t) C.push_back(t);
  17. return C;
  18. }
  19. int main()
  20. {
  21. string a,b;
  22. cin>>a;
  23. cin>>b;
  24. vector<int> A;
  25. vector<int> B;
  26. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  27. for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
  28. vector<int> C=add(A,B);
  29. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  30. return 0;
  31. }

高精度减法

不带负数

首先,先回忆一下我们是怎么用竖式进行减法的

与加法不同,我们在列减法的竖式时会把大数放在上面,小数放在下面,因为减法涉及到借位的问题

所以说在计算机计算的时候,我们要先判断 \(A\) 是否 \(\geq B\),如果 \(<B\),为了避免增加代码量我们直接计算 \(-(A-B)\) 就行了

那么因为数字特别大,所以我们也需要手写一个比较函数,那么我们是怎么比较两个数的呢?

先比较哪个位数大,位数多的大,如果位数一样,那么分别比较每一位

  1. bool cmp(vector<int>& A, vector<int>& B)
  2. {
  3. if (A.size() != B.size())return A.size() > B.size();
  4. for (int i = A.size()-1; i>=0; i--)
  5. {
  6. if (A[i] != B[i]) return A[i] > B[i];
  7. }
  8. return true;
  9. }

类似加法,变量分别为被减数,减数,结果,借位

使用循环遍历(从0开始)被减数的每一位

借位 \(t\) = \(A_i-(B_i)-t\),如果说最终结果小于0,就要借一位,将 \(t+10\) 最后再 \(mod~10\) 便是 \(C_i\)

如果借位了 \(t=1\) 否则 \(t=0\)

注意:为了方便,我们直接不管结果是否小于0,每次都加10,因为如果结果不小于0的话 \(+10\) \(mod~10\) 就抵消了对结果不影响

最后还要去除前导0

  1. while (C.size() > 1 && C.back() == 0)
  2. {
  3. C.pop_back();
  4. }

代码模板

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. bool cmp(vector<int>& A,vector<int>& B)
  6. {
  7. if(A.size()!=B.size()) return A.size()>B.size();
  8. for(int i=A.size()-1;i>=0;i--)
  9. {
  10. if(A[i]!=B[i]) return A[i]>B[i];
  11. }
  12. return true;
  13. }
  14. vector<int> sub(vector<int>& A,vector<int>& B)
  15. {
  16. int t=0;
  17. vector<int> C;
  18. for(int i=0;i<A.size();i++)
  19. {
  20. t=A[i]-t;
  21. if(i<B.size()) t-=B[i];
  22. C.push_back((t+10)%10);
  23. if(t<0) t=1;
  24. else t=0;
  25. }
  26. while(C.size()>1&&C.back()==0) C.pop_back();
  27. return C;
  28. }
  29. int main()
  30. {
  31. string a,b;
  32. vector<int> A,B;
  33. cin>>a;
  34. cin>>b;
  35. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  36. for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
  37. if(cmp(A,B))
  38. {
  39. vector<int> C=sub(A,B);
  40. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  41. }
  42. else
  43. {
  44. vector<int> C=sub(B,A);
  45. cout<<'-';
  46. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  47. }
  48. return 0;
  49. }

带有负数

  • 自然数 \(A\) 减负数 \(B\) 等于 $A+\vert B\vert $
  • 负数 \(A\) 减自然数 \(B\) 等于 \(-(\vert A \vert+B)\)
  • 自然数 \(A\) 减负数 \(B\) 等于 \(\vert A\vert+B\)
  • 负数 \(A\) 减负数 \(B\)\(\vert A\vert\leq\vert B\vert\) 时,等于\(\vert B\vert -\vert A\vert\)\(\vert A \vert>\vert B\vert\) 时,等于 \(-(\vert A\vert-\vert B\vert)\)

代码模板

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. bool cmp(vector<int>& A,vector<int>& B)
  6. {
  7. if(A.size()!=B.size()) return A.size()>B.size();
  8. for(int i=A.size()-1;i>=0;i--)
  9. {
  10. if(A[i]!=B[i]) return A[i]>B[i];
  11. }
  12. return true;
  13. }
  14. bool cmp1(vector<int>& A,vector<int>& B)
  15. {
  16. if(A.size()!=B.size()) return A.size()>B.size();
  17. for(int i=A.size()-1;i>=0;i--)
  18. {
  19. if(A[i]!=B[i]) return A[i]>B[i];
  20. }
  21. return false;
  22. }
  23. vector<int> add(vector<int>A,vector<int>B)
  24. {
  25. vector<int> C;
  26. int t=0;
  27. for(int i=0;i<max(A.size(),B.size());i++)
  28. {
  29. if(i<A.size()) t+=A[i];
  30. if(i<B.size()) t+=B[i];
  31. C.push_back(t%10);
  32. t/=10;
  33. }
  34. if(t) C.push_back(t);
  35. return C;
  36. }
  37. vector<int> sub(vector<int>& A,vector<int>& B)
  38. {
  39. int t=0;
  40. vector<int> C;
  41. for(int i=0;i<A.size();i++)
  42. {
  43. t=A[i]-t;
  44. if(i<B.size()) t-=B[i];
  45. C.push_back((t+10)%10);
  46. if(t<0) t=1;
  47. else t=0;
  48. }
  49. while(C.size()>1&&C.back()==0) C.pop_back();
  50. return C;
  51. }
  52. int main()
  53. {
  54. string a,b;
  55. vector<int> A,B;
  56. cin>>a;
  57. cin>>b;
  58. if(a[0]!='-'&&b[0]!='-')
  59. {
  60. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  61. for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
  62. if(cmp(A,B))
  63. {
  64. vector<int> C=sub(A,B);
  65. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  66. }
  67. else
  68. {
  69. vector<int> C=sub(B,A);
  70. cout<<'-';
  71. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  72. }
  73. }
  74. else if(a[0]=='-'&&b[0]!='-')
  75. {
  76. for(int i=a.size()-1;i>=1;i--) A.push_back(a[i]-'0');
  77. for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
  78. vector<int> C=add(A,B);
  79. cout<<'-';
  80. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  81. }
  82. else if(a[0]!='-'&&b[0]=='-')
  83. {
  84. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  85. for(int i=b.size()-1;i>=1;i--) B.push_back(b[i]-'0');
  86. vector<int> C=add(A,B);
  87. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  88. }
  89. else if(a[0]=='-'&&b[0]=='-')
  90. {
  91. for(int i=a.size()-1;i>=1;i--) A.push_back(a[i]-'0');
  92. for(int i=b.size()-1;i>=1;i--) B.push_back(b[i]-'0');
  93. if(cmp1(A,B))
  94. {
  95. cout<<'-';
  96. vector<int> C=sub(A,B);
  97. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  98. }
  99. else
  100. {
  101. vector<int> C=sub(B,A);
  102. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  103. }
  104. }
  105. return 0;
  106. }

高精度乘法

高精度乘低精度

高精度乘法与前面有所不同,在我们用竖式计算乘法时,都是一位对一位的,而在这里因为 \(b\) 比较小,所以我们直接拿大数的每一位去乘上 \(b\) 就行了,那么我们还是拿一个竖式举例:

先模拟一下这个例子:

\(C_0=(3×12)~mod~10=6\) \(t_1=3×12/10=3\) \(C_1=(2×12+t_1)~mod~10=7\) \(t_2=2×12/10=2\)

\(C_2=(1×12+2)~mod~10=4\) \(t_3=1×12/10=1\) \(C_3=t_3=1\)

那么最终的结果就是 1476

我们用循环遍历 \(A\) 的每一位就行了

如果最后 \(t\neq0\),那么就添上 \(t~mod~10\),注意因为我们是直接乘上 \(b\) 所以进位不一定是个位数,要用一个循环来做

代码模板

  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> mul(vector<int>& A,int B)
  6. {
  7. int t=0;
  8. vector<int> C;
  9. for(int i=0;i<A.size();i++)
  10. {
  11. t+=A[i]*B;
  12. C.push_back(t%10);
  13. t/=10;
  14. }
  15. while(t)
  16. {
  17. C.push_back(t%10);
  18. t/=10;
  19. }
  20. return C;
  21. }
  22. int main()
  23. {
  24. string a;
  25. int B;
  26. cin>>a;
  27. cin>>B;
  28. vector<int> A;
  29. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  30. vector<int> C=mul(A,B);
  31. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  32. }

高精度乘高精度

因为两个数都很大,所以我们按照手算的方式进行计算,首先先举个例子:

我们可以发现 \(A_0×B_0\) 对应 \(C_0\) \(A_1×B_0\) 对应 \(C_1\) \(A_2×B_0\) 对应 \(C_2\) 以此类推……

我们可以得出 \(A_i×B_j\) 对应 \(C_i\)\(_+\)\(_j\)

那么进位 \(t\) 就等于\(C_i\)\(_+\)\(_j\)\(/10\)

与大数乘小数一样,最后还要添上 \(t\),不过这里是模拟手算,不需要再循环了

因为不能直接往后添数,所以我们的答案先初始化长一点,否则无法存储 vector<int> C(A.size() + B.size() + 7, 0);

最后记得去除前导0

代码模板

  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> mul(vector<int>& A,vector<int>& B)
  6. {
  7. vector<int> C(A.size()+B.size()+7,0);
  8. for(int i=0;i<A.size();i++)
  9. {
  10. int t=0;
  11. for(int j=0;j<B.size();j++)
  12. {
  13. C[i + j] += A[i] * B[j] + t;
  14. t = C[i + j] / 10;
  15. C[i + j] %= 10;
  16. }
  17. if(t) C[i+B.size()]+=t;
  18. }
  19. while(C.size()>1&&C.back()==0) C.pop_back();
  20. return C;
  21. }
  22. int main()
  23. {
  24. string a,b;
  25. cin>>a; cin>>b;
  26. vector<int> A,B;
  27. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  28. for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
  29. vector<int> C=mul(A,B);
  30. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  31. }

注意:\(t\) 在一轮用完后要及时初始化为0,另外 \(t\) 一定要赋值为 \(C_i\)\(_+\)\(_j/10\),因为当重叠时可能加法上又有进位。

高精度除法

大数除小数

首先,回想一下我们是怎么用竖式算除法的

我们可以发现几个变量分别是被除数、除数、商、余数

我们使用一个变量 \(r\) 来存储余数

因为计算机不像人那么聪明,所以一位一位来

首先看1,1除11不够,商0,余1

再看2,因为现在余1,所以变成10+2,12除11够,商1,余1,结束

我们就可以得到 \(r=r×10+A_i~mod~B\)\(C_i=r×10+A_i~/B\)

注意因为我们除法是从前往后的,所以去除前导0的时候要先进行翻转

代码模板

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. vector<int> div(vector<int>& A, int& B,int& r)
  7. {
  8. r=0; vector<int> C;
  9. for(int i=A.size()-1;i>=0;i--)
  10. {
  11. r=r*10+A[i];
  12. C.push_back(r/B);
  13. r%=B;
  14. }
  15. reverse(C.begin(),C.end());
  16. while(C.size()>1&&C.back()==0) C.pop_back();
  17. return C;
  18. }
  19. int main()
  20. {
  21. string a;
  22. cin>>a;
  23. vector<int> A; int B;
  24. cin>>B;
  25. for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
  26. int r;
  27. vector<int> C=div(A,B,r);
  28. for(int i=C.size()-1;i>=0;i--) cout<<C[i];
  29. cout<<endl;
  30. cout<<r;
  31. }

压位

因为数组一个位置可以存很大的数,所以我们只存一个数有点浪费,所以我们可以使用压位这个技巧

我们先开两个全局变量 \(N=x\) \(M=10^x\) (x为你想压的位数)

输入的时候改成

  1. int st=max(0,1-N+1),len=i-st+1;
  2. A.push_back(a.substr(st,len)-'0');

注意所有 \(/10~mod~10\) 的操作均要修改成 \(/M~mod~M\)
输出的时候要先输出首位,因为输出的时候有可能不一定正好是 \(x\) 位数,要使用 printf("%04d",C[i])(以4位举例)
所以当输出完首位后,从C.size()-2开始

高精度小数

保留?位

首先,我们先算出整数部分,因为计算机不像手算,直接算出就可以了,不需要像手算一样一位一位算

然后我们回想一下手算是怎么算小数部分的,我们将上一位算得的余数乘10再除以除数就行了

示意图

代码模板

  1. //c是位数
  2. digit[0]=a/b;
  3. a%=b;
  4. for(int i=1;i<=c+1;i++)
  5. {
  6. a*=10;
  7. digit[i]=a/b;
  8. a%=b;
  9. }
  10. cout<<digit[0]<<'.';
  11. for(int i=1;i<=c;i++) cout<<digit[i];

四舍五入

由于小数会出现循环,所以题目一般会给出一些要求,例如最后一位四舍五入

四舍五入即为 当数 \(>=5\) 进一位,\(<5\) 时舍去

不过我们需要注意,进位的时候可能会出现“多米诺骨牌”

例如 9.99999... 进位后会变成10.00000....,所以我们需要使用循环来处理

注意进位到整数位如果变成10不用管,因为我们是直接输出整数位的

代码模板

  1. if(digit[c+1]>=5) digit[c]++;
  2. for(int i=c;i>0;i--)
  3. {
  4. if(digit[i]>=10)
  5. {
  6. digit[i]-=10;
  7. digit[i-1]++;
  8. }
  9. }

8进制转10进制

因为8进制小数能完美转换成10进制小数,所以我们就不用管保留几位的问题

举个例子,0.75如何转换成10进制呢?

\(7/8^1+7/8^2=0.953125\) 这样就转换完成了,不会的去补初一数学

于是我们就可以模拟手算(见上文保留?位),再用数组进行存储就行了,因为题目也给出了范围 \(0<k<15\),因为所有小数点后位数为n的八进制小数都可以表示成小数点后位数不多于3n的十进制小数。所以我们数组长度开个50就行了

还要注意进位的问题,与之前一样都是”多米诺骨牌“,所以要用循环

还要开一个变量,记录数组里面一共有多少位了方便输出

坑点:

pow返回的是double类型,所以要进行强转,因为 \(3^1\)\(^5\) 非常大,使用long long,所以 与它进行计算的 \(x\) 也必须是long long类型

答案有可能变成1点几,例如当输入为 0.898 时,网上很多人都没有注意到这一点,为此我们从数组的第一位开始,第0位专门留着防止进位变1

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. using namespace std;
  5. typedef long long ll;
  6. int digit[50];
  7. int main() {
  8. string a;
  9. cin >> a;
  10. int t = 0;
  11. for (int i = 2; i <= a.size() - 1; i++) {
  12. ll x = a[i] - '0';
  13. int j = 0;
  14. while (x) {
  15. x *= 10;
  16. digit[++j] += x / (ll)pow(8, i - 1);
  17. int k = j;
  18. while (digit[k] >= 10) {
  19. digit[k] -= 10;
  20. digit[--k]++;
  21. }
  22. x %= (ll)pow(8, i - 1);
  23. }
  24. t = max(t, j);
  25. }
  26. cout << a << " [8] = " << digit[0] << '.';
  27. for (int i = 1; i <= t; i++) cout << digit[i];
  28. cout << " [10]";
  29. return 0;
  30. }

棋盘放米

首先我们分析一下题目是什么意思,相信大家在上幂这一课,老师都讲过这个故事

第一个格子有 \(2^0\) 粒米,第二个格子有 \(2^1\) 粒米,……

我们在这里直接从1开始,不然全是0,第20个格子就遍历19次

注意这题的说法略微有些歧义,从第 \(n\) 个到第 \(m\) 个,应该第一次从 1 遍历到 \(n-1\) 第二次从 1 遍历到 \(m\),然后将两次结果一减就行了,注意也要使用高精

接下来就是三位一撇的问题了,我是先将正序的结果存储下来,然后再根据位数对3进行取模,注意最后一位不要有逗号

  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> mul(vector<int>& A,int B)
  6. {
  7. int t=0;
  8. vector<int> C;
  9. for(int i=0;i<A.size();i++)
  10. {
  11. t+=A[i]*B;
  12. C.push_back(t%10);
  13. t/=10;
  14. }
  15. while(t)
  16. {
  17. C.push_back(t%10);
  18. t/=10;
  19. }
  20. return C;
  21. }
  22. vector<int> sub(vector<int>& A,vector<int>& B)
  23. {
  24. int t=0;
  25. vector<int> C;
  26. for(int i=0;i<A.size();i++)
  27. {
  28. t=A[i]-t;
  29. if(i<B.size()) t-=B[i];
  30. C.push_back((t+10)%10);
  31. if(t<0) t=1;
  32. else t=0;
  33. }
  34. while(C.size()>1&&C.back()==0) C.pop_back();
  35. return C;
  36. }
  37. int main()
  38. {
  39. int n,m;
  40. cin>>n>>m;
  41. vector<int> C,D,E,F;
  42. C.push_back(1); D.push_back(1);
  43. for(int i=1;i<n;i++) C=mul(C,2);
  44. for(int i=1;i<=m;i++) D=mul(D,2);
  45. E=sub(D,C);
  46. for(int i=E.size()-1;i>=0;i--) F.push_back(E[i]);
  47. int cnt=0;
  48. if(E.size()%3==0) cnt=3;
  49. else cnt=E.size()%3;
  50. for(int i=0;i<F.size();i++)
  51. {
  52. cout<<F[i];
  53. if(i==cnt-1&&i!=F.size()-1) cout<<',',cnt+=3;
  54. }
  55. return 0;
  56. }

n的阶乘

我们可以发现这题就是高精度乘低精度
我们直接将上一次得到的结果再乘当前的数就行了

  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> mul(vector<int>& A,int B)
  6. {
  7. int t=0;
  8. vector<int> C;
  9. for(int i=0;i<A.size();i++)
  10. {
  11. t+=A[i]*B;
  12. C.push_back(t%10);
  13. t/=10;
  14. }
  15. while(t)
  16. {
  17. C.push_back(t%10);
  18. t/=10;
  19. }
  20. return C;
  21. }
  22. int main()
  23. {
  24. int B;
  25. cin>>B;
  26. vector<int> A; A.push_back(1);
  27. for(int i=B;i>=1;i--) A=mul(A,i);
  28. for(int i=A.size()-1;i>=0;i--) cout<<A[i];
  29. }

原文链接:https://www.cnblogs.com/xiaozhu0602/p/17632356.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号