10高精度計算

1、高精度計算Task：高精度加法高精度減法高精度乘法 高精度乘單精度 高精度乘高精度 高精度除法 高精度除單精度 高精度除高精度Problem 1：a+b=?輸入:a b 輸出:a+b的和輸入輸出樣例：Input: 1 2Input:1234567890 8765432109Output:3Output:9999999999PS:int32: -2147483648.2147483647uint32:0.4294967295Problem 1：a+b=?觀察人工計算的方法：豎式加法223+996-93+6=9 12+9=11,當(dāng)前位1,進位122+9+1=12,當(dāng)前位2,進位1 1進位的1- 1

2、219例題1：高精度加法1553 【問題描述】輸入兩個整數(shù)x,y，輸出它們的和。【文件輸入】輸入兩個整數(shù)x,y（0=x,ys; /讀入字符串s a0=s.length(); /用a0計算字符串s的位數(shù) for(i=1;i=a0;i+)ai=sa0-i-0; /將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲 2、高精度加法 void jia(int a,int b) /計算a=a+b int i,k; if(a0b0)a0=b0; /確定加法最大位數(shù) for(i=1;i=a0;i+)ai+=bi; /逐位相加 for(i=1;i0)a0+;/修正a的位數(shù)(a+b最多只能進一位) 3、高精度結(jié)果的輸出 void

3、 print(int a) /打印輸出 int i; if(a0=0)cout0=1;i-)coutai; coutendl; Problem 2：a-b=?豎式減法：927-896-17-6=1 312-9=3,借位120(9-1)-8=0- 31提示：注意是大數(shù)減小數(shù)例題2：高精度減法1554 Description 輸入兩個整數(shù)x,y，輸出它們的差x-y。Input 輸入兩個整數(shù)x,y（0 = x,y b則為1，ab0)return 1; /a的位數(shù)大于b則a比b大 if(a0=1;i-) /否則a和b的位數(shù)相同，則從高位到低位比較 if(aibi)return 1; if(aibi)r

4、eturn -1; return 0;/各位都相等則兩數(shù)相等。 2、高精度減法 思想：先判斷大小，分情況用大數(shù)減小數(shù)的原則；void jian(int a,int b)/計算a=a-b int flag,i; flag=compare(a,b); /調(diào)用比較函數(shù)判斷大小 if (flag=0) a0=0;return; /相等 if(flag=1) /大于 for(i=1;i=a0;i+) if(aibi) ai+1-;ai+=10; /若不夠減則向上借一位 ai=ai-bi; while(aa0=0) a0-; /修正a的位數(shù) return; if (flag=-1)/小于 則用a=b-a,

5、返回-1 cout-; for(i=1;i=b0;i+) if(biai)bi+1-;bi+=10; /若不夠減則向上借一位 ai=bi-ai; a0=b0; while(aa0=0) a0-; /修正a的位數(shù) return; Problem 3：a*b=?豎式乘法：1. 高精度乘單精度，比如12345*9=?12345* 9- 455*9=45 364*9=36 273*9=27182*9=18+91*9=9- 111105練習(xí)： 輸入N,求N! (1=N=10000)高精度數(shù)乘以單精度 void chengdan(int a,int k) /a=a*k,k是單精度數(shù) int i; for(

6、i=1;i=a0;i+)ai=ai*k;/先每位乘起來 for(i=1;i0) a0+;aa0+1=aa0/10;aa0=aa0%10; /處理最高位相乘的進位 Problem 3：a*b=?豎式乘法：2. 高精度乘高精度，比如12345*12345=?問題轉(zhuǎn)化為若干個高精度乘單精度之和例題3：高精度乘法1555 Description 輸入兩個整數(shù)x,y，輸出它們的積。Input 輸入兩個整數(shù)x,y（0 = x,y = 10100）Output 輸出它們的積Sample Input 11 12 Sample Output 132 高精度數(shù)乘以高精度 void chenggao(int a,i

7、nt b,int c) int i,j,len; for(i=1;i=a0;i+) for(j=1;j=b0;j+)ci+j-1+=ai*bj; c0=a0+b0; /位數(shù)最多為兩個高精度為數(shù)之和 for(i=1;i0&cc0=0)c0-;Problem 4：a/b=?豎式除法 36 12345 452678 3703512345*3=37035 823245267-37035=8232 82328下一位再次減法 7407012345*6=74070 825882328-74070=8258 余數(shù)例題4：高精度除單精度1556 Description 輸入兩個整數(shù)x,y，輸出它們的商。Inpu

8、t 輸入兩個整數(shù)x,y（0 = x = 10100，y =1;i-) /按照由高位到底位的順序,逐位相除 d=d*10+ai; /接受了來自第i+1位的余數(shù) ci=d/b; /計算商的第i位 d=d%b; /計算第i位的余數(shù) c0=a0; while(c00&cc0=0)c0-;/計算商的有效位數(shù) 高精度數(shù)除以單精度-優(yōu)化 void chudan(int a,int b) int i,d=0; for(i=a0;i=1;i-)/按照由高位到底位的順序,逐位相除 d=d*10+ai; /接受了來自第i+1位的余數(shù) ai=d/b; /計算商的第i位 d=d%b; /計算第i位的余數(shù) while(a

9、00&aa0=0)a0-;/計算商的有效位數(shù) 例題5：高精度除高精度1557 Description 輸入兩個整數(shù)x,y，輸出它們的商和余數(shù)。Input 輸入兩個整數(shù)x,y（0 = x,y = 10100）Output 輸出共計兩行，第一行為它們的商，第二行為他們的余數(shù)Sample Input 123 12 Sample Output 10 3 高精度除高精度 void numcpy(int b,int tmp,int i)/復(fù)制b數(shù)組到tmp數(shù)組從i開始 for(int j=1;j0;i-) memset(tmp,0,sizeof(tmp);/數(shù)組清零 numcpy(b,tmp,i); wh

10、ile(compare(a,tmp)=0)ci+;jian(a,tmp);/用減法模擬 while(c00&cc0=0)c0-; 例題6：求n! 1570 Description 精確計算n的階乘n!（1 = n 350）Input 輸入nOutput 輸出n的階乘的值Sample Input 3 Sample Output 6 例題7：回文數(shù)（NOIP1999普及）1267 【問題描述】 若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個 10進制數(shù) 56，將 56加 65（即把56從右向左讀），得到 121是一個回文數(shù)。 又如，對于10進制數(shù)87： STEPl:8778=165； STEP2:165561= 726； STEP3:7266271