例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;
}
習題68
68-1 大整數除法
問題描述
求兩個大的正整數相除的商，
輸入
第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;
}
68-2 階乘之和
問題描述
用高精度計算出 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;
}
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/428484.html
標籤：其他