高精度算法課件

高精度運(yùn)算High-precisionAlgorithm基本整數(shù)類型的取值范圍類型數(shù)值范圍占字節(jié)數(shù)

unsignedchar0..2551char-128..1271

int(long)-2147483648..21474836471094unsignedint(long)0..42949672954longlong-9223372036854775808..922337203685477580710188unsigned0..184467440737095516158Longlong

使用時(shí)有限制，例如，不能作為數(shù)組的下標(biāo)等。為什么需要高精度運(yùn)算當(dāng)要處理的數(shù)據(jù)超過了任何一種數(shù)據(jù)類型所能容納的范圍,這種數(shù)稱為高精度數(shù),必須自定義類型來存儲.同時(shí)還要自行編寫高精度數(shù)的運(yùn)算函數(shù)(加\減\乘\除等)高精度數(shù)的輸入和存儲在運(yùn)算對象的數(shù)值范圍為任何數(shù)據(jù)類型所無法容納的情況下,采用數(shù)組（每一個(gè)元素對應(yīng)一位十進(jìn)制數(shù)，由其下標(biāo)順序指明位序號）來表示一個(gè)數(shù),就稱為高精度數(shù)。1、采用字符串形式輸入，并將其轉(zhuǎn)化為整數(shù)數(shù)組。2、用一個(gè)整型變量記錄數(shù)據(jù)的實(shí)際長度（即數(shù)組的元素個(gè)數(shù)）字符串到整數(shù)數(shù)組的轉(zhuǎn)換字符串存儲時(shí),數(shù)的高位被存放在字符串的低位。76321801234567轉(zhuǎn)換成整數(shù)數(shù)組時(shí)，要把高精度數(shù)的低位“還原”到數(shù)組的低位。這樣才便于后續(xù)計(jì)算。a[1]存放最低位，a[6]存放最高位。高精度數(shù)的位數(shù)可存放在a[0]中。也可以另用一個(gè)變量存放。字符串s681236701234567整型aconstintMAXLEN=241; //最大長度為240位typedef

int

hp[MAXLEN]; //定義hp為高精度類型voidStr2hp(strings,hp&a)//s轉(zhuǎn)換后存入a{

inti,len;

memset(a,0,sizeof(a));//cleara

len=s.size(); a[0]=len; //savethelength for(i=0;i<len;i++) //convert

a[len-i]=s[i]-'0';}高精度數(shù)類型定義與讀入輸出voidPrint(hpa){

inti,len;

len=a[0]; //getthelength for(i=len;i>=1;i--)

cout<<a[i];

cout<<endl;}高精度加法問題描述：輸入a，b（<10240）兩個(gè)數(shù)，輸出a+b的值。樣例輸入：9999999999999999999912345678901234567890樣例輸出：112345678901234567889算法分析算法思想類似于豎式加法運(yùn)算，注意進(jìn)位處理。把計(jì)算結(jié)果存到c中：(1)先計(jì)算：直接將a[i]和b[i]相加，結(jié)果放在c[i]中。…….a[3]a[2]a[1]…….b[3]b[2]b[1]+……c[3]c[2]c[1]思考：要進(jìn)行多少位加法呢？應(yīng)該取a或b中較長的位數(shù)。對10進(jìn)制而言，c[i]中的數(shù)可能的取值范圍是什么？合要求的取值范圍是什么？需要作什么處理？算法分析(2)處理進(jìn)位從最低位開始，逐位整理：把本位模10，向高一位進(jìn)位：

c[i+1]+=c[i]/10;

c[i]=c[i]%10;思考：最多要處理多少位呢？因?yàn)閮蓴?shù)相加最多向前進(jìn)一位，所以我們把長度加1。len++;for(i=1;i<len;i++)//注意是i<len,寫成i<=len結(jié)果不錯(cuò)，但道理不對{

c[i+1]+=c[i]/10;

c[i]=c[i]%10;}算法分析(3)去掉最高位的0因?yàn)閮蓴?shù)相加,也可能不產(chǎn)生進(jìn)位，因此要把這種情況下最高位的0去掉，其實(shí)就是減小和的長度len的值。While((len>1)&&(c[len]==0))

len--;注意，len>1的條件是必要的，因?yàn)槿绻褪?的話，想一想該如何保存。voidadd(hpa,hpb,hp&c)//Adda,btoc{hpd;

inti,len;

memset(d,0,sizeof(d));//d清0

if(a[0]>b[0])len=a[0];//求和的位數(shù)

elselen=b[0];for(i=1;i<=len;i++)//逐位相加

d[i]=a[i]+b[i];

len++;//位數(shù)加1

for(i=1;i<len;i++)//處理進(jìn)位{

d[i+1]+=d[i]/10;

