高精度算法

迈不过友情╰ 2022-12-11 07:49 146阅读 0赞

C++中规定数不能无限大，否则溢出报错  
可在一些编程语言中，如：Python，Java等语言中允许数可以无限大（前提：你的内存要足够的大）

--------------------

C++/C

#include<iostream>
    using namespace std;
    int main()
    { 
    	cout<<1243544743546514334123412341234+124135325243515121234123412341234; 
    	//管你内存够不够大，哪怕是1023.9999PB，都溢出
    	return 0;
    }

Python

print(13124123412341234+345142341235134524123433234)
    #如果内存足够的大，不会报错

Java

System.out.println(121323453251234123413412341234+2345141235342546346253413213241234);
    //如果内存足够的大，不会报错

--------------------

那我们不妨用C++做一个几百位加几百位的一个程序吧！

## 高精度 ##

在NOIP，NOI中已经很少考，但有这样的题目  
其实并不难，这个算法以我们平时的数学方法为基准

### 1.高精度输入输出 ###

112312323243675451342+1232353577795131212421314784731  
这么大的数，如果按我们小时候数学方法计算：  
–1232353577795131212421314784731  
\+112312323243675451342  
对！就是这样计算！  
按照数学计算，末位+末位计算，>=10的向前进1  
现在有没有思路了？  
**1.输入输出**  
用字符串输入一个“数”，再用数组存储字符串的每一位，最后输出这个数组，非常完美！

#include<iostream>
    #include<cstring>
    #include<string>
    using namespace std;
    const int LEN=1005;
    int a[LEN],b[LEN],c[LEN];
    void clear(int a[])//清空数组
    { 
    	memset(a,0,sizeof(int)*LEN);
    }
    void read(int a[])
    { 
    	clear(a);//清空数组a 
    	char s[LEN];
    	cin>>s;
    	int len=strlen(s);//获取字符串s的长度 
    	for(int i=0;i<len;i++) a[len-i-1]=s[i]-'0';
    }
    void print(int a[])
    { 
    	int i;
    	for(i=LEN-1;i>0;i--)//i>0是为了考虑输入是0的情况 
    	{ 
    		if(a[i]!=0) break;//找到就停止 
    	}
    	for(;i>=0;i--) cout<<a[i];
    }
    int main()
    { 
    	read(a);
    	print(a);
    	return 0;
    }

输入12345，输出12345  
输入14135234634534623425，输出14135234634534623425  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center]

### 2.高精度加法 ###

123113435135  
123124354645  
———————  
246237789780

--------------------

5+5=10，向十位进一，个位减去———————0  
3+4=7，没有向前进一，加上个位进的1，是——8  
1+6=7，没有向前进一，是—————————–7  
5+4=9，没有向前进一，是—————————–9  
3+5=8，没有向前进一，是—————————–8  
.  
.  
.  
3+3=6，没有向前进一，是—————————–6  
2+2=4，没有向前进一，是—————————–4  
1+1=2，没有向前进一，是—————————–2  
所以答案是：246237789780（数学老师）  
C++：

void add(int a[],int b[],int c[])
    { 
    	clear(c);//清空c数组
    	for(int i=0;i<LEN-1;i++)
    	{ 
    		//不能直接等于a和b的和，因为这样可能忽略了前一位的进一
    		c[i]+=a[i]+b[i];
    		if(c[i]>=10)//满十进一
    		{ 
    			c[i]-=10;
    			c[i+1]+=1;
    		}
    	}
    }

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

### 高精度减法 ###

与加法并无太大差别  
加法以十进一`c[i+1]+=1`表示向前一位进一  
减法不一样  
一旦出现a\[i\]-b\[i\]小于了0，也就是不够减的时候，我们要向a\[i+1\]借个1，在给a\[i\]+10，也就是`借一当十`，从而解决不够减的问题

void sub(int a[],int b[],int c[])
    { 
    	clear(c);//清空c数组
    	for(int i=0;i<LEN-1;i++)
    	{ 
    		c[i]+=a[i]-b[i];
    	}
    }

### 高精度乘法 ###

这一次的讲解会复杂一点  
**高精度乘低精度**  
与减法和加法并不一样  
57  
25 乘  
首先`25`的个位`5`乘以7得35，满十了，向高位进3  
再用`25`的个位`5`乘以5得25，满十了，向高位进2  
第一次得到285

--------------------

Then`25`的十位`2`乘以7得14，满十了，向高位进1  
Finally`25`的十位`2`乘以5得10，满十了，向高位进1  
第二次得到1140

--------------------

上为数学方法去做57\*25

但是用这种数学方法算出乘法，其程序不免有些复杂，  
因为也许这个数组几十位，另一个数组几百位，最起码要乘10\*100=1000次  
不如这样想：

> 由于每个位只保留一个数，那么我们直接干脆一点，一次乘上另一个数，然后高位全部丢弃给上一位，这一位只保留个位上的数字

void div(int a[],int b,int c[])
    { 
    	clear(c);//清空数组
    	for(int i=0;i<LEN-1;i++)
    	{ 
    		a[i]*=b;//直接乘b，然后高位全部丢弃给上一位，只保留个位上的数
    		if(a[i]>=10)
    		{ 
    			a[i+1]=a[i]/10;
    			a[i]%=10;
    		}
    	}
    }
    //注：尽管想法不错，但是特别注意的是int类型，可能承受不下

**高精度乘高精度**

# 后期博客更新中。。。 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/90726fab255d4e46a25cb9ebad772350.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQ0NTU5OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/b9e341f48da44550b476c4e49d9c1043.png