大数问题：用字符串解决大数相加和相乘。

发布时间：2020-12-14 04:09:47 所属栏目：大数据来源：网络整理

导读：? 大数问题：用字符串解决大数相加和相乘。分类：?数据结构和算法 2008-03-03 08:44 ? 4349人阅读 ? 评论(5) ? 收藏 ? 举报 c 算法面试在ACM的题目中经常会遇到大数相加和相乘的问题，在有些公司的面试题中也有暗含要用大数才能解决的问题。比如：输入三

大数问题：用字符串解决大数相加和相乘。

分类：?数据结构和算法 2008-03-03 08:44? 4349人阅读? 评论(5)? 收藏? 举报

 
 c 
 算法 
 面试 

在ACM的题目中经常会遇到大数相加和相乘的问题，在有些公司的面试题中也有暗含要用大数才能解决的问题。比如：输入三个整数，写一个程序判断这个三个整数能否构成一个直角三角形。此题算法很简单，但是却暗含着结果可能溢出的问题。如果不会用大数，此题就无法给出完美的答案。

下面给出大数的乘法和加法算法：

1、加法：

// ?assume?m?is?bigger?than?n.
char * ?add( ? a,? b,255)">int ?m,0)">?n)
{
???? ?为结果分配内存空间。 ???? c? = ?( )malloc((m? + 2 ) sizeof ( ));
????memset(c,0)">0 ,?(m? )? ));
???? ?将字符（0?+?0x30?到?9?+?0x30）转换为数字（0到9）进行计算。 for ?i? ?n? - 1 ;?j? >= ;? -- i,0)">j)
????????c[i]? += ?(b[j]? 0x30 );
???? ?m? j)
????{
????????c[i]? ?(a[j]? );
???????? if ?(c[i]? > 9 )
????????{
????????????c[i? ]? ;
????????????c[i]? -= 10 ;
????????}
????}
???? ?将由纯数字组成的结果转换为字符串，并去除首部可能还存在的零。

???c[m + 1] = '/0'; ;?i? != ++ i)
????????c[i]? ;
???? ?(c[ == )
???????? ;?c[i] != '/0';? i)
????????????c[i]? ?c[i? ];
???? ?返回结果所在内存单元的首地址。 return ?c;
}

2、乘法：

?mult( ));

???? r)
????{
???????? ?j? ?r;?j? j,0)">k)
????????{
????????????c[k]? ?(a[i]? );
???????????? ?tmp? ?c[k]? / ;
???????????? ?(tmp? )
????????????{
????????????????c[k? ?tmp;
????????????????c[k]? ;
????????????}
????????}
????}

???? ?将由纯数字组成的结果转换为字符串，并去除首部可能还存在的零。 ????c[m + n] = '/0';
???? ?n;? ;

;??c[i] != '/0';? ];

???? ?c;
}

[cpp]? 
      view plain 
      copy 
       
      
 #include?<stdio.h>??
 #include?<stdlib.h>??
 #include?<string.h>??
 #include?<assert.h>??
 ??
 //?assume?m?is?bigger?than?n.??
 char*?mult(char?*a,?char?*b,87); background-color:inherit; font-weight:bold">int?m,87); background-color:inherit; font-weight:bold">int?n)?{??
 ????int?g?=?m?+?n;??
 ????//?为结果分配内存空间。??
char?*c?=?(char*)malloc(g?*?sizeof(char));??
 ????memset(c,?0,?g?*?char));??
 ??
 ????c[g?-?1]?=?'';??
 ????//?将字符（0?+?0x30?到?9?+?0x30）转换为数字（0到9）进行计算。??
 ????for?(int?i?=?m?-?1,?r?=?g?-?2;?i?>=?0;?--i,?--r)?{??
 ????????int?j?=?n?-?1,?k?=?r;?j?>=?0;?--j,?--k)?{??
 ????????????c[k]?+=?(a[i]?-?0x30)?*?(b[j]?-?0x30);??
 ????????????int?tmp?=?c[k]?/?10;??
 ????????????if?(tmp?>=?1)?{??
 ????????????????assert(k?-?1?>=?0);??
 ????????????????c[k?-?1]?+=?tmp;??
 ????????????????c[k]?-=?tmp?*?10;??
 ????????????}??
 ????????}??
 ????}??
//?将由纯数字组成的结果转换为字符串，并去除首部可能还存在的零。??
 ????int?i?=?0;?i?!=?g?-?1;?++i)??
 ????????c[i]?+=?0x30;??
if?(c[0]?==?0x30)??
 ????????int?i?=?0;?c[i]?!=?'';?++i)??
 ????????????c[i]?=?c[i?+?1];??
//?返回结果所在内存单元的首地址。??
return?c;??
 }??
 void?test(char*?a,87); background-color:inherit; font-weight:bold">char*?b)?{??
int?i?=?0;?a[i]?!=?'';?++i)?{??
if?(a[i]?!=?b[i])?{??
 ????????????printf("%d?%c?%cn",?i,?a[i],?b[i]);??
 ????????assert(a[i]?==?b[i]);??
 ????}??
 }??
int?main()?{??
char?a[1024]?=?"123";??
 ????char?b[1024]?=?"1";??
 ????printf("123?*?1n");??
char*?c?=?mult(a,?b,?3,?1);??
 ????test(c,?"123");??
 ????free(c);??
 ????strcpy(b,?"12");??
 ????printf("123?*?12n");??
 ????c?=?mult(a,?2);??
"1476");??
"123");??
 ????printf("123?*?123n");??
"15129");??
 ????strcpy(a,?"123456789123456789");??
 ????strcpy(b,?"123456789123456789");??
 ????printf("123456789123456789?*?123456789123456789n");??
 ????c?=?mult(a,?18,?18);??
 ????test(c,?"15241578780673678515622620750190521");??
 ????free(c);??
 ????strcpy(a,?"12345678912345678");??
 ????printf("123456789123456789?*?12345678912345678n");??
"1524157878067367740451151863907942");??
"1234567891234567");??
 ????printf("123456789123456789?*?1234567891234567n");??
"152415787806736675279683887625363");??
return?0;??
 }??

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!