d[i]%=10;}while((len>1)&&(d[len]==0))//處理最高位

len--;d[0]=len;

memcpy(c,d,sizeof(d));//保存結(jié)果}思考：能不能不用d，直接讓c參與加法運(yùn)算呢？提示：結(jié)果要保存在a或b中,即Add(a,b,a),不用d行嗎？高精度減法運(yùn)算問題表述：

輸入a，b（<10240）兩個(gè)數(shù)，輸出a-b的值。樣例2輸入：9991000樣例2輸出：-1樣例1輸入：456409樣例1輸出：47算法分析1、比較a和b的大小，從而確定結(jié)果的正負(fù)號2、依照由低位至高位的順序進(jìn)行減法運(yùn)算。在每一次位運(yùn)算中，若出現(xiàn)不夠減的情況(a[i]<b[i])，則向高位借位。在進(jìn)行了減運(yùn)算后，若高位為0，則要減少結(jié)果的長度。在具體計(jì)算過程中，仍然用三位走的辦法。voidsub(hpa,hpb,hp&c)//amustbegreaterthanb{

inti,len; hpd;

memset(d,0,sizeof(d));//cleard

len=a[0]; for(i=1;i<=len;i++)

d[i]=a[i]-b[i];for(i=1;i<=len;i++) if(d[i]<0) //處理借位 {

d[i]+=10; d[i+1]-=1; } while((len>1)&&(d[len]==0))//整理差的長度

len--; d[0]=len;

memcpy(c,d,sizeof(d));}寫程序的小經(jīng)驗(yàn)1、數(shù)組的清零：保存結(jié)果的數(shù)組使用前一般都要清零：For(i=0;i<MAXLEN;i++)

a[i]=0;Memset(a,0,sizeof(a))2、變量的使用要規(guī)范：如：循環(huán)控制變量一般用i、j、k，一般不要用m、n等。長度用len表示。這樣容易找錯(cuò)誤。比較兩個(gè)高精度數(shù)大小當(dāng)a>b，返回1；a<b,返回-1；a==b，返回0int

compare(hpa,hpb){

inti; if(a[0]>b[0])return1; if(a[0]<b[0])return-1; for(i=a[0];i>=1;i--) if(a[i]>b[i])return1; elseif(a[i]<b[i])return-1; return0;}求Fibonacci數(shù)列的第n項(xiàng)Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”(又稱“Fibonacci問題”)。問題的提出：有雌雄一對兔子，假定過兩個(gè)月后便每個(gè)月可繁殖雌雄各一的一對小兔子。問過n個(gè)月后共有多少對兔子？已知：N<=1000F(i):第i個(gè)月后共有的兔子對數(shù)。F(1)=1;F(2)=1;f(3)=2;f(4)=3;f(5)=5;f(6)=8;遞推公式F(i)=f(i-2)+f(i-1)//用基本類型就可解決unsignedlonglong

fibo(intn){ unsignedlonglongf0,f1,t;

inti; if((n==1)||(n==2))return1;f0=1;f1=1; for(i=3;i<=n;i++) { t=f0+f1; f0=f1; f1=t; } returnf1;}當(dāng)N<=93小結(jié):高精度運(yùn)算畢竟比基本類型運(yùn)算麻煩,費(fèi)時(shí)，因此只有在確有必要時(shí)才使用voidfibo(intn,hp&ans){ hpf0,f1,t;

inti;

memset(ans,0,sizeof(ans)); f0[0]=1;f0[1]=1; f1[0]=1;f1[1]=1; if((n==1)||(n==2)) { ans[0]=1; ans[1]=1; return; }

for(i=3;i<=n;i++) { add(f0,f1,t); memcpy(f0,f1,sizeof(f1)); memcpy(f1,t,sizeof(t)); }

memcpy(ans,f1,sizeof(f1));}

