分类导航

C&C++ 发布时间：2022-04-13 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了C语言程序设计100例之（68）：大整数乘法，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

@H_696_0@例68 大整数乘法

问题描述

求两个不超过200位的非负整数的积。

输入

有两行，每行是一个不超过200位的非负整数，没有多余的前导0。

输出

一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

输入样例

12345678900

98765432100

输出样例

1219326311126352690000

（1）编程思路。

将大整数用字符串保存，编写函数void mul(char *a,char *b,char *C)实现大整数c=a*b。

在函数中用int x[201]和int Y[201]分别存放两个乘数，用int z[401]来存放积。计算的中间结果也都存在数组z中。数组z长度取401 是因为两个200 位的数相乘，积最多会有400 位。x[0], y[0], z[0]都表示个位。

计算的过程基本上和小学生列竖式做乘法相同。为编程方便，不急于处理进位，而将进位问题留待最后统一处理。

在乘法过程中，数组x的第i 位和y的第j 位相乘所得的数，一定是要累加到z的第i+j 位上。这里下标i, j 都是从右往左，从0 开始数。

（2）源程序。

#include <stdio.h>

#include <String.h>

void mul(char *a,char *b,char *C)

{

int len1=strlen(a),len2=strlen(b);

int x[201],Y[201],z[401];

int len=len1+len2;

memset(x,0,sizeof(X));

memset(y,0,sizeof(y));

memset(z,0,sizeof(z));

int i,j;

for (i=len1-1;i>=0;i--)

x[len1-1-i]=a[i]-'0';

for (i=len2-1;i>=0;i--)

Y[len2-1-i]=b[i]-'0';

for (i=0;i<len1;i++)

{

for (j=0;j<len2;j++)

{

z[i+j]+=x[i]*Y[j];

}

for (i=0;i<len;i++)

{

if (z[i]>=10)

{

z[i+1]+=z[i]/10;

z[i]=z[i]%10;

}

while (len>0 && z[len-1]==0) // 去前置0

len--;

if (len==0) // a*b=0时特判

{

c[0]='0';

c[1]='\0';

return ;

}

for (i=0;i<len;i++)

c[i]=z[len-1-i]+'0';

c[len]='\0';

}

int main()

{

char s1[201],s2[201],ans[401];

scanf("%s%s",s1,s2);

mul(s1,s2,ans);

printf("%s\n",ans);

return 0;

}

@H_696_0@习题68

68-1 大整数除法

问题描述

求两个大的正整数相除的商。

输入

第1行是被除数，第2行是除数。每个数均不超过100位。

输出

一行，相应的商的整数部分

输入样例

2376

输出样例

（1）编程思路。

将大整数用字符串保存，编写函数void div(char *a,char *b,char *q)实现q=a/b。

实现大整数除法的基本的思想是反复做减法，从被除数里最多能减去多少个除数，商就是多少。但是不能一个一个地减除数，这样既慢又不好处理。

实际处理方法应该这样，将除数扩大10倍、100倍、…或10^k倍，使得除数和被除数等长，之后再进行减法操作，依次减除数的10^k倍、…、除数的100倍、除数的10倍、除数本身。每次记下够减的次数，所得结果就是商。

下面以231568除以328为例进行说明。

先将除数328扩大1000倍，即后面加上3个0，使得除数328000与被除数231568等长，231568减去328000，不够减，因此记下减的次数为0；之后，去掉除数后面的 1个0，得到32800（即除数扩大100倍），231568减去32800，够减7次，余下 1968，同样记下减的次数为7；再去掉除数后面的 1个0，得到3280（即除数扩大10倍），1968减3280，不够减，同样记下减的次数为0；再去掉除数后面的 1个0，此时就是除数本身328，1968减328，够减6次，余下0，同样记下减的次数为6，结束运算。依次记下的减的次数为0706，去掉前导的0，商就是706。

（2）源程序。

#include <stdio.h>

#include <String.h>

void sub(char *a,char *b,char *C)

{

int len1=strlen(a),len2=strlen(b);

int x[111],Y[111],z[111];

int len=len1;

memset(x,0,sizeof(X));

memset(y,0,sizeof(y));

memset(z,0,sizeof(z));

int i,j;

for (i=len1-1,j=0;i>=0;i--,j++)

x[j]=a[i]-'0';

for (i=len2-1,j=0;i>=0;i--,j++)

Y[j]=b[i]-'0';

int cf=0;

for (i=0;i<len;i++)

{

z[i]=x[i]-Y[i]+cf;

if (z[i]<0)

{

z[i]+=10;

cf=-1;

}

else

cf=0;

}

while (len>0 && z[len-1]==0) // 去前置0

len--;

if (len==0) // a-b=0时特判

{

c[0]='0';

c[1]='\0';

return ;

}

for (i=0;i<len;i++)

c[i]=z[len-1-i]+'0';

c[len]='\0';

}

int bigger(char *a,char *b)

{

if (strlen(a)>strlen(b)) return 1;

if (strlen(a)<strlen(b)) return 0;

if (strcmp(a,b)>=0) return 1;

else return 0;

}

void div(char *a,char *b,char *q)

{

if (bigger(a,b)==0) // 被除数a小于除数b，商为0

{

q[0]='0';

q[1]='\0';

return ;

}

int len1=strlen(a);

int len2=strlen(b);

int i;

for (i=len2;i<len1;i++) // 将b的末尾添加0到与a等长

b[i]='0';

b[i]='\0';

for (i=0;i<=len1-len2;i++)

{

int times=0;

while (bigger(a,b))

{

times++;

sub(a,b,a);

}

q[i]=times+'0';

b[strlen(b)-1]='\0';

}

q[i]='\0';

for (i=0;q[i]=='0';i++);

strcpy(q,&q[i]);

}

int main()

{

char a[115],b[115],q[115];

scanf("%s", a);

scanf("%s", b);

div(a,b,q);

printf("%s\n",q);

return 0;

}

68-2 阶乘之和

问题描述

用高精度计算出 S = 1!+2!+3!+⋯+n!（n≤50）。

其中“!”表示阶乘，例如：5! = 5×4×3×2×1。

输入格式

一个正整数n。

输出格式

一个正整数 S，表示计算结果。

输入样例

输出样例

（1）编程思路。

编写函数void bigNumMul(char a[],int b,char c[])实现一个大整数a乘以一个int型整数，得到乘积为大整数c。

编写函数void bigNumAdd(char a[],char b[],char c[])实现大整数c=a+b。

（2）源程序。

#include <stdio.h>

#include <String.h>

#define MAX_LEN 201

void bigNumAdd(char a[],char b[],char c[])

{

int len1=strlen(a),len2=strlen(b);

int x[MAX_LEN],Y[R_158_11845@AX_LEN],z[MAX_LEN];

int len=len1>len2?len1:len2;

memset(x,0,sizeof(X));

memset(y,0,sizeof(y));

memset(z,0,sizeof(z));

int i;

for (i=len1-1;i>=0;i--)

x[len1-1-i]=a[i]-'0';

for (i=len2-1;i>=0;i--)

Y[len2-1-i]=b[i]-'0';

int cf=0;

for (i=0;i<len;i++)

{

z[i]=(x[i]+Y[i]+cf)%10;

cf=(x[i]+Y[i]+cf)/10;

}

z[len++]=cf;

while (len>0 && z[len-1]==0) // 去前置0

len--;

if (len==0) // a+b=0时特判

{

c[0]='0';

c[1]='\0';

return ;

}

for (i=0;i<len;i++)

c[i]=z[len-1-i]+'0';

c[len]='\0';

}

void bigNumMul(char a[],int b,char c[]) // C=a*b

{

int num[MAX_LEN]={0},result[R_158_11845@AX_LEN+10]={0};

// 将a中存储的字符串形式的整数转换到num中去，

// num[0]对应于个位、num[1]对应于十位、……

int len1 = strlen(a);

int i,j;

for (i=len1-1,j=0;i>=0; i--)

num[j++] = a[i] - '0';

int len2 =0;

int t=b;

do {

len2++;

t=t/10;

} while (t!=0 );

for (i=0;i < len1; i++)

result[i] = num[i]*b;

// 统一处理进位问题

int len=len1+len2;

for (i = 0; i < len; i++)

{

if (result[i] >= 10)

{

result[i+1] += result[i] / 10;

result[i] %= 10;

}

while (len>0 && result[len-1]==0) // 去前置0

len--;

if (len==0) // a*b=0时特判

{

c[0]='0';

c[1]='\0';

return ;

}

for (i=0;i<len;i++)

c[i]=result[len-1-i]+'0';

c[len]='\0';

}

int main()

{

char a[MAX_LEN],s[MAX_LEN];

int n,i;

scanf("%d",&n);

a[0]='1', a[1]='\0';

s[0]='1'; s[1]='\0';

for (i=2;i<=n;i++)

{

bigNumMul(a,i,a);

bigNumAdd(s,a,s);

}

printf("%s\n",s);

return 0;

}

68-3 Hillwer编码

问题描述

Hillwer编码的转换规则如下：对于每一条原码S，保证仅由26个大写字母组成。将每个字母后移R位，得到中转码S1（当S=‘XYZ’，R=2时，S1=‘ZAB’。即变成当前字母后R个字母，超过‘Z’则从‘a’开始）。接着，将中转码进行“符转数”操作，将S1每一位的ACS码（即ASCLL码）相乘，得到数串Q。转换后的编码即为Q。

输入

第1行，读入n，R。第2~n+1行，每行一条编码S。

输出

共n*2行，奇数行，每行一条中转码S1；偶数行，每行一条转换后的编码Q。

输入样例

2 6

HelLOWORLD

LETUSGO

输出样例

NKRRUCUXRJ

10167740864629920000

RKZAymU

20957073637500

（1）编程思路1。

将S1中每一个字符的ASCLL码相乘得到的数串Q超出了长整数的表示范围，因此需要进行高精度乘法运算。

编写函数void bigNumMul(char a[],int b,char c[])实现一个大整数a乘以一个int型整数，得到乘积为大整数c。

（2）源程序1。

#include <stdio.h>

#include <String.h>

void bigNumMul(char a[],int b,char c[]) // C=a*b

{

int num[1300]={0},result[1300+10]={0};

// 将a中存储的字符串形式的整数转换到num中去，

// num[0]对应于个位、num[1]对应于十位、……

int len1 = strlen(a);

int i,j;

for (i=len1-1,j=0;i>=0; i--)

num[j++] = a[i] - '0';

int len2 =0;

int t=b;

do {

len2++;

t=t/10;

} while (t!=0 );

for (i=0;i < len1; i++)

result[i] = num[i]*b;

// 统一处理进位问题

int len=len1+len2;

for (i = 0; i < len; i++)

{

if (result[i] >= 10)

{

result[i+1] += result[i] / 10;

result[i] %= 10;

}

while (len>0 && result[len-1]==0) // 去前置0

len--;

if (len==0) // a*b=0时特判

{

c[0]='0';

c[1]='\0';

return ;

}

for (i=0;i<len;i++)

c[i]=result[len-1-i]+'0';

c[len]='\0';

}

int main()

{

int n,r;

scanf("%d%d",&n,&r);

r=r%26;

char s[600],q[1300];

while(n--)

{

scanf("%s",s);

q[0]='1';

q[1]='\0';

int i;

for (i=0;s[i]!='\0';i++)

{

if (s[i]+r<='Z') s[i]=s[i]+r;

else s[i]=s[i]+r-'Z'+'A'-1;

bigNumMul(q,(int)s[i],q);

}

printf("%s\n",s);

printf("%s\n",q);

}

return 0;

}

（3）编程思路2。

在上面的源程序1中，实现大整数乘法时，保存大整数的数组num中，每个数组元素保存1位数字，这样既浪费存储空间，又耗费计算时间。实际上，一个数组元素中可以保存大整数的6位数字，因为它与一个ASCII码（最多为3位整数）相乘，不会超过int型整数的表数范围。下面的源程序2就是按这个想法编写的。

（4）源程序2。

#include <stdio.h>

#include <String.h>

#define MOD 1000000

void work(char s[])

{

int q[205];

memset(q,0,sizeof(q));

int len=1;

q[1]=1;

int i,j;

for (i=0;s[i]!='\0';i++)

{

int t=(char)s[i];

for (j=1;j<=len;j++)

q[j]=q[j]*t;

int cf;

for (j=1;j<=len;j++)

{

cf=q[j]/MOD;

q[j]=q[j]%MOD;

q[j+1]+=cf;

}

if (q[len+1]!=0)

{

len++;

}

printf("%d",q[len]);

for (i=len-1;i>=1;i--)

printf("%06d",q[i]);

printf("\n");

}

int main()

{

int n,r;

scanf("%d%d",&n,&r);

while (n--)

{

char s[605];

scanf("%s",s);

int i;

for (i=0;s[i]!='\0';i++)

{

s[i]=(s[i]-'A'+r)%26+'A';

}

printf("%s\n",s);

work(s);

}

return 0;

}

大佬总结

以上是大佬教程为你收集整理的C语言程序设计100例之（68）：大整数乘法全部内容，希望文章能够帮你解决C语言程序设计100例之（68）：大整数乘法所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。

标签：

上一篇: C语言程序设计100例之（69）：麦... 下一篇:C语言程序设计100例之（67）：大...

猜你在找的C&C++相关文章

两个稀疏矩阵的乘法算法的实现——十字链表矩阵相乘 2022-04-13
c – program_options代码中的链接错误与ubuntu上的boost库 2019-10-05
如何将警告视为Makefile中的错误？ 2019-10-05
如何检查数组是否有任何重复？ 2019-10-05
c – 你应该在虚拟继承中写“公共虚拟”还是“虚拟公共”？ 2019-10-05
C URLencode库(支持Unicode)？ 2019-10-05
objective-c – 启用ARC的设备上的iOS崩溃 2019-10-05
c – 除零除法：检查除数的表达式不会导致零与检查除数不为零？ 2019-10-05
c – 重复排列：避免溢出 2019-10-05
C“删除”很慢.我应该先看哪儿？ 2019-10-05