0基礎學演算法 第四彈 高精度
- 2020 年 3 月 18 日
- 筆記
今天寫這個的時候心情是非常糟糕的，因為我寫了這篇博文四遍，每次都因為網頁問題，不是需要刷新就是要重開，以至於我昨天一天和今天上午寫了整整4遍沒提交成功，不嘮嗑了，切入正題。
高精度是一種計算大數的演算法，通常我們計算的時候會用int，要是範圍大了就會用long long類型，這有張表，共大家參考
一旦數據超過了long long型，就會用到了高精度，高精度的基本原理是將數字分別存入數組的每一項中，然後將它模擬豎式計算，剛好他滿足豎式計算的條件，只要小心進退位的問題就好了
由於洛谷上有模版題，所以今天我們就結合題目一起來理解高精度
高精度的加減法
P1601 https://www.luogu.com.cn/problem/P1601
P1601是高精度的加法，先思考一下，不要看題解，如果你有思路，就去實現一下吧，沒有思路也沒事，不管怎樣，你都可以繼續看這篇部落格。
好，請確保你已經思考過了，如果你看過我的第一彈的流程圖，就把你的思路畫下來，然後就把它實現好了。
大致思路
如果你完成了前面的內容，那麼恭喜你，你離成功只有一步了，首先看看流程圖，梳理一下思路，再照著流程圖完成程式碼吧
思路就是這樣了，那我們可以根據流程圖，去模擬程式碼，達到實現高精度加法，來給大家看看我的程式碼
#include <bits/stdc++.h> using namespace std; int main(){ char a[505],b[505]; cin>>a>>b; int alen,blen,sum[505],f=0,k=0; alen=strlen(a); blen=strlen(b); while(alen!=0||blen!=0) { int a1=0,b1=0; if(alen>0) { a1=a[--alen]-'0'; } if(blen>0) { b1=b[--blen]-'0'; } int t=a1+b1+f; f=t/10; if(t>9) { t=t%10;//這裡是進位操作，千萬不能漏 } sum[k++]=t; } if(f) { sum[k++]=1; } for(int i=k-1;i>=0;i--) { cout<<sum[i]; } return 0; }
是非常吻合流程圖的，你們可以自己去試試，或者運行一下，這個高精度加法也可以去提交一下，另外思考一下高精度減法，減法和加法非常相似，區別就在於減法要注意退位的事，還有就是要注意可能有負數，記得加負號，接下來只要你能理解高精度加法的內容，就可以自己獨立完成高精度減法，我可以再給大家一個思路（其實是一個豎式）
好，看了這個豎式後有沒有豁然開朗的感覺？沒有就對了自己試一試，也許就柳暗花明又一村了呢？
接下來，我們來講乘法 其實乘法原理是一樣的，都和加法一樣，模擬出豎式的
運算，然後注意一下進位的問題就ok了，因為我知道你認真看到這已經很辛苦了，所以我就直接給出程式碼好了。
#include <bits/stdc++.h> #define N 2001 using namespace std; int main(){ string s1,s2; int a[N],b[N],c[2*N],la,lb; cin>>s1>>s2; la = s1.length(),lb=s2.length(); //cout<<la<<lb; for(int i=0;i<la;i++) a[i]=s1[la-i-1]-'0'; for(int i=0;i<lb;i++) b[i]=s2[lb-i-1]-'0'; for(int i=0;i<la;i++) for(int j=0;j<lb;j++) c[i+j]+=a[i]*b[j]; int l=la+lb; //cout<<l; //return 0; for(int i=0;i<l;i++) { c[i+1]+=c[i]/10; c[i]%=10; } while(c[l-1]==0&&l>1) l--; for(int i=l-1;i>=0;i--) { cout<<c[i]; } return 0; }
以上就是今天的內容了，你是不是感覺缺了什麼，對，我還沒寫除法的，如果你還想學到關於除法的高精度演算法，就請關注➕一下我，我會在下期開頭公布答案，今天的課後練習就是自己把今天的高精度程式碼在編譯器中寫一遍。
如果你覺得我寫的好，或喜歡我的0基礎學演算法系列，請你點贊?，和關注➕我，我會給大家帶來更多的演算法，下一期預告 第五彈 填坑！
如果你對我講的有什麼問題，你可以在評論區留言，我會在填天坑系列中解答所有的問題