小結(jié)：高精度數(shù)不一定非要經(jīng)過“輸入-轉(zhuǎn)換”過程。也可能是通過計(jì)算直接產(chǎn)生。當(dāng)N>93時(shí)高精度數(shù)乘以整型數(shù)運(yùn)算問題表述：精確計(jì)算n的階乘n!（7<n<80）樣例輸入：20樣例輸出：2432902008176640000算法分析估算n!所需的高精度數(shù)組長度被乘數(shù)（高精度）從低位向高位逐位乘以乘數(shù)（整數(shù)）1、估算n!所需的高精度數(shù)組長度因?yàn)?0!<8080<10080=(102)80=10160所以80！可以用160個(gè)數(shù)組元素a[1],a[2],…,a[160]來存放，一個(gè)數(shù)組元素存放一個(gè)數(shù)位上的數(shù)字。同樣的方法，可以估算出100！可以用200位的數(shù)組來存放。n!=1*2*3*…*k*(k+1)*…(n-1)*n可以知道，當(dāng)n大于某個(gè)數(shù)時(shí)，n!將無法再用基本類型裝下，需要用高精度數(shù)來存放，而每次的乘數(shù)則是一個(gè)基本整型，因此求n!的問題是一個(gè)高精度數(shù)乘以一個(gè)基本整型。2.高精度數(shù)乘以整型數(shù)voidmultiply(hpa,int

b,hp&c){hpd;

inti,len,t;

memset(d,0,sizeof(d));

len=a[0];for(i=1;i<=len;i++)

d[i]=a[i]*b;

for(i=1;i<=len;i++){d[i+1]+=d[i]/10;

d[i]%=10;}

len++;while(d[len]){d[len+1]=d[len]/10;

d[len]%=10;

len++;}while((d[len]==0)&&(len>1))

len--;d[0]=len;

memcpy(c,d,sizeof(d));}后一個(gè)for循環(huán)和while循環(huán)都是來處理進(jìn)位用的。為什么要這么麻煩？因?yàn)槲覀儾恢勒麛?shù)b有多少位?？梢詫懸粋€(gè)函數(shù)去求一個(gè)整數(shù)的位數(shù)。然后就可以只用一個(gè)for循環(huán)處理進(jìn)位了。可以把兩個(gè)for循環(huán)合在一塊，象后一頁的程序一樣。2.高精度數(shù)乘以整型數(shù)voidmultiply(hpa,int

b,hp&c){hpd;

inti,len,t;

memset(d,0,sizeof(d));

len=a[0];for(i=1;i<=len;i++){t=a[i]*b+d[i];

d[i]=t%10;d[i+1]=t/10;}

len++;while(d[len]){d[len+1]=d[len]/10;

d[len]%=10;

len++;}while((d[len]==0)&&(len>1))

len--;d[0]=len;

memcpy(c,d,sizeof(d));}intmain(){

intn,i;hpans;

cin>>n;ans[0]=1;ans[1]=1;for(i=2;i<=n;i++)

multiply(ans,i,ans);for(i=ans[0];i>=1;i--)

cout<<ans[i];

cout<<endl;return0;}高精度數(shù)乘以高精度數(shù)樣例輸入：1234567890098765432100樣例輸出：1219326311126352690000問題表述：輸入a，b（<10100）兩個(gè)數(shù)，輸出a*b的值。算法分析1、積的位數(shù)為lena+lenb-1或者lena+lenb；2、如果暫且不考慮進(jìn)位關(guān)系，則ai*bj應(yīng)該累加在積的第j+i-1位上：c[i+j-1]:=a[i]*b[j]+c[i+j-1];3、可以先乘、后處理進(jìn)位1、不考慮進(jìn)位關(guān)系，a[i]*b[j]累加在積的第j+i-1位上，積用c存儲。for(i=1;i<=lena;i++)for(j=1;j<=lenb;j++)c[i+j-1]=c[i+j-1]+a[i]*b[j];83764321228abc8376448505428abc8376453568abc1)b的第1位乘a的各位2)b的第2位乘a的各位3)處理c的各位進(jìn)位2、從低位到高位逐位向前處理進(jìn)位lenc=lena+lenb;for(i=1;i<=lenc;i++){c[i+1]=c[i+1]+c[i]/10;

c[i]=c[i]%10;}while((lenc>1)&&(c[lenc]==0)

lenc--;C[0]=lenc;voidhigh_multiply(hpa,hpb,hp&c){hpd;

inti,j,len;

memset(d,0,sizeof(d));for(i=1;i<=a[0];i++)for(j=1;j<=b[0];j++)d[i+j-1]+=a[i]*b[j];

len=a[0]+b[0]+1;for(i=1;i<=len;i++){d[i+1]+=d[i]/10;

d[i]=d[i]%10;}while((d[len]==0)&&(len>1))

len--;d[0]=len;

memcpy(c,d,sizeof(d));}intmain(){

inti;hpa,b,ans;strings1,s2;

cin>>s1;

cin>>s2;str2hp(s1,a);str2hp(s2,b);

high_multiply(a,b,ans);for(i=ans[0];i>=1;i--)

cout<<ans[i];

cout<<endl;return0;}高精度數(shù)除以整型數(shù)問題表述：輸入a（<10240），b（<109）兩個(gè)數(shù)，輸出a/b的值和余數(shù)。樣例輸入：998877665544332211002001920樣例輸出：498959831334081077740算法分析1、基本方法是從被除數(shù)的最高位開始，逐位計(jì)算商和余數(shù)。存儲商。余數(shù)則轉(zhuǎn)移到下一次的被除數(shù)中。注意在下一次的計(jì)算中，余數(shù)