- 前言
- 一、什么是大数运算?
- 二、实现思想——**模拟手算**
- 1.乘法
- 2.除法
- 三、代码实现
- 1.乘法函数
- 2.除法函数
- 3.主函数
- 四、实际效果
- 总结
前言
使用C语言实现大数相乘。
一、什么是大数运算?二、实现思想——模拟手算大数运算,顾名思义,就是对很大的数进行一系列的运算。在数学中,数值的大小是没有上限的,但是在计算机中,由于字长的限制,计算机所能表示的范围有限,对于很大的数,计算机无法对其进行直接计算,需要用到所谓的高精度算法,即用数组来存储整数,并模拟手算的方法进行四则运算。
1.乘法前提:我们无法直接以整数形式存储非常大的运算数,因为数据类型有字节大小的限制。因此我们使用字符串来存储大数,字符串中的每一个元素都是大数的一个位数。字符串的元素个数可以无限多,故能非常方便地存储大数。
2.除法乘法:在手算中,我们使用竖式计算法。即将一个运算数的每一位(自小位到大位)与另一个运算数的所有位相乘,并将结果累加。因此我们可以模拟进行运算:
第一步:将两个字符串中的每一个元素转化为整数并逆序存储(即个位数放在数组的第一个元素中)在整数数组中(假设数组a,b);
第二步:创建一个积数组(sum),该数组长度最大是上述数组a与b长度的乘积,注意一定要把该数组初始化为0!!!
第三步:用a数组的每一位元素乘以b数组的所有元素(假设a数组下标从i=0开始,b数组下标从j=0开始),将结果存入sum【i+j】中;
第四步:对积数组(sum)进行整理,从低位到高位,逢十进一
三、代码实现 1.乘法函数除法:在手算中,我们使用的也是竖式计算,即先取被除数的前n位数字(n是除数的位数)与除数进行除法,如果该数大于除数则进行除法,余数和被除数的剩余位数合并,重复上述操作;如果该数小于除数,则扩大这个数,即取被除数的前n+1位数字,再重复上述操作。
简而言之:使用减法,但是进行优化,被除数前n位数字与除数的减法次数,要乘以10的m-n次方,才能正确表示商。(m是被除数的位数)
第一步:将被除数与除数用字符串存储;
第二步:判断被除数与除数的大小关系。如果被除数小,直接输出商为0,余数是被除数;如果被除数不小于除数,则进行下述操作;
第三步:创建循环。如果被除数不小于除数,则将被除数的前n位数字(n是除数的位数)创建位字符串tem,并将tem与除数比较大小。如果tem大于除数,则用tem中的每一位减去除数的每一位,如果结果为负数要进行借位,循环执行,并记录减法的次数;如果tem小于除数,则扩大tem,即将被除数的前n+1位创建为字符串tem,再将tem与除数进行循环减法;
第四步:被扩大后的tem在循环减法时,有两种先后状态。1.tem位数比除数多一位;2.tem位数与除数一样多注意两种情况代码处理不同,请仔细观察!
代码如下:
void Multiply(int n1[], int n2[], int sum[], int m, int n) { int i = 0, j = 0; //将n1的每一位依次与n2的所有位相乘 //结果累加后存入sum中 for (i = 0; i < m; i++) { //积的最大长度为m+n for (j = 0; j < n; j++) { sum[i + j] += n1[i] * n2[j]; } } //对sum的每一位进行逢10进1 for (i = 0; i < m + n; i++) { if (sum[i] > 9) { sum[i + 1] += sum[i] / 10; sum[i] %= 10; } } //记录最后一个非零位 int flag = m + n; while (sum[flag] == 0) { flag--; } if (flag == 0) { printf("0"); } else { //输出结果 printf("积为:"); for (i = flag; i >= 0; i--) { printf("%d", sum[i]); } } }2.除法函数
代码如下:
void Divide(char s1[],char s2[]) { //获得两个数的位数 int m = strlen(s1); int n = strlen(s2); //被除数小于除数 if (m3.主函数printf("商:0 余数:%s",s1); return; } //被除数大于除数 else { int m = strlen(s1); int n = strlen(s2); int sum[Max] = {0}; int count = 0; char tem[Max] = { 0 }; //被除数不小于除数 while (((strcmp(s1, s2) != -1) && m == n)||m>n) { count = 0; int i = 0, j = 0; //从被除数的第一个非零位起,将后面n个位存入tem中 for (i=0;i tem[i] = s1[i]; } //如果相同位数的tem不小于s2就执行减法 if (strcmp(tem, s2) != -1) { //用tem去循环减去除数s2 while (strcmp(tem, s2) != -1) { for (i = n-1; i >=0; i--) { tem[i] = tem[i] - s2[i] + '0'; if (tem[i] < '0') { tem[i] += 10; tem[i - 1] -= 1; } //记录减了多少次 } count++; } //将s1的前n位赋值为tem for (i = 0; i < n; i++) { s1[i] = tem[i]; } //将减的次数存放 sum[m - n] += count; } //相同位数的tem小于s2,就扩大tem else { //tem位数比s2多一位 tem[n] = s1[n]; //用tem去循环减去除数s2 int l1 = strlen(tem); while (((strcmp(tem, s2) != -1) && l1 == n) || l1 > n) { //tem比s2多一位 if (l1==n+1) { for (i = l1 - 1, j = n - 1; j >= 0; i--, j--) { tem[i] = tem[i] - s2[j] + '0'; if (tem[i] < '0') { tem[i] += 10; tem[i - 1] -= 1; } //记录减了多少次 } count++; if (tem[0] == '0') { for (i = 1; i < n + 1; i++) { tem[i - 1] = tem[i]; } tem[n] = ' '; } } //tem与s2位数相同 else if(l1==n) { for (i = n - 1; i >= 0; i--) { tem[i] = tem[i] - s2[i] + '0'; if (tem[i] < '0') { tem[i] += 10; tem[i - 1] -= 1; } } //记录减了多少次 count++; } l1 = strlen(tem); } //将s1的前n+1位赋值为tem s1[0] = '0'; for (i = 1; i < n+1; i++) { s1[i] = tem[i-1]; } //将减的次数存放 sum[m - n-1] += count; } //整理s1,去掉字符串前面的0 //找到第一个非零位 i = 0; while (s1[i] == '0') { i++; } //将s1数组前移i个单位 for (j = i; j < m; j++) { s1[j - i] = s1[j]; } //将数组后i个元素赋值为 for (j = m - i; j < m; j++) { s1[j] = 0; } //记录当前s1的位数 m = strlen(s1); } //sum就是商,s1就是余数 printf("商:"); int flag = Max-1; int i = 0; while (sum[flag] == 0) { flag--; } for (i = flag; i >= 0; i--) { printf("%d", sum[i]); } printf("n余数:"); if (s1[0] != 0) { printf("%s", s1); } else { printf("0"); } } }
代码如下:
int main() { char s1[Max], s2[Max]; //注意创建积数组时,要把数组初始化为0 int n1[Max], n2[Max], sum[Max * Max]={0}; //以字符串形式输入两个大数 printf("请输入两个大数:n"); while (1) { scanf("%s %s", s1, s2); if (s1[0] != '0' && s2[0] != '0') break; else { printf("大数不可以0开头,请重新输入两个大数:"); } } //获得两个字符串的长度 int m = strlen(s1); int n = strlen(s2); //将字符串的每一位转化为整数逆序存储 int i = 0, j = 0; for (i = 0; i < m; i++) { n1[i] = s1[m - i - 1] - '0'; } for (j = 0; j < n; j++) { n2[j] = s2[n - j - 1] - '0'; } printf("请选择:1.乘法 2.除法n"); int input = 0; scanf("%d", &input); if (input == 1) { Multiply(n1, n2, sum, m, n); } else if (input == 2) { Divide(s1,s2); } return 0; }四、实际效果 总结
实现大数除法时,杂糅地实现了大数减法,因此使得代码十分臃肿。
该代码可以先实现大数减法功能函数,再来实现大数除法。这样就可以简化大数除法,美化观感。