可以知道在处理高精度乘法的时候,我们是不考虑当场进位的,在所有位数都模拟完竖式乘法后才进行逐位进位,这就要求存储每个位的数组保证不会爆掉溢出
众所周知char类型最多只能存储到255,非常非常容易溢出成负数,对于char型数组要考虑每一步乘法都要进位。
而int型数组最大21亿就不用考虑这种问题,当然是在内存允许的前提下
P1045 [NOIP2003 普及组] 麦森数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn),举个例子
这道题要求高精度的乘法,我一开始开的就是char型数组,当输入P较小时尚可,当P超过50时就会爆负数,我真的会谢,找了半天没找到问题,最终发觉应该是char型变量爆了,随后改为int就好了
如图
void Big_Multiple(char A[], char B[], int* lena, int lenb) { char C[1000000]={0}; for (int i = 0; i < *lena; i++) { for (int j = 0; j < lenb; j++) { C[i + j] += A[i] * B[j]; } } int lenc = *lena + lenb - 1; int last = 0; for (int i = 0; i < lenc; i++) { int Temp = C[i] + last; C[i] = Temp % 10; last = Temp / 10; } while (last) { C[lenc++] = last % 10; last /= 10; } for (int i = 0; i < lenc; i++) A[i] = C[i]; *lena = lenc; }
char型数组,结果如下
(算的是2的P次方,用了快速幂),可以看到当P大于30就开始爆负数了
下面是改为int后的
void Big_Multiple(int A[], int B[], int* lena, int lenb) { int C[1000000]={0}; for (int i = 0; i < *lena; i++) { for (int j = 0; j < lenb; j++) { C[i + j] += A[i] * B[j]; } } int lenc = *lena + lenb - 1; int last = 0; for (int i = 0; i < lenc; i++) { int Temp = C[i] + last; C[i] = Temp % 10; last = Temp / 10; } while (last) { C[lenc++] = last % 10; last /= 10; } for (int i = 0; i < lenc; i++) A[i] = C[i]; *lena = lenc; }
可以看到即使P为10000还没爆负数,完美
当然不难发现我们并不需要将所有数组都开成int型,只有一个数组需要为int型那就是高精度乘法时接受加和的那个数组,其他数组为char型即可
void Big_Multiple(char A[], char B[], int* lena, int lenb) { int C[1000000]={0};//就是这个数组需要设为int型,其他数组设为char型即可 for (int i = 0; i < *lena; i++) { for (int j = 0; j < lenb; j++) { C[i + j] += A[i] * B[j]; } } int lenc = *lena + lenb - 1; int last = 0; for (int i = 0; i < lenc; i++) { int Temp = C[i] + last; C[i] = Temp % 10; last = Temp / 10; } while (last) { C[lenc++] = last % 10; last /= 10; } for (int i = 0; i < lenc; i++) A[i] = C[i]; *lena = lenc; }
标签:lenc,10,last,大数,int,char,++ From: https://www.cnblogs.com/WKWKSL/p/17331587.html