C++算法之高精度计算
利用计算机进行计算时，有时会遇到计算精度不够的问题。但是我们可以利用程序实现高精度计算，本文介绍几种常用的高精度计算方法。
·
利用计算机进行计算时，有时会遇到计算精度不够的问题。但是我们可以利用程序实现高精度计算，以下介绍几种常用的高精度计算方法。
目录
1.要处理的问题
1.1 数据的接收和存储
可以采用整型数组顺位存储，即整数高位存储在数组高位：
void st(int a[]) // 传入数组
{
string b;
cin >> b;
int len = b.length(); //用len计算字符串位数
for(int i = 1; i <= len; i++)
a[i] = b[len - i] - '0'; //将字符串s转换为数组a, 并倒序存储
}1.2 进位和借位
1.2.1 加法进位
c[i] = a[i] + b[i]
if(c[i] >= 10) {
c[i] %= 10;
++c[i++];
}1.2.2 减法借位
if(a[i] < b[i]) {
--a[i+1];
a[i] += 10;
}
c[i] = a[i] - b[i]1.2.3 乘法进位
c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
x = c[i + j - 1] / 10;
c[i + j - 1] % 10;2.高精度运算
2.1 高精度加法
输入两个数到变量中，然后用赋值语句求它们的和后输出。但是，当两个加数很大时，以前的算法不能求出精确解，因此我们需要寻求另一种方法 。在小学时，我们做加法都采用竖式。 这样我们方便写出两个整数相加的算法。
8 5 6
+ 2 5 5 +
———— —————
1 1 1 1
如果我们用数组a、b分别储存两个加数，用数组 c 储存结果。则上例有 a[1] = 6，a[2] = 5，a[3] = 8，b[1] = 5，b[2] = 5，c[4] = 1，c[3] = 2，c[2] = 1，c[1] = 1。
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
char a1[5005], b1[5005]; //用字符存储数字
int a[5005], b[5005], c[5005]; //c[i] 用来储存每位相加的结果
int len_a, len_b, len_c = 1, x, i;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
scanf("%s%s", a1, b1); //输入两个加数
len_a = strlen(a1);
len_b = strlen(b1);
for(i=0; i<len_a; i++) a[len_a - i] = a1[i] - '0'; // 将加数放进a数组
for(i=0; i<len_b; i++) b[len_b - i] = b1[i] - '0'; // 将另一个加数放进b数组
x = 0; // x为进位
while(len_c <= len_a || len_c <= len_b) {
c[len_c] = a[len_c] + b[len_c] + x; // 两数相加，再加上前两个数进位的
x = c[len_c] / 10; // 刷新进位
c[len_c] %= 10; // 进位后剩下的
len_c++; //位数加1
}
c[len_c] = x;
if(c[len_c] == 0) { //判断首位是否为0
len_c--; // 不输出此位
}
for(int i=len_c; i>=1; i--) {
printf("%d", c[i]); //输出每一位的数
}
return 0;
}2.2 高精度减法
也可以用竖式求减法，注意要处理借位
#include <iostream>
#include <cstring>
int main() {
int a[5005], b[5005], c[5005];
int lena, lenb, lenc, i;
char n[5005], n1[5005], n2[5005];
std::memset(a, 0, sizeof(a));
std::memset(b, 0, sizeof(b));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> n2; //输入被减数和减数
lena = std::strlen(n1);
lenb = std::strlen(n2);
for(i=0; i<lena; i++) a[lena - i] = (int)n1[i] - '0';
for(i=0; i<lenb; i++) b[lenb - i] = (int)n2[i] - '0'; //逆序存放排列
i = 1;
while(i <= lena || i <= lenb) {
if(a[i] < b[i]) {
c[i] = a[i] + 10 - b[i];
a[i+1]--; //借位处理
}
else {
c[i] = a[i] - b[i];
}
i++;
}
lenc = i;
while(c[lenc] == 0 && lenc > 1) { //如果最后一位是0，是需要输出的
lenc--; // 不输出首位0
}
for(i=lenc; i>=1; i--) std::cout << c[i];
return 0;
}2.3 高精度乘法
很像加法，可以使用竖式，同样也有进位。
分析 c 数组下标的变换规律，可以写出这些关系式：
···由此可见，
跟
乘积有关，跟上次的进位有关，跟还原
的值有关，分析下标规律，有 c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];x = c[i + j - 1]/10;c[i + j - 1]% = 10;
8 5 6
× 2 5 ×
————— ————————
4 2 8 0
1 7 1 2
__________ _____________
2 1 4 0 0
#include <iostream>
#include <cstring>
int main() {
int a[105], b[105], c[10005];
char n1[105], n2[105], lena, lenb, lenc, j, i, x;
std::memset(a, 0, sizeof(a));
std::memset(b, 0, sizeof(b));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> n2;
lena = std::strlen(n1);
lenb = std::strlen(n2);
for(i=0; i<=lena-1; i++) a[lena - i] = n1[i] - 48;
for(i=0; i<=lenb-1; i++) b[lenb - i] = n2[i] - 48; // 倒序储存
for(i=1; i<=lena; i++) {
x = 0;
for(j=1; j<=lenb; j++) {
c[i + j - 1] = c[i + j - 1] + x + a[i] * b[j];
x = c[i + j - 1] / 10; // 进位
c[i + j - 1] %= 10; // 剩余
}
c[i + lenb] = x; // 进位的数
}
lenc = lena + lenb;
while(c[lenc] == 0 && lenc > 1) {
lenc--; // 删除前导0
}
for(i=lenc; i>=1; i--) {
std::cout << c[i];
} // 输出每一位
std::cout << std::endl;
return 0;
} 2.4 高精度除法
高精除以高精则使用减法模拟除法，对被除数的每一位都减去除数，一直减到当前位置的数字（包含前面的余数）小于除数。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int a[50005], b[50005], c[50005], d;
void init(int a[]) {
char s[50005];
cin >> s;
a[0] = strlen(s); // 字符串存储，表示位数
for (int i=1; i<=a[0]; i++) {
a[i] = s[a[0]-i] - 48; // 正序储存
}
}
void print(int a[]) {
if (a[0] == 0) {
cout << 0 << endl;
return; // 位数为0，输出0
}
for (int i=a[0]; i>=1; i--) {
cout << a[i]; // 输出函数
}
cout << endl;
return;
}
int compare(int a[], int b[]) {
if (a[0] > b[0]) {
return 1; // 被减数大于减数
}
if (a[0] < b[0]) {
return -1; // 被减数小于减数
}
for (int i=a[0]; i>=1; i--) {
if (a[i] > b[i]) {
return 1;
}
if (a[i] < b[i]) {
return -1;
} // 位数相同，找到第一位不同的进行比较
}
return 0;
}
void numcpy(int p[], int q[], int det) {
for (int i=1; i<=p[0]; i++) {
q[i+det-1] = p[i]; //复制p数组到q数组从det开始的地方
}
q[0] = p[0] + det - 1;
}
void jian(int a[], int b[]) {
int flag = compare(a, b);
if (flag == 0) {
a[0] = 0;
return;
}
if (flag == 1) {
for (int i=1; i<=a[0]; i++) {
if (a[i] < b[i]) {
a[i+1]--;
a[i] += 10;
}
a[i] -= b[i];
}
while (a[0]>0 && a[a[0]]==0) {
a[0]--;
}
return;
}
} // 高精减法
void chugao(int a[], int b[], int c[]) {
int tmp[50005];
c[0] = a[0] - b[0] + 1;
for (int i=c[0]; i>0; i--) {
memset(tmp, 0, sizeof(tmp));
numcpy(b, tmp, i);// 清零
while (compare(a, tmp) >= 0) {
c[i]++;
jian(a, tmp); // 用减法模拟
}
}
while (c[0] > 0 && c[c[0]] == 0) {
c[0]--;
}
return;
}
int main() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
init(a);
init(b);
chugao(a,b,c);
print(c);
return 0;
}2.5 高精度比较
我们可以使用字符数组a,b来进行存储，比较a,b的长度，若长度相等，则从左往右挨个进行比较。
#include<iostream>
#include<algorithm>
using namespace std;
main()
{
string a,b;
while(cin>>a>>b&&a!="0"&&b!="0")
{
bool check=true,same=true;
int xa[1000]={},xb[1000]={};
for(int i=0;i<a.length();i++)
xa[i]=a[a.length()-i-1]-'0';
for(int i=0;i<b.length();i++)
xb[i]=b[b.length()-i-1]-'0';
for(int i=max(a.length(),b.length());i>=0;i--)
{
if(xa[i]!=xb[i]) same=false;
if(xa[i]<xb[i]) {check=false;break;}
if(xa[i]>xb[i]) break;
}
if(same)
cout<<"="<<endl;
else
check?cout<<">"<<endl:cout<<"<"<<endl;
}
}创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，如果喜欢我的文章，给个关注吧！
冰焰狼 | 文
如果本篇博客有任何错误，请批评指教，不胜感激 ！
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
10
0- 0
已为社区贡献2条内容
所有评论(0)