大数相乘问题
发布时间:2020-12-14 02:20:21 所属栏目:大数据 来源:网络整理
导读:算法题-大数相乘问题 今天在网上看到一个大数相乘的问题,题目是这样的:输入两个整数,要求输出这两个数的乘积。输入的数字可能超过计算机内整形数据的存储范围。 分析: 由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字。然后按照乘
算法题-大数相乘问题 今天在网上看到一个大数相乘的问题,题目是这样的:输入两个整数,要求输出这两个数的乘积。输入的数字可能超过计算机内整形数据的存储范围。 分析: 由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字。然后按照乘法的运算规则,用一个乘数的每一位乘以另一个乘数,然后将所有中间结果按正确位置相加得到最终结果。可以分析得出如果乘数为A和B,A的位数为m,B的位数为n,则乘积结果为m+n-1位(最高位无进位)或m+n位(最高位有进位)。因此可以分配一个m+n的辅存来存储最终结果。为了节约空间,所有的中间结果直接在m+n的辅存上进行累加。最后为了更符合我们的乘法运算逻辑,可以讲数字逆序存储,这样数字的低位就在数组的低下标位置,进行累加时确定下标位置较容易些。 下面是我的解法。 首先是对数组逆序的函数: 1 void reverSEOrder(char* str,int p,255)">int q) 2 { 3 char temp; 4 while(p < 5 { 6 temp = str[p]; 7 str[p] = str[q]; 8 str[q] = 9 p ++; 10 q --11 } 12 } 然后是完成大数相乘的函数: char* multiLargeNum(char* A,255)">char* B) int m = strlen(A); int n = strlen(B); 5 char* result = new char[m+n+1]; 6 memset(result,'0',m+n); 7 result[m+n] = |