C++高精度算法—大数加大数，大数乘以小数

103 阅读 0 评论 68 点赞

我是靠谱客的博主含蓄金针菇，这篇文章主要介绍C++高精度算法—大数加大数，大数乘以小数，现在分享给大家，希望可以做个参考。

一次偶然的机会，看到百度面试题中出现了很多关于处理大数据的处理题目，也称作高精度题目，另外在ACM竞赛中也偶尔会碰到。我们知道在C语言或C++语言中，通常受机器字长的限制，我们会碰到如果某个整数的范围超过一个范围就没法运算。这时我们只能先用字符串读进去，然后再将字符型的“数”转换成数值的“数”，再模拟手算，一位一位相加，最后得到结果。

具体请看下面的例子：

复制代码

#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
/*****任务：高精度，计算大数乘以小数
******参数：被乘数a[],乘数b;
******结果存储在a[]中***************/
int Mul(char a[],int b)
{
int i,j,len;
char tmp[1000];
len=strlen(a);
for(i=0;i<len;i++)
tmp[len-i-1]=a[i]-'0';
//将字符数组a转换成整型数组，并逆序记录在tmp中
int c=0,s;
for(j=0;j<len;j++)
//模拟人工手算
{
s=tmp[j]*b+c;
//记录每次相乘的结果(包括进位)
tmp[j]=s%10;
c=s/10;
}
while(c)
//对数据位数修正
{
tmp[len++]=c%10;
c/=10;
}
for(i=0;i<len;i++)
a[i]=tmp[len-1-i]+'0';
//再次逆序并换成字符数组
for(i=0;i<len;i++)
cout<<a[i];
cout<<endl;
return 0;
}
/****高精度：大数加大数模板
*****参数：两个字符数组a[],b[]
*****结果保存在ans[]中*********/
int add(char a[],char b[])
{
int i,j,s,len,c=0;
char ans[10000];
int temp_a[10000],temp_b[10000],temp_ans[10000];
memset(ans,0,sizeof(ans));
memset(temp_a,0,sizeof(temp_a));
memset(temp_b,0,sizeof(temp_b));
memset(temp_ans,0,sizeof(temp_ans));
len=max(strlen(a),strlen(b));
for (i=0;i<strlen(a);i++)
temp_a[strlen(a)-i-1]=a[i]-'0';//字符数组转换为整型数组
for (i=0;i<strlen(b);i++)
temp_b[strlen(b)-i-1]=b[i]-'0';
for(j=0;j<len;j++)
//模拟手算
{
s=temp_a[j]+temp_b[j]+c;
temp_ans[j]=s%10;
c=s/10;
}
if(c) temp_ans[len++]=c;
//数据位数修正
for (i=0;i<len;i++)
//整型数组转字符数组
ans[len-1-i]=temp_ans[i]+'0';
for(int i=0;i<len;i++)
//输出结果
cout<<ans[i];
cout<<endl;
}
int main()
{
char a[1000],b[1000];
int m;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cout<<"模拟大数乘以小数："<<endl;
cin>>a>>m;
Mul(a,m);
cout<<"模拟大数加大数： "<<endl;
cin>>a>>b;
add(a,b);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
/*****任务：高精度，计算大数乘以小数
******参数：被乘数a[],乘数b;
******结果存储在a[]中***************/
int Mul(char a[],int b)
{
int i,j,len;
char tmp[1000];
len=strlen(a);
for(i=0;i<len;i++)
tmp[len-i-1]=a[i]-'0';
//将字符数组a转换成整型数组，并逆序记录在tmp中
int c=0,s;
for(j=0;j<len;j++)
//模拟人工手算
{
s=tmp[j]*b+c;
//记录每次相乘的结果(包括进位)
tmp[j]=s%10;
c=s/10;
}
while(c)
//对数据位数修正
{
tmp[len++]=c%10;
c/=10;
}
for(i=0;i<len;i++)
a[i]=tmp[len-1-i]+'0';
//再次逆序并换成字符数组
for(i=0;i<len;i++)
cout<<a[i];
cout<<endl;
return 0;
}
/****高精度：大数加大数模板
*****参数：两个字符数组a[],b[]
*****结果保存在ans[]中*********/
int add(char a[],char b[])
{
int i,j,s,len,c=0;
char ans[10000];
int temp_a[10000],temp_b[10000],temp_ans[10000];
memset(ans,0,sizeof(ans));
memset(temp_a,0,sizeof(temp_a));
memset(temp_b,0,sizeof(temp_b));
memset(temp_ans,0,sizeof(temp_ans));
len=max(strlen(a),strlen(b));
for (i=0;i<strlen(a);i++)
temp_a[strlen(a)-i-1]=a[i]-'0';//字符数组转换为整型数组
for (i=0;i<strlen(b);i++)
temp_b[strlen(b)-i-1]=b[i]-'0';
for(j=0;j<len;j++)
//模拟手算
{
s=temp_a[j]+temp_b[j]+c;
temp_ans[j]=s%10;
c=s/10;
}
if(c) temp_ans[len++]=c;
//数据位数修正
for (i=0;i<len;i++)
//整型数组转字符数组
ans[len-1-i]=temp_ans[i]+'0';
for(int i=0;i<len;i++)
//输出结果
cout<<ans[i];
cout<<endl;
}
int main()
{
char a[1000],b[1000];
int m;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cout<<"模拟大数乘以小数："<<endl;
cin>>a>>m;
Mul(a,m);
cout<<"模拟大数加大数： "<<endl;
cin>>a>>b;
add(a,b);
return 0;
}