程序設(shè)計(jì)實(shí)習(xí)講義

程序設(shè)計(jì)實(shí)習(xí)

第四講高精度計(jì)算1/33例題：ai2981大整數(shù)加法(P159)問題描述求兩個(gè)不超出200位非負(fù)整數(shù)和。輸入數(shù)據(jù)有兩行，每行是一種不超出200位非負(fù)整數(shù)，沒有多出前導(dǎo)0。輸出要求一行，即相加后成果。成果里不能有多出前導(dǎo)0，即假如成果是342，那么就不能輸出為0342。輸入樣例2222222222222222222233333333333333333333輸出樣例555555555555555555552/33例題：ai2981大整數(shù)加法(P159)解題思緒1)用字符型或整型數(shù)組來寄存大整數(shù)an[0]寄存?zhèn)€位數(shù)，an[1]寄存十位數(shù)，an[2]寄存百位數(shù)……2）模擬小學(xué)生列豎式做加法，從個(gè)位開始逐位相加，超出或達(dá)成10則進(jìn)位。

用unsignedan1[201]保存第一種數(shù)，用unsignedan2[200]表達(dá)第二個(gè)數(shù)，然后逐位相加，相加成果直接寄存在an1中。要注意處理進(jìn)位。3/33#include<stdio.h>#include<string.h>#defineMAX_LEN201intan1[MAX_LEN+10];intan2[MAX_LEN+10];charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intAdd(intnMaxLen,int*an1,int*an2)//將長度最多為nMaxLen大整數(shù)an1和an2相加，成果放在an1,//an1[0],an2[0]對應(yīng)于個(gè)位{ intnHighestPos=0; for(inti=0;i<nMaxLen;i++){ an1[i]+=an2[i]; //逐位相加 if(an1[i]>=10){ //看是否要進(jìn)位 an1[i]-=10; an1[i+1]++; //進(jìn)位 } if(an1[i]) nHighestPos=i;//統(tǒng)計(jì)最高位位置 } returnnHighestPos;}4/33intmain(){ scanf("%s",szLine1);scanf("%s",szLine2); inti,j; //庫函數(shù)memset將地址an1開始sizeof(an1)字節(jié)內(nèi)容置成0 //sizeof(an1)值就是an1長度 //memset函數(shù)在string.h中申明 memset(an1,0,sizeof(an1)); memset(an2,0,sizeof(an2)); //下面將szLine1中存放字符串形式整數(shù)轉(zhuǎn)換到an1中去， //an1[0]對應(yīng)于個(gè)位 intnLen1=strlen(szLine1); for(j=0,i=nLen1-1;i>=0;i--) an1[j++]=szLine1[i]-'0'; intnLen2=strlen(szLine2); for(j=0,i=nLen2-1;i>=0;i--) an2[j++]=szLine2[i]-'0'; intnHighestPos=Add(MAX_LEN,an1,an2); for(i=nHighestPos;i>=0;i--)printf("%d",an1[i]); return0;}5/33例題：ai2736大整數(shù)減法問題描述求2個(gè)大正整數(shù)相減差輸入數(shù)據(jù)第1行是測試數(shù)據(jù)組數(shù)n，每組測試數(shù)據(jù)占2行，第1行是被減數(shù)a，第2行是減數(shù)b(a>b)。每組測試數(shù)據(jù)之間有一種空行，每行數(shù)據(jù)不超出100個(gè)字符輸出要求n行，每組測試數(shù)據(jù)有一行輸出是對應(yīng)整數(shù)差6/33例題：ai2736大整數(shù)減法輸入樣例29999999999999999999999999999999999999999999999999954096567750978508956870567980689709345465465756767686784354353451輸出樣例999999999999999999999999000000000000054096567750978508956870567980689709345465465756767686784354353447/33#include<stdio.h>#include<string.h>#defineMAX_LEN110intan1[MAX_LEN];intan2[MAX_LEN];charszLine1[MAX_LEN];charszLine2[MAX_LEN];intSubstract(intnMaxLen,int*an1,int*an2){//兩個(gè)最多nMaxLen位大整數(shù)an1減去an2,an1確保大于an2 intnStartPos=0; for(inti=0;i<nMaxLen;i++){ an1[i]-=an2[i];//逐位減 if(an1[i]<0){//看是否要借位 an1[i]+=10; an1[i+1]--;//借位 } if(an1[i]) nStartPos=i;//統(tǒng)計(jì)最高位位置 } returnnStartPos;//返回值是成果里面最高位位置}8/33intmain(){ intn; scanf("%d",&n); while(n--){ scanf("%s",szLine1); scanf("%s",szLine2); inti,j; memset(an1,0,sizeof(an1)); memset(an2,0,sizeof(an2)); //下面將szLine1中存放字符串形式整數(shù)轉(zhuǎn)換到an1中去， //an1[0]對應(yīng)于個(gè)位 intnLen1=strlen(szLine1); for(j=0,i=nLen1-1;i>=0;i--) an1[j++]=szLine1[i]-'0'; intnLen2=strlen(szLine2); for(j=0,i=nLen2-1;i>=0;i--) an2[j++]=szLine2[i]-'0'; intnStartPos=Substract(MAX_LEN,an1,an2); for(i=nStartPos;i>=0;i--) printf("%d",an1[i]); printf("\n"); }return0;}9/33例題：ai2980大整數(shù)乘法

