大数是算法语言中的数据类型无法表示的数,其位数超过最大数据类型所能表示的范围,所以,在处理大数问题时首先要考虑的是怎样存储大数,然后是在这种存储方式下其处理的实现方法。
一般情况下大数的存储是采用字符数组来存储,即将大数当作一个字符串来存储,而对其处理是按其处理规则在数组中模拟实现。
?三 大数乘法。
大数乘法,相对之前的加法和减法,难度有所提高,但是本质还是一样的。
下面说说我的方法:
1、利用字符数组读入大数a,b
2、将大数反向存储到整型数组中。(此时满足低位在数组下标小的位置上)
3、逐个相乘。?? 此时要注意 乘数i位和乘数j位的乘积,应累加在结果数组的i+j位上。? 这个结论不难发现,可通过列个简单的竖式乘法验证。
4.、处理进位,(从低位开始到最高位逐位处理,将本位结果的个位作为该为的结果,而10位以上的数均作为进位进到上一位,一直到所有进位处理完)
5、然后整体再反向存入字符数组,打印出结果。
?
思路很常规,算法也比较简单,但是效率方面,可能不太理想。
水平有限,只能写出这样的代码。以后有能力了,再优化优化。
- #include<stdio.h>??
- #include<string.h>??
- #define?MaxLen?1000??
- int?main()??
- {??
- ????char?str_a[MaxLen],?str_b[MaxLen],?str_c[2*MaxLen];??
- ????int?num_a[MaxLen],?num_b[MaxLen],?num_c[2*MaxLen];??
- int?i,?j,?k,?d,?len_a,?len_b;??
- ??
- ????while?(scanf("%s%s",str_a,str_b)!=EOF)?????
- ????{??
- ????????for?(i=0;?i<MaxLen;?i++)?????
- ????????{??
- ????????????num_a[i]?=?0;????????
- ????????????num_b[i]?=?0;??
- ????????}??
- ????????for?(i=0;?i<2*MaxLen;?i++)??
- ????????????num_c[i]?=?0;??
- ????????len_a?=?strlen(str_a);???????
- ????????i?=?len_a?-?1;??
- ????????k?=?0;??
- while?(?i>=0?)??
- ????????????num_a[k++]?=?str_a[i--]?-?'0';??
- ??
- ????????len_b?=?strlen(str_b);??
- ????????i?=?len_b?-?1;??
- ????????????num_b[k++]?=?str_b[i--]?-?'0';??
- for?(?i=0;?i<len_a;?i++?)?????
- ????????????for?(?j=0;?j<len_b;?j++?)??
- ????????????????num_c[i+j]?+=?num_a[i]?*?num_b[j];??
- ????????k?=?2?*?MaxLen?-?1;??
- while?(?k>=0?&&?num_c[k]==0?)??????????
- ????????????k--;??
- ????????i?=?0;??
- ????????d?=?0;??
- while(?i<=k?)??????
- ????????{??
- ????????????num_c[i]?+=?d;??????
- ????????????d?=?num_c[i]?/?10;??????
- ????????????num_c[i]?%=?10;??????
- ????????????i++;??
- ????????}??
- while?(?d>0?)??????????
- ????????????num_c[i]?=?d?%?10;??
- ????????????d?=?d?/?10;??
- ????????????i++;??
- ????????k?=?i;?????????
- for?(?i=k-1;?i>=0;?i--?)??
- ????????????str_c[k-i-1]?=?num_c[i]?+?'0';??????
- ????????str_c[k]?=?' ';??
- ????????printf("%sn",str_c);?????
- ????}??
- ????return?0;??
- }??