高精度计算
由于创建的变量存在空间大小的限制，若数字的位数过大，可能无法进行计算，甚至无法创建相应变量。
因此借助数组将数字的每一位单独储存，并以小学所学的竖式计算为原理进行运算。最后的结果也以数组进行储存。
输入
输入的时候,要倒序储存，以便进位。
同时用数组的第一位来储存该数的位数，便于随时调用。
1
2
3
4
5
6
7
8
|
void init(int a[])
{
string s;
cin>>s;
a[0] = s.length();
for (int i=1; i<=a[0]; i++)
a[i] = s[a[0]-i] - 48;
}
|
输出
注意倒序输出
1
2
3
4
5
6
|
void print(int a[])
{
for (int i=a[0]; i>0; i--)
printf("%d",a[i]);
cout<<endl;
}
|
加法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void add(int a[],int b[])
{
int i=1,x=0; //i为当前计算的位数，x为向下一位的进位
while (i<=len1 || i<=len2) //len为两个数字的位数，要满足两者的每一位均进入计算过程
{
c[i]=a[i]+b[i]+x;
x=c[i]/10; //处理进位
c[i]%=10;
i++;
}
if (x == 0) //最高位特判
{
len3=i-1;
return;
}
c[i]=x;
len3=i;
}
|
减法
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
|
void minuss(char S1[],char S2[])
{
char S3[num];
if (strlen(S1)<strlen(S2) || (strlen(S1) == strlen(S2) && strcmp(S1,S2)<0)) //strcmp()用于比较字符串大小，原理为将两个字符串同位上的字符进行ASCLL码相减，若为0则将下一位相减，结果不为0时返回相减所得值，若字符串相等则返回0.
{
strcpy(S3,S1); //strcpy()将函数中的后一个数组的值完全赋值给前一个数组
strcpy(S1,S2);
strcpy(S2,S3);
cout<<"-";
}
len1=strlen(S1);
len2=strlen(S2);
for (int i=0;i<=len1-1;i++) //逆序存入int数组,便于计算
a[len1-i]=int(S1[i]-48); //S1的指针从0开始,a的指针从1开始
for (int i=0;i<=len2-1;i++)
b[len2-i]=int(S2[i]-48);
int w=1;
while (w<=len1 || w<=len2)
{
if (a[w]<b[w]) //不够减的话向高位借1
{
a[w]+=10;
a[w+1]--;
}
ans[w]=a[w]-b[w];
w++;
}
lena=w;
while ((ans[lena] == 0) && lena > 1) lena--;
for (int i=lena;i>=1;i--) //注意倒序输出最后是i--
printf("%d",ans[i]);
return;
}
|
乘法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void chen(int a1[],int a2[])
{
for (int i=1;i<=len1;i++)
{
int jw=0; //处理进位
for (int j=1;j<=len2;j++)
{
ans[i+j-1]=ans[i+j-1]+a1[i]*a2[j]+jw; //例如6*6=36中，第一步是确定个位上的6，再将3进位
jw=ans[i+j-1]/10;
ans[i+j-1]%=10; //注意每一位上的数字要小于10
}
ans[i+len2]+=jw;
}
ans[0]=len1+len2; //多位数乘多位数，结果的位数不会超过两数位数之和
while (ans[0] >= 1 && ans[ans[0]] == 0) ans[0]--; //日常抹零
}
|
高精除以低精
1
2
3
4
5
6
7
8
9
10
11
12
|
void dichu(int a[],int b)
{
int x=0;
for (int i=1; i<=a[0]; i++)
{
ans[i] = (x * 10 + a[i]) / b;
x = (x * 10 + a[i]) % b;
}
int ans[0] = 1;
while (ans[ans[0]] == 0 && ans[0] <= lens)
ans[0]++;
}
|
高精除以高精
重中之重，并且是难点。
cop函数用于比较两个高精度数据的大小。
jian函数是正常的高精度减法。
gc函数是主体函数，主要思想是以减法来模拟除法，从而实现计算。
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
|
int cop(int a[],int b[])
{
if (a[0] < b[0]) return -1;
else if (a[0] > b[0]) return 1;
else
{
for (int i=a[0]; i>0; i--)
{
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
}
return 0;
}
}
void jian(int a[],int b[])
{
int flag;
flag = cop(a,b);
if (flag == 0)
{
a[0] = 0;
return;
}
else if (flag == 1)
{
for (int i=1; i<=b[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 gc(int a[],int b[],int c[])
{
if (cop(a,b) == -1)
{
printf("0\n");
print(a);
}
else
{
int tmp[num];
c[0] = a[0] - b[0] + 1;
for (int i=c[0]; i>0; i--)
{
memset(tmp,0,sizeof(tmp));
for (int j=1; j<=b[0]; j++)
tmp[i+j-1] = b[j];
tmp[0] = b[0] + i - 1;
while (cop(a,tmp) != -1)
{
c[i]++;
jian(a,tmp);
}
}
while (c[0] > 0 && c[c[0]] == 0) c[0]--;
}
return;
}
|