算法————大数加法，大数乘法，高次方
文章目录
一.前言
最近在给同学讲算法的时候，系统的讲了一下大数相关的运行，包括大整数的加法，大整数的乘法，高次方(100次方)。在这里对其相关的算法进行整理。
在处理大数相关的算法时，数字会很大，往往发生超出int的表示范围的情况下，这时候就要采用数组对他们进行保存，即将运算的数字存为字符串进行运算。
在运算的过程中，为了方便起见，我将所有的数字全部放在数组的后面，前面全面放‘\0’.
也会将每个算法进行封装，因为在后面的算法往往会调用前面的算法，比如大数乘法中会调用大数加法。
二.准备函数
准备函数分为两个，一个是将字符串置后的算法，一个是将置后的数字输出的算法
1.置后算法
思想很简单，就是将字符串整体平移
void postpone(char a[],int n){ //置后 参数a需要置后的字符串，参数n字符串所在数组的空间大小
int i;
int al = strlen(a);
for(i=0;a[i];i++){
a[n-al+i] = a[i];
a[i] = 0;
}
}
2.输出函数
思想也很简单，遍历数组输出不是‘\0’的字符
//输出置后字符串
void prin(char a[],int n){ //参数a：需要输出的数组，参数n：数组的长度。
int i;
for(i=0;i<n;i++){
if(a[i]!=0){
printf("%c",a[i]);
}
}
printf("\n");
}
三.大数加法
1.算法思想
求c = a + b；f表示进位
例如 987+98
1.0 f =0
1.1num = a[3]+b[3] +f =8+7 =15
1.2 c[3] =5 ,f =1 (取模)
2.0 f =1
2.1 num = a[2] + b[2] + f = 18
2.2 c[2] = 8 ,f =1;
3.0 f =1
3.1 num =a[1]+b[1] +f = 10
3.2 c[1] = 0 ,f=1
4.0 f =1
4.1 num = a[0]+b[0] +f =1
4,2 c[0] = 1,f=0
so c = 1086
2.代码
//加法，结果存在b数组中
//参数含义：c = a+b
void add(char a[],char b[],char c[]){
int i,num,fi=0;
for(i=Max-1;a[i]!=0||b[i]!=0||fi!=0;i--){
a[i]==0?a[i]='0':0;
b[i]==0?b[i]='0':0;
num = a[i]-'0'+b[i]-'0'+fi;
c[i]= num%10 +'0';
fi = num/10;
}
}
3.调用
int main(void){
char a[Max]={0},b[Max]={0},c[Max]={0};
gets(a);
gets(b);
int bl =strlen(b);
postpone(a,Max);
postpone(b,Max);
add(a,b,c); //c= a+b
prin(c,Max);
return 0;
}
4.运行结果
四.多位数 X 一位数
1.思想
和加法类似，不同的地方在于
num = a[i] * n +f
其中a[i]表示多位数的某一位，n表示1位数，f表示进位
1.代码
//多位数 X 一位数，第二位乘数的范围从0到10，包含10.
//c = a * n
void multiplication (char a[],int n,char c[]){
int i,num,fi=0;
for(i=Max-1;a[i]!=0||fi!=0;i--){
a[i]==0?a[i]='0':0;
num = (a[i]-'0')*n+fi;
c[i]= num%10 +'0';
fi = num/10;
}
}
2.调用
int main(void){
char a[Max]={0},b[Max]={0},c[Max]={0};
gets(a);
postpone(a,Max);
multiplication (a,11,c);
prin(c,Max);
return 0;
}
五.多位数 X 多位数
1.思想
c = a * b；求c是多少。
num = a * b[i] （i的取值b的最高位到最低位）。
c = c * 10 + num；
比如999 *65
1.0 c = 0
1.1 num = a * b[0] = 999 * 6 = 5994;
1.1 c = c *10 +num = 5994
2.0 c = 5549
2.1 num =a
b[0] = 4995
2.2 c = c
10 +num = 64935
so 999 * 65 = 64935
2.代码
//多位数 X 多位数(bl 第二个乘数的长度)
//c = a * b
//多位数 X多位数调用了前面的两个算法
void multiplicationMax (char a[],char b[],int bl,char c[]){
int i;
char num[Max]={0};
for(i = Max -bl;i<Max;i++){
multiplication(a,b[i]-'0',num);
multiplication(c,10,c);//c = c*10
add(c,num,c);//c = c+num
}
}
3.调用
int main(void){
char a[Max]={0},b[Max]={0},c[Max]={0};
gets(a);
gets(b);
int bl =strlen(b);
postpone(a,Max);
postpone(b,Max);
multiplicationMax (a,b,bl,c);
prin(c,Max);
return 0;
}
4.运行结果
六.高次方
1.代码
//乘方
//a = background ^ index
//这里也调用了
void power(char background[],int index,char a[]){
int i,j,fi,num;
char b[Max] = {0};//暂存每次的结果
a[Max-1]='1';
for(i=0;i<index;i++){
fi=0;
//这里也可以直接调用多 X 多算法
for(j = 0;j<strlen(background);j++){
char c[Max] = {0};//暂存每次的结果
multiplication(a,background[j]-'0',c); //c = a * background[j]
multiplication(b,10,b);//b = b*10
add(b,c,b); //b = b+c;
}
for(j=0;j<100;j++){ //a=b
a[j] = b[j];
b[j] = 0;
}
}
}
2.调用
int main(void){
char a[Max]={'2','2'},b[Max]={0}; //也可以改为接收键盘录入
printf("%s^5=",a) ;
power(a,5,b);
prin(b,Max);
return 0;
}
3.运行结果
22 ^5
2^32
