大佬教程收集整理的这篇文章主要介绍了C语言程序设计100例之(68):大整数乘法,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
问题描述
求两个不超过200位的非负整数的积。
输入
有两行,每行是一个不超过200位的非负整数,没有多余的前导0。
输出
一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。
输入样例
12345678900
98765432100
输出样例
1219326311126352690000
将大整数用字符串保存,编写函数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 开始数。
#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;
}
问题描述
求两个大的正整数相除的商。
输入
第1行是被除数,第2行是除数。每个数均不超过100位。
输出
一行,相应的商的整数部分
输入样例
2376
24
输出样例
99
(1)编程思路。
将大整数用字符串保存,编写函数void div(char *a,char *b,char *q)实现q=a/b。
实现大整数除法的基本的思想是反复做减法,从被除数里最多能减去多少个除数,商就是多少。但是不能一个一个地减除数,这样既慢又不好处理。
实际处理方法应该这样,将除数扩大10倍、100倍、…或10k倍,使得除数和被除数等长,之后再进行减法操作,依次减除数的10k倍、…、除数的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;
}
问题描述
用高精度计算出 S = 1!+2!+3!+⋯+n!(n≤50)。
其中“!”表示阶乘,例如:5! = 5×4×3×2×1。
输入格式
一个正整数n。
输出格式
一个正整数 S,表示计算结果。
输入样例
3
输出样例
9
(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[MAX_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[MAX_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;
}
问题描述
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,请注明来意。