算法————大数加法，大数乘法，高次方

r囧r小猫 2022-05-09 03:08 119阅读 0赞

# 算法————大数加法，大数乘法，高次方 #

### 文章目录 ###

*  算法————大数加法，大数乘法，高次方
 *   *   *  一.前言
         *  二.准备函数
         *   *  1.置后算法
             *  2.输出函数
         *  三.大数加法
         *   *  1.算法思想
             *  2.代码
             *  3.调用
             *  4.运行结果
         *  四.多位数 X 一位数
         *   *  1.思想
             *  1.代码
             *  2.调用
         *  五.多位数 X 多位数
         *   *  1.思想
             *  2.代码
             *  3.调用
             *  4.运行结果
         *  六.高次方
         *   *  1.代码
             *  2.调用
             *  3.运行结果

### 一.前言 ###

最近在给同学讲算法的时候，系统的讲了一下大数相关的运行，包括大整数的加法，大整数的乘法，高次方(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.运行结果 ####

![在这里插入图片描述][2018093001205222]

### 四.多位数 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.运行结果 ####

![在这里插入图片描述][2018093001334276]

### 六.高次方 ###

#### 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  
![在这里插入图片描述][20180930014101476]

2^32  
![在这里插入图片描述][20180930014208790]

[2018093001205222]: /images/20220509/d20e8fe2b3de4352986044894ff2af3d.png
[2018093001334276]: /images/20220509/9b145bbf3539419f946d98ce1c117a2a.png
[20180930014101476]: /images/20220509/bb5661916c62451db0059b62adc8248c.png?
[20180930014208790]: /images/20220509/261553e8c4734040a19d8e2e7fcdce01.png