問題描述求兩個(gè)不超出200位非負(fù)整數(shù)積。輸入數(shù)據(jù)有兩行，每行是一種不超出200位非負(fù)整數(shù)，沒有多出前導(dǎo)0。輸出要求一行，即相乘后成果。成果里不能有多出前導(dǎo)0，即假如成果是342，那么就不能輸出為0342。輸入樣例1234567890098765432100輸出樣例121932631112635269000010/33解題思緒用unsignedan1[200]和unsignedan2[200]分別寄存兩個(gè)乘數(shù)，用aResult[400]來寄存積。計(jì)算中間成果也都存在aResult中。aResult長度取400是由于兩個(gè)200位數(shù)相乘，積最多會有400位。an1[0],an2[0],aResult[0]都表達(dá)個(gè)位。一種數(shù)第i位和另一種數(shù)第j位相乘所得數(shù)，一定是要累加到成果第i+j位上。這里i,j都是從右往左，從0開始數(shù)。計(jì)算過程基本上和小學(xué)生列豎式做乘法相同。為編程方便，并不急于處理進(jìn)位，而將進(jìn)位問題留待最后統(tǒng)一處理。11/33現(xiàn)以835×49為例來說明程序計(jì)算過程。先算835×9。5×9得到45個(gè)1，3×9得到27個(gè)10，8×9得到72個(gè)100。由于不急于處理進(jìn)位，因此835×9算完后，aResult如下：接下來算4×5。此處4×5成果代表20個(gè)10，因此要aResult[1]+=20，變?yōu)椋?2/33再下來算4×3。此處4×3成果代表12個(gè)100，因此要aResult[2]+=12，變?yōu)椋鹤詈笏?×8。此處4×8成果代表32個(gè)1000，因此要aResult[3]+=32，變?yōu)椋?3/33乘法過程完成。接下來從aResult[0]開始向高位逐位處理進(jìn)位問題。aResult[0]留下5，把4加到aResult[1]上，aResult[1]變?yōu)?1后，應(yīng)留下1，把5加到aResult[2]上……最后使得aResult里每個(gè)元素都是1位數(shù)，成果就算出來了：14/33#include<stdio.h>#include<string.h>#defineMAX_LEN200unsignedan1[MAX_LEN+10];unsignedan2[MAX_LEN+10];unsignedaResult[MAX_LEN*2+10];charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intmain(){ gets(szLine1);//gets函數(shù)讀取一行 gets(szLine2); inti,j; intnLen1=strlen(szLine1); memset(an1,0,sizeof(an1)); memset(an2,0,sizeof(an2)); memset(aResult,0,sizeof(aResult)); j=0; for(i=nLen1-1;i>=0;i--) an1[j++]=szLine1[i]-'0'; intnLen2=strlen(szLine2); j=0; for(i=nLen2-1;i>=0;i--) an2[j++]=szLine2[i]-'0';15/33 //每一輪都用an2一位，去和an1各位相乘，從an1個(gè)位開始 for(i=0;i<nLen2;i++) { //用選定an2那一位，去乘an1各位 for(j=0;j<nLen1;j++)

