700字范文 > 面试官让你用C语言实现大数相乘慌吗？

面试官让你用C语言实现大数相乘慌吗？

时间：2022-06-05 02:43:32

相关推荐

面试官让你用C语言实现大数相乘慌吗？

在之前的笔试题解析里面，我写了大数相加的问题，这里再剖析一个大数相乘，顾名思义，大数相乘就是这个数已经大到最大的数据类型都没有办法保存了。

我们看看最大的数据类型可以保存多大的数据。

#include"stdio.h"#include"string.h"intmain(){printf("0~%llu\n",(1ULL<<sizeof(unsignedlonglong)*8)-1);return0;}

代码输出：

0~18446744073709551615

所以如果我们的数大于18446744073709551615就会存在没有一个数据类型可以存储的情况，所以会有大数相乘的问题。

如何解决大数相乘问题？

看我下面的解题思路，这个思路可以也是从网上看到的。

我们拿乘数的最低位，也就是2358中的8 依次乘以被乘数的每一位，然后不做进位处理得到8 16 32 40.

继续拿十位，百位，千位相乘，还是不进位

然后依次列相加，相加的时候，也不做进位处理得到一个数据2 7 19 40 51 57 40.

后面循环对上一步得到的数据进行进位处理，就会得到最终的结果。

代码实现

#include"stdio.h"#include"string.h"#definechar_to_int(a)(int)(a-'0')#defineint_to_char(a)(char)(a+'0')intmain(){chara[1000]={"1245"};charb[1000]={"2358"};charc[1000]={0};inti=0,j=0,k=0;memset(c,0,sizeof(c));printf("%ld\n",strlen(a)-1);printf("%ld\n",strlen(b)-1);/*完成图片中的1，2步，结果从数组开头开始存放*/for(i=0;i<strlen(a);i++){k=i;for(j=0;j<strlen(b);j++){c[k]+=char_to_int(a[i])*char_to_int(b[j]);k++;}}printf("k=%d\n%.2d%.2d%.2d%.2d%.2d%.2d%.2d\n",k,c[0],c[1],c[2],c[3],c[4],c[5],c[6]);/*完成图片中的3步,从后面往前面*/for(i=k-1;i>0;i--){if(c[i]>=10){c[i-1]=c[i]/10+c[i-1];c[i]=c[i]%10;printf("%.2d%.2d%.2d%.2d%.2d%.2d%.2d\n",c[0],c[1],c[2],c[3],c[4],c[5],c[6]);}}/*输出*/for(i=0;i<k;i++)printf("%d",c[i]);putchar('\n');return0;}

我这个代码直接参照我上面的图片例程编写，比较有参考性，大家在看代码的时候也需要注意一些细节，比如strlen获取的长度，k变量的大小等等。

程序输出：

33k=702 07 19 40 51 57 4002 07 19 40 51 61 0002 07 19 40 57 01 0002 07 19 45 07 01 0002 07 23 05 07 01 0002 09 03 05 07 01 002935710

随机验证下代码

验证的时候发现上面写的代码还有一些问题，顺便修改了下

#include"stdio.h"#include"string.h"#definechar_to_int(a)(int)(a-'0')#defineint_to_char(a)(char)(a+'0')intmain(){chara[1000]={"1561591985156415641419841516515919"};charb[1000]={"45645689129812561564159129821985125641"};unsignedlonglongc[1000]={0};inti=0,j=0,k=0;memset(c,0,sizeof(c));/*完成图片中的1，2步，结果从数组开头开始存放*/for(i=0;i<strlen(a);i++){k=i;for(j=0;j<strlen(b);j++){c[k]+=char_to_int(a[i])*char_to_int(b[j]);k++;}}/*完成图片中的3步,从后面往前面*/for(i=k-1;i>0;i--){if(c[i]>=10){c[i-1]=c[i]/10+c[i-1];c[i]=c[i]%10;}}/*输出*/for(i=0;i<k;i++)printf("%llu",c[i]);putchar('\n');return0;}

代码输出：

71279942302056620434200279768171066840415273983925010258196655791579079

但是遗憾的是，电脑自带的计算器不能计算这么大的数据，所以，我也不知道这个计算结果是不是正确的。

所以计算一个计算器可以计算的值

#include"stdio.h"#include"string.h"#definechar_to_int(a)(int)(a-'0')#defineint_to_char(a)(char)(a+'0')intmain(){chara[1000]={"1844674407"};charb[1000]={"3709551615"};unsignedlonglongc[1000]={0};inti=0,j=0,k=0;memset(c,0,sizeof(c));/*完成图片中的1，2步，结果从数组开头开始存放*/for(i=0;i<strlen(a);i++){k=i;for(j=0;j<strlen(b);j++){c[k]+=char_to_int(a[i])*char_to_int(b[j]);k++;}}/*完成图片中的3步,从后面往前面*/for(i=k-1;i>0;i--){if(c[i]>=10){c[i-1]=c[i]/10+c[i-1];c[i]=c[i]%10;}}/*输出*/for(i=0;i<k;i++)printf("%llu",c[i]);putchar('\n');return0;}

程序输出：

6842914925636017305

计算器输出

好吧，再来一次

#include"stdio.h"#include"string.h"#definechar_to_int(a)(int)(a-'0')#defineint_to_char(a)(char)(a+'0')intmain(){chara[1000]={"184467"};charb[1000]={"3709551615"};unsignedlonglongc[1000]={0};inti=0,j=0,k=0;memset(c,0,sizeof(c));/*完成图片中的1，2步，结果从数组开头开始存放*/for(i=0;i<strlen(a);i++){k=i;for(j=0;j<strlen(b);j++){c[k]+=char_to_int(a[i])*char_to_int(b[j]);k++;}}/*完成图片中的3步,从后面往前面*/for(i=k-1;i>0;i--){if(c[i]>=10){c[i-1]=c[i]/10+c[i-1];c[i]=c[i]%10;}}/*输出*/for(i=0;i<k;i++)printf("%llu",c[i]);putchar('\n');return0;}

程序输出

684289857764205

计算器输出

嗯，好像没有问题。