高精加和高精乘
仅正整数
高精度加法
实现思路
核心：模拟笔算
即用数组里的每个元素来作为笔算加法竖式的每一位
为规范化以及移植性，输入输出均为string
步骤：
- 将字符串存入数组a和b
- 另外定义两个数组s和c，分别存储每一位的结果值和进位值
- c[0]的值为0，s[i]的值是(a[i]+b[i]+c[i])%10，c[i]的值是(a[i]+b[i]+c[i])/10，以此类推，完成所有位数的相加
- 将数组元素存入新定义的string中
注意事项：
- 对数组int a[10]的理解：包含a[0]，a[1]，a[2]，…，a[9]共10个元素
- string类：按顺序往里填入元素时（步骤4），用
str+ = '单个元素'，表示结束时如果用赋值的方法（比如str[2] = '\0';），可能引起后续对该字符串的操作出错
- 输出string类：调用函数
cout<<sum.c_str()<<endl;（因为不能直接输出）（可以试试）
代码如下：
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
| #include<iostream>
using namespace std;
int getN(string a)
{
int n=0;
while(a[n]!='\0')n++;
return n;
}
int main()
{
string a,b;
cin>>a>>b;
int an=getN(a);
int bn=getN(b);
int N=an;
if(an<bn)N=bn;
int aa[N]={0};
for(int i=0;i<an;i++)aa[i]=a[an-1-i]-'0';
int bb[N]={0};
for(int i=0;i<bn;i++)bb[i]=b[bn-1-i]-'0';
int s[N+1],c[N+1];
c[0]=0;
for(int i=0;i<N;i++)
{
s[i]=(aa[i]+bb[i]+c[i])%10;
c[i+1]=(aa[i]+bb[i]+c[i])/10;
}
s[N]=c[N];
string sum;
if(s[N]==0)
{
for(int i=0;i<N;i++)
sum+=s[N-1-i]+'0';
}
else
{
for(int i=0;i<=N;i++)
sum+=s[N-i]+'0';
}
cout<<sum.c_str()<<endl;
system("pause");
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
| #include<bits/stdc++.h>
using namespace std;
int getN(string a)
{
int n=0;
while(a[n]!='\0')n++;
return n;
}
int main()
{
int a;
string b;
cin>>a>>b;
int n=getN(b);
int bb[n];
for(int i=0;i<n;i++)
bb[i]=b[n-1-i]-'0';
int c[n+1]={0};
int s[n+1]={0};
for(int i=0;i<n;i++)
{
s[i]=(a*bb[i]+c[i])%10;
c[i+1]=(a*bb[i]+c[i])/10;
}
s[n]=c[n];
string r;
if(s[n]==0)
{
for(int i=0;i<n;i++)
r+=s[n-1-i]+'0';
}
else
{
for(int i=0;i<=n;i++)
r+=s[n-i]+'0';
}
cout<<r.c_str()<<endl;
}
|
多位数乘多位数
代码如下：
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
90
91
92
93
94
| #include<bits/stdc++.h>
using namespace std;
int getN(string a)
{
int n=0;
while(a[n]!='\0')n++;
return n;
}
string add(string a,string b)
{
int an=getN(a);
int bn=getN(b);
int N=an;
if(an<bn)N=bn;
int aa[N]={0};
for(int i=0;i<an;i++)
aa[i]=a[an-1-i]-'0';
int bb[N]={0};
for(int i=0;i<bn;i++)
bb[i]=b[bn-1-i]-'0';
int s[N+1],c[N+1];
c[0]=0;
for(int i=0;i<N;i++)
{
s[i]=(aa[i]+bb[i]+c[i])%10;
c[i+1]=(aa[i]+bb[i]+c[i])/10;
}
s[N]=c[N];
string sum;
if(s[N]==0)
{
for(int i=0;i<N;i++)
sum+=s[N-1-i]+'0';
}
else
{
for(int i=0;i<=N;i++)
sum+=s[N-i]+'0';
}
return sum;
}
string multi_1(int a,string b)
{
int n=getN(b);
int bb[n];
for(int i=0;i<n;i++)
bb[i]=b[n-1-i]-'0';
int c[n+1]={0};
int s[n+1]={0};
for(int i=0;i<n;i++)
{
s[i]=(a*bb[i]+c[i])%10;
c[i+1]=(a*bb[i]+c[i])/10;
}
s[n]=c[n];
string r;
if(s[n]==0)
{
for(int i=0;i<n;i++)
r+=s[n-1-i]+'0';
}
else
{
for(int i=0;i<=n;i++)
r+=s[n-i]+'0';
}
return r;
}
string add_0(int a,string b)
{
for(int i=0;i<a;i++)
{
b+="0";
}
return b;
}
int main()
{
string a,b;
cin>>a>>b;
int an=getN(a);
int aa[an];
for(int i=0;i<an;i++)
aa[i]=a[an-1-i]-'0';
string c="0";
for(int i=0;i<an;i++)
c=add(add_0(i,multi_1(aa[i],b)),c);
cout<<c.c_str()<<endl;
}
|
总结
核心思想是模拟竖式计算
注意string类的用法
PS: 其实这一篇博客还是为了测试