//兩數(shù)第i,j位相乘，累加到成果第i+j位 aResult[i+j]+=an2[i]*an1[j]; } //下面循環(huán)統(tǒng)一處理進(jìn)位問題 intnHighestPos=0; for(i=0;i<MAX_LEN*2;i++) { if(aResult[i]>=10){ aResult[i+1]+=aResult[i]/10; aResult[i]%=10; } if(aResult[i]) nHighestPos=i; } for(i=nHighestPos;i>=0;i--) printf("%d",aResult[i]); return0;}16/33例題：ai2737大整數(shù)除法(P165)求兩個(gè)大正整數(shù)相除商基本思想是反復(fù)做減法，看看從被除數(shù)里最多能減去多少個(gè)除數(shù)，商就是多少。一種一種減顯然太慢，如何減得更加快某些呢？以7546除以23為例來看一下：開始商為0。先減去23100倍，就是2300，發(fā)覺夠減3次，余下646。于是商值就增加300。然后用646減去230，發(fā)覺夠減2次，余下186，于是商值增加20。最后用186減去23，夠減8次，因此最后商就是328。因此本題關(guān)鍵是要寫一種大整數(shù)減法函數(shù)，然后反復(fù)調(diào)用該函數(shù)進(jìn)行減法操作。17/33求2個(gè)大正整數(shù)相除商Input

第1行是測試數(shù)據(jù)組數(shù)n，每組測試數(shù)據(jù)占2行，第1行是被除數(shù)，第2行是除數(shù)。每組測試數(shù)據(jù)之間有一種空行，每行數(shù)據(jù)不超出100個(gè)字符Output

n行，每組測試數(shù)據(jù)有一行輸出是對應(yīng)整數(shù)商SampleInput

324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451SampleOutput

010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345例題：ai2737大整數(shù)除法(P165)18/33例題：ai2737大整數(shù)除法(P165)基本思想是反復(fù)做減法，看看從被除數(shù)里最多能減去多少個(gè)除數(shù)，商就是多少。一種一種減顯然太慢，如何減得更加快某些呢？以7546除以23為例來看一下：開始商為0。先減去23100倍，就是2300，發(fā)覺夠減3次，余下646。于是商值就增加300。然后用646減去230，發(fā)覺夠減2次，余下186，于是商值增加20。最后用186減去23，夠減8次，因此最后商就是328。因此本題關(guān)鍵是要寫一種大整數(shù)減法函數(shù)，然后反復(fù)調(diào)用該函數(shù)進(jìn)行減法操作。19/33#include<stdio.h>#include<string.h>#defineMAX_LEN110intan1[MAX_LEN];intan2[MAX_LEN];inttmpAn2[MAX_LEN];intanResult[MAX_LEN];charszLine1[MAX_LEN];charszLine2[MAX_LEN];charszNouse[MAX_LEN];intSubstract(intnMaxLen,int*an1,int*an2)//大整數(shù)an1減去an2。二者最多nMaxLen位，an1必須大于an2,差放在an1里//返回差最高非0位位置{ intnStartPos=0; for(inti=0;i<nMaxLen;i++){ an1[i]-=an2[i]; //逐位相 if(an1[i]<0){ //看是否要進(jìn)位 an1[i]+=10; an1[i+1]--; //進(jìn)位 } if(an1[i]) nStartPos=i;//記錄最高位位置 } returnnStartPos;}20/33intLength(intnMaxLen,int*an)//求大整數(shù)位數(shù)。0算0位{ inti; for(i=nMaxLen-1;an[i]==0&&i>=0;i--); if(i>=0) returni+1; return0;}voidShiftLeft(intnMaxLen,int*an1,int*an2,intn)//將大整數(shù)an1左移n位，即乘以10n次方，成果放到an2里{ memcpy(an2,an1,nMaxLen*sizeof(int)); if(n<=0) return; for(inti=nMaxLen-1;i>=0;i--) if(i-n>=0) an2[i]=an1[i-n]; else an2[i]=0;}21/33int*Max(intnMaxLen,int*an1,int*an2)//求大整數(shù)an1和an2里面大那個(gè)//假如都是0，則返回NULL{ boolbBothZero=true; for(inti=nMaxLen-1;i>=0;i--){ if(an1[i]>an2[i]) returnan1; elseif(an1[i]<an2[i]) returnan2; elseif(an1[i]) bBothZero=false; } if(bBothZero) returnNULL; returnan1;}22/33intmain(){ intn; scanf("%d",&n); gets(szNouse); while(n--){ gets(szLine1); gets(szLine2); gets(szNouse); inti,j; //庫函數(shù)memeset將地址an1開始sizeof(an1)字節(jié)內(nèi)容置成0 //sizeof(an1)值就是an1長度 //memset函數(shù)在string.h中申明 memset(an1,0,sizeof(an1)); memset(an2,0,sizeof(an2)); //下面將szLine1中存放字符串形式整數(shù)轉(zhuǎn)換到an1中去， //an1[0]對應(yīng)于個(gè)位 intnLen1=strlen(szLine1); for(j=0,i=nLen1-1;i>=0;i--) an1[j++]=szLine1[i]-'0'; intnLen2=strlen(szLine2); for(j=0,i=nLen2-1;i>=0;i--) an2[j++]=szLine2[i]-'0';23/33 intnHighestPos=0; memset(anResult,0,sizeof(anResult)); intnShiftLen=Length(MAX_LEN,an1)-Length(MAX_LEN,an2); //只要an1大于an2，就不停相減 while(Max(MAX_LEN,an1,an2)==an1){ //算出an110nShiftLen次方倍 ShiftLeft(MAX_LEN,an2,tmpAn2,nShiftLen); //反復(fù)減去an110nShiftLen次方倍，看能減幾次 while(Max(MAX_LEN,an1,tmpAn2)==an1){ Substract(MAX_LEN,an1,tmpAn2); //統(tǒng)計(jì)商對應(yīng)位 anResult[nShiftLen]++; } //統(tǒng)計(jì)成果最高位位置 if(nHighestPos==0&&anResult[nShiftLen]) nHighestPos=nShiftLen; nShiftLen--; } for(i=nHighestPos;i>=0;i--) printf("%d",anResult[i]); printf("\n"); }return0;}24/33例題：ai2952循環(huán)數(shù)問題描述當(dāng)一種N位整數(shù)X滿足下列條件時(shí)，稱其為循環(huán)數(shù)：X與任意一種整數(shù)1≤Y≤N相乘時(shí)，都將產(chǎn)生一種X“循環(huán)”。即：分別將這兩個(gè)整數(shù)第1位數(shù)字與最后1位數(shù)字連在一起，能夠得到一種相同數(shù)字循環(huán)；當(dāng)然兩個(gè)整數(shù)在該數(shù)字循環(huán)中起始位置不一樣。例如，142857是一種循環(huán)數(shù)142857*1=142857

