大数相乘问题 约定不等于承诺〃 2022-08-05 10:25 157阅读 0赞 [算法题-大数相乘问题][-] 今天在网上看到一个大数相乘的问题,题目是这样的:输入两个整数,要求输出这两个数的乘积。输入的数字可能超过计算机内整形数据的存储范围。 分析: 由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字。然后按照乘法的运算规则,用一个乘数的每一位乘以另一个乘数,然后将所有中间结果按正确位置相加得到最终结果。可以分析得出如果乘数为A和B,A的位数为m,B的位数为n,则乘积结果为m+n-1位(最高位无进位)或m+n位(最高位有进位)。因此可以分配一个m+n的辅存来存储最终结果。为了节约空间,所有的中间结果直接在m+n的辅存上进行累加。最后为了更符合我们的乘法运算逻辑,可以讲数字逆序存储,这样数字的低位就在数组的低下标位置,进行累加时确定下标位置较容易些。 下面是我的解法。 首先是对数组逆序的函数: ![复制代码][copycode.gif] 1 void reverseOrder(char* str, int p, int q) 2 { 3 char temp; 4 while(p < q) 5 { 6 temp = str[p]; 7 str[p] = str[q]; 8 str[q] = temp; 9 p ++; 10 q --; 11 } 12 } ![复制代码][copycode.gif] 然后是完成大数相乘的函数: ![复制代码][copycode.gif] 1 char* multiLargeNum(char* A, char* B) 2 { 3 int m = strlen(A); 4 int n = strlen(B); 5 char* result = new char[m+n+1]; 6 memset(result, '0', m+n); 7 result[m+n] = '\0'; 8 reverseOrder(A, 0, m-1); 9 reverseOrder(B, 0, n-1); 10 11 int multiFlag; // 乘积进位 12 int addFlag; // 加法进位 13 for(int i=0; i <= n-1; i++) // B的每一位 14 { 15 multiFlag = 0; 16 addFlag = 0; 17 for(int j=0; j <= m-1; j++) // A的每一位 18 { 19 // '0' - 48 = 0 20 int temp1 = (A[j] - 48) * (B[i] - 48) + multiFlag; 21 multiFlag = temp1 / 10; 22 temp1 = temp1 % 10; 23 int temp2 = (result[i+j] - 48) + temp1 + addFlag; 24 addFlag = temp2 / 10; 25 result[i+j] = temp2 % 10 + 48; 26 } 27 result[i + m] += multiFlag + addFlag; 28 } 29 reverseOrder(result, 0, m+n-1); // 逆序回来 30 31 return result; 32 } ![复制代码][copycode.gif] 最后是测试程序: ![复制代码][copycode.gif] 1 int main() 2 { 3 char A[] = "962346239843253528686293234124"; 4 char B[] = "93459382645998213649236498"; 5 char *res = multiLargeNum(A, B); 6 if(res[0] != 48) 7 printf("%c", res[0]); 8 printf("%s", res+1); 9 delete [] res; 10 return 0; 11 } ![复制代码][copycode.gif] 时间复杂度分析: 3个逆序操作的时间分别为O(n)、O(m)、O(m+n),双重循环的时间复杂度为O(mn),则总的时间复杂度为O(mn + (m+n)),通常m+n << mn,因此可近似认为为O(mn)。而且,逆序操作只是为了思考更容易,完全可以去掉。 空间复杂度为O(m+n) 链接:[http://www.cnblogs.com/jason-yang/archive/2012/04/26/2472755.html][-] [-]: http://www.cnblogs.com/jason-yang/archive/2012/04/26/2472755.html [copycode.gif]: /images/20220731/8bc9049d6d974d8ca1f7e0b9da299388.png
相关 大数相乘 一、背景 最近在看算法的时候发现了一个问题,我们都知道方法的形参是要指定类型的,假如有以下方法 public int example(int a,int b){ 傷城~/ 2022年09月30日 13:55/ 0 赞/ 209 阅读
相关 大数相乘 参考地址:[http://www.cnblogs.com/heyonggang/p/3599857.html][http_www.cnblogs.com_heyonggang_ 悠悠/ 2022年08月20日 06:29/ 0 赞/ 189 阅读
相关 大数相乘 [用分治法实现大数乘法,加法,减法(java实现)][java] 大数乘法即多项式乘法问题,求A(x)与B(x)的乘积C(x),朴素解法的复杂度O 小咪咪/ 2022年08月19日 15:12/ 0 赞/ 184 阅读
相关 大数相乘 无意中看到一个华为面试题,使用代码计算[1234567891011121314151617181920\2019181716151413121110987654321][123 系统管理员/ 2022年08月11日 20:29/ 0 赞/ 194 阅读
相关 大数相乘问题 [算法题-大数相乘问题][-] 今天在网上看到一个大数相乘的问题,题目是这样的:输入两个整数,要求输出这两个数的乘积。输入的数字可能超过计算机内整形数据的存储范围。 约定不等于承诺〃/ 2022年08月05日 10:25/ 0 赞/ 158 阅读
相关 大数相乘 题目:请使用代码计算1234567891011121314151617181920\2019181716151413121110987654321。 答: ![复制代码][ Bertha 。/ 2022年08月05日 08:54/ 0 赞/ 205 阅读
相关 大数相乘 在这之前我们先来了解一下Java 中每种基本数据类型所占存储空间的大小。其中 1Byte = 8bit。 <table> <tbody> <tr> <th> 朱雀/ 2022年06月02日 02:36/ 0 赞/ 253 阅读
相关 大数相乘 设X和Y是n位的二进制整数,现在要计算X\Y的结果 将a和b分为两段,每段长均为总长的1/2, ![20180329214901958][] 拼搏现实的明天。/ 2022年05月28日 05:06/ 0 赞/ 215 阅读
相关 大数相乘 题目 编写两个任意位数的大数相乘的程序,给出计算结果。比如: > 题目描述: 输出两个不超过100位的大整数的乘积。 > 输入: 输入两个大整数,如1234567 今天药忘吃喽~/ 2022年05月23日 11:23/ 0 赞/ 336 阅读
相关 大数相乘 def fun(num1,num2): num1 type str num2 type str a = map(int, 落日映苍穹つ/ 2021年10月24日 01:48/ 0 赞/ 330 阅读
还没有评论,来说两句吧...