****使用高精度演算法的理由****
在C/C++中常用的資料型別有int和long long.int占用一個機器字長,在32位系統中int占4個位元組,范圍為[-2-31,231-1];long long占用8個位元組,范圍為[-263,263-1].一旦超過這兩種資料型別的范圍則不能夠滿足特定資料要求.比如資料2100數量級不能夠滿足要求,這一型別因此被稱為高精度或大數型別.高精度有加減乘除型別.
****高精度加法****
題目：https://www.luogu.com.cn/problem/P1601
求解A+B：（1）輸入兩個正數a,b,輸出和（a,b≤109）;（2）輸入兩個正數a,b,輸出和（a,b≤10500）
如下圖（左）所示,演算法核心為紅色筆記部分,既要實作a[i]與b[i]的相加,又要實作進位和本位的輸出考慮.在程式考慮時,如果輸入數為1234和827這組資料,如下圖（右）將1234的1認為陣列的第0位,827的8認為陣列的第0位,則會導致相加錯誤,正確的操作應如圖中紫色部分所示,對資料進行轉置，將1234中的第0位認為是4,827中的第0位認為是7.
具體代碼如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 //采用陣列模擬高精度型別 4 char s1[505],s2[505]; 5 int a[505],b[505],c[505]; 6 7 int main(void) 8 { 9 int la,lb,lc; 10 memset(c,0,sizeof(c)); 11 scanf("%s",s1); //輸入字符s1 12 scanf("%s",s2); //輸入字符s2 13 14 la = strlen(s1); 15 lb = strlen(s2); 16 17 //將字符轉換為數字并且轉置 18 for(int i = 0; i < la; i++) 19 a[la-i] = s1[i] - '0'; 20 for(int i = 0; i < lb; i++) 21 b[lb-i] = s2[i] - '0'; 22 23 lc = max(la,lb) + 1; 24 for(int i = 1; i <= lc; i++) 25 { 26 c[i] += a[i] + b[i]; 27 c[i+1] = c[i] / 10; 28 c[i] = c[i] % 10; 29 } 30 31 if(c[lc] == 0 && lc > 0) 32 //洗掉前導0,lc>0是防止0+0=0的情況 33 lc--; 34 for(int i = lc; i > 0; i--) 35 printf("%d",c[i]); 36 37 return 0; 38 } 39
****高精度減法****
題目：https://www.luogu.com.cn/problem/P2142
求解A-B，需要注意：（1）如果a<b，則需要交換a與b;（2）如果a[i]<b[i]，需要高位借1當10使用.
具體代碼如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 char s1[10090],s2[10090],s3[10090]; 5 int a[10090],b[10090],c[10090]; 6 int flag = 0; 7 bool compare(char s1[],char s2[]) 8 { 9 //如果s1>=s2回傳T,否則回傳F. 10 int u = strlen(s1),v = strlen(s2); 11 if (u != v) return u > v; 12 //u>v回傳T,u<v回傳F 13 //u=v時進行比較 14 for(int i = 0; i < u; i++) 15 if(s1[i] != s2[i]) 16 return s1[i] > s2[i]; 17 return true; 18 } 19 20 int main(void) 21 { 22 int la,lb,lc; 23 scanf("%s",s1); 24 scanf("%s",s2); 25 26 if(!compare(s1,s2)) 27 { 28 //如果s1<s2則交換,利用復制方式 29 flag = 1; 30 strcpy(s3,s1); 31 strcpy(s1,s2); 32 strcpy(s2,s3); 33 } 34 35 la = strlen(s1); 36 lb = strlen(s2); 37 lc = max(la,lb); 38 39 //字符轉數字并轉置 40 for(int i = 0; i < la; i++) 41 a[la-i] = s1[i] - '0'; 42 for(int i = 0; i < lb; i++) 43 b[lb-i] = s2[i] - '0'; 44 45 for(int i = 1; i<= lc; i++) 46 { 47 //如果a[i]<b[i]則借位 48 if(a[i] < b[i]) 49 { 50 a[i+1]--; 51 a[i] += 10; 52 } 53 c[i] = a[i] - b[i]; 54 } 55 56 while(c[lc] == 0 && lc > 1) lc--; 57 if(flag == 1) printf("-"); 58 //如果是負數先輸出負號 59 for(int i = lc; i > 0; i--) 60 printf("%d",c[i]); 61 return 0; 62 }
****高精度乘法****
題目：求兩個不超過200位的非負整數的積.
求解a*b,如下圖所示為a4a3a2a1 * b2b1的計算程序,可見c1=a1*b1,c2=a2*b1+a1*b2,c3=a3*b1+a2*b2,c4=a4*b1+a3*b2,
c5=a4*b2,經過分析可以得到圖中紫色部分結論，ai*bj對應位為ci+j-1.乘法運算同樣需要滿足加法高精度中的規則.
具體代碼如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 char s1[2005],s2[2005]; 5 int a[2005],b[205],c[2005]; 6 7 int main(void) 8 { 9 int la,lb,lc; 10 scanf("%s",s1); 11 scanf("%s",s2); 12 13 la = strlen(s1); 14 lb = strlen(s2); 15 lc = la + lb; 16 17 for(int i = 0; i < la; i++) 18 a[la-i] = s1[i] - '0'; 19 for(int i = 0; i < lb; i++) 20 b[lb-i] = s2[i] - '0'; 21 22 for(int i = 1; i <= la; i++) 23 { 24 for(int j = 1; j <= lb; j++) 25 { 26 c[i+j-1] += a[i]*b[j]; 27 c[i+j] = c[i+j-1] / 10; 28 c[i+j-1] %= 10; 29 } 30 } 31 32 if(c[lc] == 0 && lc > 0) lc --; 33 for(int i = lc; i > 0; i--) 34 printf("%d",c[i]); 35 36 return 0; 37 }
****高精度除法****
題目1：https://www.luogu.com.cn/problem/P1480
A/B需要考慮高精度/高精度和高精度/低精度兩種情況,高精度除以低精度采用逐位試商法;高精度除以高精度采用減法模擬除法.
如下圖所示，針對題目1的a÷b，a為大數（高精度，陣列模擬），b為小數（long long型別）
題目1中的代碼具體如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 char s1[5005]; 5 long long b,c[5005],a[5005],la,lc; 6 7 int main(void) 8 { 9 long long x = 0; 10 scanf("%s",s1);//被除數 11 scanf("%d",&b);//除數 12 13 la = strlen(s1); 14 //區別于其他加減乘操作 15 //將如輸入的1234字符依次按順序 16 //放入a陣列中 17 for(int i = 1; i<=la; i++) 18 a[i] = s1[i-1] -'0'; 19 20 for(int i = 1; i <= la; ++i) 21 //商最多有la位 22 { 23 c[i] = (x * 10 + a[i]) / b; 24 x = (x * 10 + a[i]) % b; 25 } 26 27 //洗掉前導零 28 lc = 1; 29 while(c[lc] == 0 && lc < la) 30 lc++; 31 32 for(int i = lc; i <= la; ++i) 33 printf("%d",c[i]); 34 35 return 0; 36 }
下面對高精度除以高精度的情況進行分析，舉個案例解釋，如531518/123的案例，531518為高精度被除數，123設為很大的高精度除數，這時可以采用下圖的①-④步驟進行處理，即將531518和填補至相同位數的123000進行減法處理，經過四次減法后得到的數的位數要比原來531518的位數即6位小，因此4作為商的最高位，次高位等位的處理如后續②③④同理可得， 
//高位c[4]的來源 a = 531518; tmp = 123000;（將123左移3位） while a >= tmp: c[4]++; a = a - tmp;（需要用到高精度減法） //c[3]的來源 a=39518; tmp=12300;（將123左移兩位） while a >= tmp: c[3]++; a = a - tmp;（需要用到高精度減法） //c[2]的來源 a=2618; tmp=1230;（將123左移1位） while a >= tmp: c[2]++; a = a - tmp;（需要用到高精度減法） //c[1]的來源 a=158; tmp=123;（將123左移0位） while a >= tmp: c[1]++; a = a - tmp;（需要用到高精度減法） //上述結構可以用以下回圈表示： a = 531518; for(i=lc;i>=1;i--) { tmp=0； tmp=123 左移 i-1位； while a >= tmp: c[i]++; a = a - tmp;（需要用到高精度減法） }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253425.html
標籤：其他
上一篇：貪心演算法
下一篇：世上最可愛的人生謊言