142857*2=285714

142857*3=428571

142857*4=571428

142857*5=714285

142857*6=85714225/33輸入寫一種程序判斷一種整數(shù)是否是循環(huán)數(shù)。輸入文獻(xiàn)是一種整數(shù)序列，每個(gè)整數(shù)長度為2~60。注意：每個(gè)整數(shù)前面零被看作是該整數(shù)一部分，在計(jì)算N時(shí)要統(tǒng)計(jì)。例如“01”是一種2位整數(shù)，而“1”是一種1位整數(shù)。輸出對每個(gè)輸入整數(shù)，輸出一行，說明該整數(shù)是否是循環(huán)數(shù)。26/33樣例輸入142857142856142858010588235294117647樣例輸出142857iscyclic142856isnotcyclic142858isnotcyclic01isnotcyclic0588235294117647iscycl27/33解題思緒高精度乘法：整數(shù)也許達(dá)60位X*1:Y0=X;X*2:Y1=Y0+XX*3:Y2=Y1+X……Yi是否是X“循環(huán)”？28/33解題思緒:Yi是否是X“循環(huán)”？窮舉：N位整數(shù)，循環(huán)移位能夠有N種也許循環(huán)移位辦法：Yi是否是“XX”子串？12345671234567\029/33#include<stdio.h>#include<string.h>#defineMAX_LEN201intan1[MAX_LEN+10];intan2[MAX_LEN+10];charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];charszDouble[2*MAX_LEN+10];intAdd(intnMaxLen,int*an1,int*an2)//將長度最多為nMaxLen大整數(shù)an1和an2相加，成果放在an1//an1[0],an2[0]對應(yīng)于個(gè)位{ intnHighestPos=0; for(inti=0;i<nMaxLen;i++){ an1[i]+=an2[i]; //逐位相加 if(an1[i]>=10){ //看是否要進(jìn)位 an1[i]-=10; an1[i+1]++; //進(jìn)位 } if(an1