|
****使用高精度算法的理由**** 在C/C++中常用的数据类型有int和long long.int占用一个机器字长,在32位系统中int占4个字节,范围为[-2-31,231-1];long long占用8个字节,范围为[-263,263-1].一旦超过这两种数据类型的范围则不能够满足特定数据要求.比如数据2100数量级不能够满足要求,这一类型因此被称为高精度或大数类型.高精度有加减乘除类型. ****高精度加法**** 求解A+B：（1）输入两个正数a,b,输出和（a,b≤109）;（2）输入两个正数a,b,输出和（a,b≤10500） 如下图（左）所示,算法核心为红色笔记部分,既要实现a[i]与b[i]的相加,又要实现进位和本位的输出考虑.在程序考虑时,如果输入数为1234和827这组数据,如下图（右）将1234的1认为数组的第0位,827的8认为数组的第0位,则会导致相加错误,正确的操作应如图中紫色部分所示,对数据进行转置，将1234中的第0位认为是4,827中的第0位认为是7.
具体代码如下： 1 #include <bits/stdc++.h>
2 using namespace std;
3 //采用数组模拟高精度类型
4 char s1[505],s2[505];
5 int a[505],b[505],c[505];
6
7 int main(void)
8 {
9 int la,lb,lc;
10 memset(c,0,sizeof(c));
11 scanf("%s",s1); //输入字符s1
12 scanf("%s",s2); //输入字符s2
13
14 la = strlen(s1);
15 lb = strlen(s2);
16
17 //将字符转换为数字并且转置
18 for(int i = 0; i < la; i++)
19 a[la-i] = s1[i] - '0';
20 for(int i = 0; i < lb; i++)
21 b[lb-i] = s2[i] - '0';
22
23 lc = max(la,lb) + 1;
24 for(int i = 1; i <= lc; i++)
25 {
26 c[i] += a[i] + b[i];
27 c[i+1] = c[i] / 10;
28 c[i] = c[i] % 10;
29 }
30
31 if(c[lc] == 0 && lc > 0)
32 //删除前导0,lc>0是防止0+0=0的情况
33 lc--;
34 for(int i = lc; i > 0; i--)
35 printf("%d",c[i]);
36
37 return 0;
38 }
39
****高精度减法**** 求解A-B，需要注意：（1）如果a<b，则需要交换a与b;（2）如果a[i]<b[i]，需要高位借1当10使用. 具体代码如下： 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 char s1[10090],s2[10090],s3[10090];
5 int a[10090],b[10090],c[10090];
6 int flag = 0;
7 bool compare(char s1[],char s2[])
8 {
9 //如果s1>=s2返回T,否则返回F.
10 int u = strlen(s1),v = strlen(s2);
11 if (u != v) return u > v;
12 //u>v返回T,u<v返回F
13 //u=v时进行比较
14 for(int i = 0; i < u; i++)
15 if(s1[i] != s2[i])
16 return s1[i] > s2[i];
17 return true;
18 }
19
20 int main(void)
21 {
22 int la,lb,lc;
23 scanf("%s",s1);
24 scanf("%s",s2);
25
26 if(!compare(s1,s2))
27 {
28 //如果s1<s2则交换,利用复制方式
29 flag = 1;
30 strcpy(s3,s1);
31 strcpy(s1,s2);
32 strcpy(s2,s3);
33 }
34
35 la = strlen(s1);
36 lb = strlen(s2);
37 lc = max(la,lb);
38
39 //字符转数字并转置
40 for(int i = 0; i < la; i++)
41 a[la-i] = s1[i] - '0';
42 for(int i = 0; i < lb; i++)
43 b[lb-i] = s2[i] - '0';
44
45 for(int i = 1; i<= lc; i++)
46 {
47 //如果a[i]<b[i]则借位
48 if(a[i] < b[i])
49 {
50 a[i+1]--;
51 a[i] += 10;
52 }
53 c[i] = a[i] - b[i];
54 }
55
56 while(c[lc] == 0 && lc > 1) lc--;
57 if(flag == 1) printf("-");
58 //如果是负数先输出负号
59 for(int i = lc; i > 0; i--)
60 printf("%d",c[i]);
61 return 0;
62 }
****高精度乘法**** 题目：求两个不超过200位的非负整数的积. 求解a*b,如下图所示为a4a3a2a1 * b2b1的计算过程,可见c1=a1*b1,c2=a2*b1+a1*b2,c3=a3*b1+a2*b2,c4=a4*b1+a3*b2，c5=a4*b2,经过分析可以得到图中紫色部分结论，ai*bj对应位为c_{i+j-1}.乘法运算同样需要满足加法高精度中的规则.
具体代码如下： 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 char s1[2005],s2[2005];
5 int a[2005],b[205],c[2005];
6
7 int main(void)
8 {
9 int la,lb,lc;
10 scanf("%s",s1);
11 scanf("%s",s2);
12
13 la = strlen(s1);
14 lb = strlen(s2);
15 lc = la + lb;
16
17 for(int i = 0; i < la; i++)
18 a[la-i] = s1[i] - '0';
19 for(int i = 0; i < lb; i++)
20 b[lb-i] = s2[i] - '0';
21
22 for(int i = 1; i <= la; i++)
23 {
24 for(int j = 1; j <= lb; j++)
25 {
26 c[i+j-1] += a[i]*b[j];
27 c[i+j] = c[i+j-1] / 10;
28 c[i+j-1] %= 10;
29 }
30 }
31
32 if(c[lc] == 0 && lc > 0) lc --;
33 for(int i = lc; i > 0; i--)
34 printf("%d",c[i]);
35
36 return 0;
37 }
****高精度除法**** 题目1：https://www./problem/P1480 题目2：http://ybt.:8088/problem_show.php?pid=1308 A/B需要考虑高精度/高精度和高精度/低精度两种情况,高精度除以低精度采用逐位试商法;高精度除以高精度采用减法模拟除法. 如下图所示，针对题目1的a÷b，a为大数（高精度，数组模拟），b为小数（long long类型）
题目1中的代码具体如下： 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 char s1[5005];
5 long long b,c[5005],a[5005],la,lc;
6
7 int main(void)
8 {
9 long long x = 0;
10 scanf("%s",s1);//被除数
11 scanf("%d",&b);//除数
12
13 la = strlen(s1);
14 //区别于其他加减乘操作
15 //将如输入的1234字符依次按顺序
16 //放入a数组中
17 for(int i = 1; i<=la; i++)
18 a[i] = s1[i-1] -'0';
19
20 for(int i = 1; i <= la; ++i)
21 //商最多有la位
22 {
23 c[i] = (x * 10 + a[i]) / b;
24 x = (x * 10 + a[i]) % b;
25 }
26
27 //删除前导零
28 lc = 1;
29 while(c[lc] == 0 && lc < la)
30 lc++;
31
32 for(int i = lc; i <= la; ++i)
33 printf("%d",c[i]);
34
35 return 0;
36 }
下面对高精度除以高精度的情况进行分析，举个案例解释，如531518/123的案例，531518为高精度被除数，123设为很大的高精度除数，这时可以采用下图的①-④步骤进行处理，即将531518和填补至相同位数的123000进行减法处理，经过四次减法后得到的数的位数要比原来531518的位数即6位小，因此4作为商的最高位。次高位等位的处理如后续②③④同理可得。
531518÷123=4321.....35
其中c的位数为la-lb+1，上述案例中c的位数至多有4位设为c1c2c3c4（c4为高位）.
上述过程可以用下列伪代码进行表示：
//高位c[4]的来源
a = 531518;
tmp = 123000;（将123左移3位）
while a >= tmp:
c[4]++;
a = a - tmp;（需要用到高精度减法）
//c[3]的来源
a=39518;
tmp=12300;（将123左移两位）
while a >= tmp:
c[3]++;
a = a - tmp;（需要用到高精度减法）
//c[2]的来源
a=2618;
tmp=1230;（将123左移1位）
while a >= tmp:
c[2]++;
a = a - tmp;（需要用到高精度减法）
//c[1]的来源
a=158;
tmp=123;（将123左移0位）
while a >= tmp:
c[1]++;
a = a - tmp;（需要用到高精度减法）
//上述结构可以用以下循环表示：
a = 531518;
for(i=lc;i>=1;i--)
{
tmp=0；
tmp=123 左移 i-1位；
while a >= tmp:
c[i]++;
a = a - tmp;（需要用到高精度减法）
}
最终代码如下： 1 //高精度除以高精度求它们的商和余数
2 //输入两个低于300位的正整数
3
4 #include <bits/stdc++.h>
5 using namespace std;
6
7 char s1[305],s2[305];
8 int a[305],b[305],c[305],tmp[305];
9
10 void init(int *x)
11 {
12 char s[305];
13 scanf("%s",s);
14 x[0] = strlen(s);
15 for(int i = 0; i < x[0]; i++)
16 x[x[0]-i] = s[i] - '0';
17 //字符转为数字并且倒序存储
18 }
19
20 //输出 数组第0位存储长度
21 void print(int a[])
22 {
23 if(a[0] == 0)
24 {
25 printf("0");
26 return;
27 }
28 for(int i = a[0]; i > 0; i--)
29 printf("%d",a[i]);
30 return;
31 }
32
33 //比较大小
34 int compare(int a[],int b[])
35 {
36 if(a[0] > b[0])
37 return 1;
38 if(a[0] < b[0])
39 return -1;
40 for(int i = a[0]; i > 0; i--)
41 {
42 if(a[i] > b[i])
43 return 1;
44 if(a[i] < b[i])
45 return -1;
46 }
47 return 0;
48 }
49
50 //减法处理
51 void minu(int a[],int b[])
52 {
53 for(int i = 1; i <= a[0]; i++)
54 {
55 if(a[i] < b[i])
56 {
57 a[i+1]--;
58 a[i] = a[i] + 10;
59 }
60 a[i] = a[i] - b[i];
61 }
62 while(a[a[0]] == 0 && a[0] > 0)
63 a[0]--;
64 }
65
66 //将p数组移动n位至q数组
67 void numcpy(int p[],int q[],int n)
68 {
69 for(int i = 1; i <= p[0];i++)
70 q[i+n-1] = p[i];
71 q[0] = p[0] + n - 1;
72 }
73
74
75 int main(void)
76 {
77 init(a);
78 init(b);
79 c[0] = a[0] - b[0] + 1;
80
81 //代码的核心
82 for(int i = c[0]; i >= 1; i--)
83 {
84 memset(tmp,0,sizeof(tmp));
85 numcpy(b,tmp,i);
86 while(compare(a,tmp) >= 0)
87 {
88 c[i]++;
89 minu(a,tmp);
90 }
91 }
92
93 while(c[c[0]] ==0 && c[0] > 0)
94 c[0]--;
95 print(c);//商
96 printf("\n");
97 print(a);//最后的a为余数
98 return 0;
99 }
****参考文献**** [1] 麦克老师讲算法-高精度算法全套（加减乘除，全网最详细）https://www.bilibili.com/video/BV1LA411v7mt?p=5
|
|
|
