第三章-算法優(yōu)秀文檔

第三章算法設(shè)計3．3算法優(yōu)化基本技巧

3．3．1算術(shù)運算的妙用3．3．2標(biāo)志量的妙用3．3．3信息數(shù)字化3．3．1算術(shù)運算的妙用有關(guān)算術(shù)運算的妙用，在前面的許多例題中已有體現(xiàn)。如：上一節(jié)3．2．1“原始信息與處理結(jié)果的巧妙對應(yīng)”中的例2，通過算術(shù)運算把數(shù)據(jù)信息歸類后與下標(biāo)對應(yīng)。通過恰當(dāng)?shù)乃阈g(shù)運算可以很好地提高編程效率，以及相關(guān)算法的運行效率。【例1】一次考試，共考了五門課。統(tǒng)計五十個學(xué)生中至少有三門課成績高于90分的人數(shù)。算法設(shè)計：1）對每個同學(xué)，先計算其成績高于90分的課程數(shù)目，若超過3，則累加滿足條件的人數(shù)中。2）用二重循環(huán)實現(xiàn)以上過程，外層循環(huán)模擬50個同學(xué)，內(nèi)層循環(huán)模擬五門課程。main(){inta[5],i,j,s,num=0;for(i=1;i<=50;i=i+1){s=0;for(j=0;j<=4;j=j+1){input(a[j]);

if(a[j]>=90)s=s+1;}if(s>=3)num=num+1;}print(“Thenumberis”,num);}算法如下：算法說明：對于計算其成績高于90分的課程數(shù)目，還可以簡單地這樣實現(xiàn)：

s=0；for(j=0;j<=4;j++){input(“a[j]);s=s+(a[i]>=90);}【例2】開燈問題：有從1到n依次編號的n個同學(xué)和n盞燈。1號同學(xué)將所有的燈都關(guān)掉；2號同學(xué)將編號為2的倍數(shù)的燈都打開；3號同學(xué)則將編號為3的倍數(shù)的燈作相反處理（該號燈如打開的，則關(guān)掉；如關(guān)閉的，則打開）；以后的同學(xué)都將自己編號的倍數(shù)的燈，作相反處理。問經(jīng)n個同學(xué)操作后，哪些燈是打開的？問題分析：1）用數(shù)組表示某種狀態(tài)，這里定義有n個元素的a數(shù)組，它的每個下標(biāo)變量a[i]視為一燈，i表示其編號。a[i]=1表示燈處于打開狀態(tài)，a[i]=0表示燈處于關(guān)閉狀態(tài)。2）實現(xiàn)將第i燈作相反處理的操作，可以用條件語句if表示：當(dāng)a[i]為1時，a[i]被重新賦為0；當(dāng)a[i]為0時，a[i]被重新賦為1。但通過以下算術(shù)運算：a[i]=1-a[i]

可以很好地模擬“開關(guān)”燈的操作。main(){intn,a[1000],i,k;print(“inputanumber”);input(“%d”,&n);for(i=1;i<=n;i++)a[i]=0;for(i=2;i<=n;i++){k=1;while(i*k<=n){a[i*k]=1-a[i*k];k=k+1;}}for(i=1;i<=n;i++)print(a[i]);}算法說明：算法中第二個for循環(huán)i枚舉的不是燈的編號，而是編號為i的同學(xué),其內(nèi)層循環(huán)中,就將包含i因素的燈的編號為“i*k”的燈，改變其狀態(tài)。【例3】右圖中所示的圓圈中，我們把相隔一個數(shù)據(jù)的兩個數(shù)（如1和10，3和5，3和6）稱作是“一對數(shù)”，試編程求出乘積最大的一對數(shù)和乘積最小的一對數(shù)。輸出格式如下：max：?*?=?min：?*?=?其中？表示：找到的滿足條件的數(shù)和乘積。for(i=1;i<=n;i++)這樣d除以7的余數(shù)與c相同。【例】樓梯上有n階臺階，上樓可以一步上1階，也可以一步上2階，編寫算法計算共有多少種不同的上樓梯方法。【例】編程完成下面給“余”猜數(shù)的游戲：if(k>max){if(n=1)return(1);{inta[100],i,j,n,k,temp;coeff(inta[],intn)其特征根為x1=3,x2=-1否則，i不是任意一個數(shù)的因數(shù)，為了提高運行效率再一次找出去除因數(shù)后，三個數(shù)的最大值，以決定是否繼續(xù)for循環(huán)。{n=n-3;m=m+3;}針對某一具體數(shù)據(jù)，問題的規(guī)模對時間的影響微乎其微。{inta,b,c,d;1）題目中的數(shù)據(jù)有前后“位置”關(guān)系，因此必須用數(shù)組來存儲。設(shè)數(shù)組定義為a[num]，則有a[0]—a[num-1]共num個元素。2）用i代表下標(biāo)，題目就是順序?qū)（i-1）與a（i+1）相乘，求出乘積的最大值和最小值即可。算法設(shè)計：3）關(guān)鍵問題是使:i=num-1時，保證i+1的“值”是0；當(dāng)i=0時，保證i-1的“值”是num-1.把數(shù)組當(dāng)成圓圈操作通過求余運算很容易實現(xiàn)將線性的數(shù)組當(dāng)成圓圈操作：i=num-1時，(i+1)%num等于0；當(dāng)i=0時,(num+i-1)%num等于num-1，且這樣的表達式當(dāng)i為其它值時也是同樣適用的。通過求余運算，“避免了”判別數(shù)組起點與終點的操作。4）用變量Max記錄當(dāng)前最大的乘積，m、n為對應(yīng)的兩個乘數(shù)；變量min記錄當(dāng)前最小的乘積，s、t為對應(yīng)的兩個乘數(shù)。main(){intmax=1,min=32767,a[100],num,i,k,m,n,s,t;print(“inputanumber”);input(num);for(i=0;i<num;i=i+1)input(a[i]);for(i=0;i<num;i=i+1){p=(num+i-1)modnum；q=(i+1)modnum；k=a[p]*a[q];if(k>max){max=k;m=a[p];n=a[q];}if(k<min){min=k;s=a[p];t=a[q];}}print(”max=”m,”*”,n,”=”,max);print(”min=”s,”*”,t,”=”,min);}算法如下：3．3．2標(biāo)志量的妙用【例1】冒泡排序算法的改進問題分析：假設(shè)原有的數(shù)據(jù)本來就是從小到大有序的，則原有算法仍要做n-1趟比較操作，事實上一趟比較下來，若發(fā)現(xiàn)沒有進行過交換，就已經(jīng)說明數(shù)據(jù)已全部有序，無需進行其后的比較操作了。當(dāng)發(fā)現(xiàn)某趟沒有交換后就停止下一趟的比較操作。用標(biāo)志量來記錄每趟交換數(shù)據(jù)的情況:如flag=0表示沒有進行過交換，一但有數(shù)據(jù)進行交換則置flag為1，表示已進行過交換。當(dāng)一趟比較交換完成后，若flag仍為0時，則無需進行下一趟操作，否則若flag為1時，只能繼續(xù)進行下一趟操作。main(){inti,j,t,n,a[100],flag;print(“inputdatanumber(<100):”);input(n);print(“inputdata:”,n);for(i=0;i<n;i++)input(a[i]);flag=1;for(i=1;i<=n-1andflag==1;i++)//比較趟數(shù)最高為n-1趟{flag=0;for(j=n-1;j>=i;j--)//數(shù)組的起始與終止下標(biāo) if(a[j]<a[j-1]){t=a[j];a[j]=a[j-1];a[j-1]=t;flag=1;}for(i=0;i<n;i++) print(a[i]);}}改進后的算法如下：//每次將小數(shù)向上冒出,則前面的數(shù)已有序,下一趟的冒泡則不必再比較.例如第一次循環(huán)將最小數(shù)冒出到a[0],所以下次循環(huán)時則a[0]不必再參與比較算法說明：1）排序前“for(i=1;i<=n-1andflag==1;i++)，for循環(huán)之前”的flag=1;是為了保證循環(huán)的開始。2）內(nèi)層循環(huán)外的flag=0;是假設(shè)這趟比較中沒有交換，一但發(fā)生交換操作在內(nèi)層循環(huán)中就置flag=1;，以保證繼續(xù)下一趟操作。問題分析：

這里要判定n個數(shù)互不相等，是無任何限定的數(shù)據(jù)。If(a[0]<>a[1])and(a[0]<>a[2])and(a[0]<>a[3])and(a[0]<>a[4])and(a[0]<>a[5])and(a[0]<>a[6])and…若用邏輯表達式表示需要：n-1+n-2+n-3+……+1=n*(n-1)/2個關(guān)系表達式。顯然書寫和運行效率都很低。算法設(shè)計：

下面，通過引入標(biāo)志量記錄數(shù)據(jù)是否有重復(fù)的情況，避免了復(fù)雜的邏輯表達式。【例2】編程判定從鍵盤輸入n個數(shù)據(jù)互不相等。算法如下：main(){inta[100],i,j,t,n;input(n);for(i=1;i<=n;i++)input(a[i]);t=1;for(i=1;?;i++)for(?;j<=n;j++)

if(a[i]==a[j]){t=0;break;}if(t=1)print(“Norepeat”);elseprint(“repeat”);}}算法說明：算法中通過二重循環(huán)，交叉比較所有數(shù)據(jù)，用標(biāo)志變量t=0標(biāo)識可能的重復(fù)。若循環(huán)結(jié)束，t仍為1，說明數(shù)據(jù)沒有重復(fù)，互不相同。

i<=n-1j=i+1【例3】輸入三個數(shù)值，判斷以它們的邊長是否能構(gòu)成的三角形，屬于哪種特殊三角形：等邊、等腰、直角。

問題分析：可能的輸出情況：1）不構(gòu)成三角形、2）構(gòu)成等邊三角形、3）構(gòu)成等腰三角形、4）構(gòu)成直角三角形5）構(gòu)成一般三角形。情況1）與其它情況是“否則”關(guān)系，容易分支。情況5）是在三角形不屬于2）3）4）三種情況時的輸出。情況4）與情況3）可能同時輸出。算法設(shè)計：

如何避免情況5）與情況2）3）4）之一同時輸出：

算法如下：

設(shè)置一標(biāo)志變量flag，當(dāng)數(shù)據(jù)能構(gòu)成三角形時flag=0表示情況5）當(dāng)數(shù)據(jù)屬于情況2）3）4）中的一種情況時，flag=1表示構(gòu)成了特殊三角形flag=1:不必輸出“構(gòu)成一般三角形”了；若flag=0，則輸出“構(gòu)成一般三角形”。main(){inta,b,c,flag;print(“Input3number:”);input(a,b,c);if(a>=b+corb>=a+corc>=a+b)print(“don’tformatriangle”);else{flag=0;if(a*a=b*b+c*corb*b=a*a+c*corc*c=a*a+b*b){print(“formaright-angletriangle”);flag=1;}if(a=bandb=c){print(“formaequilateraltriangle”);flag=1;}elseif(a=borb=corc=a){print(“formaequalhaunchtriangle”);flag=1;}

if(flag=0)print(“formatriangle”);}}【例4】編寫算法，求任意三個數(shù)的最小公倍數(shù)。算法設(shè)計：1）用短除法求三個已知數(shù)的最小公倍數(shù)的過程就是求它們的因數(shù)之積，這個因數(shù)可能是三個數(shù)共有的、兩個數(shù)共有或一個數(shù)獨有的三種情況。

2）用算法實現(xiàn)就只能利用嘗試法判斷三個數(shù)含有哪些因數(shù)，及屬于哪種情況。嘗試的范圍:?2——最大數(shù)無論因數(shù)屬于以下三種情況之一，都只算作一個因數(shù)，累乘一次是三個數(shù)的共有的因數(shù)，如：2是2，14，6的因數(shù)；是其中兩個數(shù)的因數(shù)，如：2是2，5，6的因數(shù)；是其中某一個數(shù)的因數(shù)，如：2是2，5，9的因數(shù)。3）再看例子2，4，8中2是的因數(shù)，為避免因數(shù)重復(fù)計算，一定要用2整除這三個數(shù)得到1，2，4。注意到2仍是（1，2，4）的因數(shù)，所以在嘗試某數(shù)是否是三個數(shù)的因數(shù)時，不是用條件語句if，而是要用循環(huán)語句while，以保證將三個數(shù)中所含的某個因數(shù)能全部被找出，直到三個數(shù)都不含這個數(shù)做因數(shù)時循環(huán)結(jié)束。4）由于某數(shù)i是已知三數(shù)的因數(shù)有多種情況，如何表示一個數(shù)是否是這三個數(shù)其中一個數(shù)的因數(shù),或是兩個數(shù)的因數(shù),或是三個數(shù)的因數(shù)?借助3.3.1小節(jié)“算術(shù)運算的妙用”中介紹的方法，用表達式:算法如下：k=(x1modi=０)+(x2modi=0)+(x3modi=0)k=0表示i不是三個數(shù)的因數(shù)，k>0表示i是因數(shù)。

While((x1modi=０)or(x2modi=0)or(x3modi=0))?為避免因數(shù)重復(fù)計算，每次都需要除掉三個整數(shù)中已找到的因數(shù)（即用因數(shù)去除含有它的整數(shù)）。而以上邏輯表達式無法識別i具體是哪一個數(shù)的因數(shù)，要對哪個數(shù)進行整除i的運算。下面我們采用標(biāo)志量的方法，來解決這里的問題。

main(){intx1,x2,x3,t=1,i,flag,x0;print(“Input3number:”);input(x1,x2,x3);x0=max(x1,x2,x3);//嘗試因數(shù)的最大值for(i=2;i<=x0;i=i+1){flag=1;while(flag=1)//是因數(shù)的時候再次尋求是不是再次因數(shù){flag=0;if(x1modi=0){x1=x1/i;flag=1;}if(x2modi=0){x2=x2/i;flag=1;}if(x3modi=0){x3=x3/i;flag=1;}if(flag=1)t=t*i;}//while結(jié)束符x0=max(x1,x2,x3)}//for結(jié)束符print(“Theresultis”,t);}max(intx,inty,intz){if(x>y&&x>z)return(x);elseif(y>xandy>z)return(y);elsereturn(z);}算法說明：在while循環(huán)體外將flag置為1，是為了能進入循環(huán)。一進入循環(huán)馬上將其置為0，表示假設(shè)i不是三個數(shù)的因數(shù)，以下用三個條件語句測試：發(fā)現(xiàn)i是某個數(shù)的因數(shù)，則用因數(shù)去除對應(yīng)整數(shù)，并將flag置為1，表示i是某個數(shù)的因數(shù)；循環(huán)體最后測試flag的值，若為1則累乘i因數(shù)；否則，i不是任意一個數(shù)的因數(shù)，為了提高運行效率再一次找出去除因數(shù)后，三個數(shù)的最大值，以決定是否繼續(xù)for循環(huán)。

3.3.3信息數(shù)字化

從我們學(xué)到的計算機基礎(chǔ)知識知道，計算機能存儲和處理各種多媒體信息，如：圖形、圖象、聲音等，當(dāng)然前提條件是將這些信息進行的數(shù)字化。下面就一些表面上看是非數(shù)值的問題，但經(jīng)過進行數(shù)字化后，就可方便進行算法設(shè)計的問題做簡單介紹。

【例1】警察局抓了a，b，c，d四名偷竊嫌疑犯，其中只有一人是小偷。審問中

a說：“我不是小偷。”

b說：“c是小偷。”

c說：“小偷肯定是d?！?/p>

d說：“c在冤枉人?！?/p>

現(xiàn)在已經(jīng)知道四個人中三人說的是真話，一人說的是假話，

問到底誰是小偷？

問題分析：將a,b,c,d將四個人進行編號，號碼分別為1，2，3，4。則問題可用枚舉嘗試法來解決。

算法設(shè)計：用變量x存放小偷的編號，則x的取值范圍從1取到4，就假設(shè)了他們中的某人是小偷的所有情況。四個人所說的話就可以分別寫成：

a說的話：x<>1

b說的話：x=3

c說的話：x=4

d說的話：x<>4或not(x=4)if((x<>1)+(x=3)+(x=4)+(x<>4)==3)n=int(exp(t*ln(3)));coeff(a,n);問經(jīng)n個同學(xué)操作后，哪些燈是打開的？input(a[i]);數(shù)學(xué)建模就是把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學(xué)知識的這一應(yīng)用過程稱為數(shù)學(xué)建模。2）a、c的系數(shù)能被5整除，且b的系數(shù)被5整除余1；●將最后一個存儲空間的數(shù)據(jù),存儲在臨時存儲空間中；input(t);a[2]=1;}coeff(inta[],intn)算法設(shè)計要點：求(a+b)n（n>1）的各項系數(shù)設(shè)(a+b)n的n+1個系數(shù)為c(i)，(a+b)n-1的系數(shù)設(shè)為c’(i)，則有：if(x2modi=0){x2=x2/i;flag=1;}print(“yournumberdivdedby7hasaremainkerof”);他們的預(yù)測如下：

甲說：學(xué)生A得第一名，學(xué)生B得第三名。{inti,j,t,n,a[100],flag;(a+b)111注意:如何表示表示“四個人中三人說的是真話，一人說的是假話”?

在x的枚舉過程中，當(dāng)這四個邏輯式的值相加等于3時算法如下：main(){intx;for(x=1;x<=4;x++)if((x<>1)+(x=3)+(x=4)+(x<>4)==3)print(chr(64+x),“isathief.”);

}運行結(jié)果：cisathief.【例2】三位老師對某次數(shù)學(xué)競賽進行了預(yù)測。他們的預(yù)測如下：

甲說：學(xué)生A得第一名，學(xué)生B得第三名。

乙說：學(xué)生C得第一名，學(xué)生D得第四名。

丙說：學(xué)生D得第二名，學(xué)生A得第三名。

競賽結(jié)果表明，他們都說對了一半，說錯了一半，并且無并列名次，試編程輸出A、B、C、D各自的名次。

問題分析：用數(shù)1，2，3，4分別代表學(xué)生a，b，c，d獲得的名次。問題就可以利用三重循環(huán)把所有的情況枚舉出來。

算法設(shè)計：1）用a，b，c，d代表四個同學(xué)，其存儲的值代表他們的名次。設(shè)置第一層計數(shù)循環(huán)a的范圍從1到4；設(shè)置第二層計數(shù)循環(huán)b的范圍從1到4；設(shè)置內(nèi)計數(shù)循環(huán)c的范圍從1到來4；d的名次值為?

10-a-b-c。2）問題的已知內(nèi)容，可以表示成以下幾個條件式：(1)(a=1)+(b=3)=1(2)(c=1)+(d=4)=1(3)(d=2)+(a=3)=1若三個條件均滿足，則輸出結(jié)果，若不滿足，繼續(xù)循環(huán)搜索，直至循環(huán)正常結(jié)束。

算法如下：main(){inta,b,c,d;for(a=1;a<=4;a=a+1)for(b=1;b<=4;b=b+1)

if(a<>b)for(c=1;c<=4;c=c+1)

if(c<>aandc<>b)

{d=10-a-b-c;

if(d<>aandd<>bandd<>c)if(((a=1)+(b=3))=1and((c=1)+(d=4))=1and((d=2)+(a=3))=1)print(“a,b,c,d=”,a,b,c,d);}}【例5】編寫算法對輸入的一個整數(shù)，判斷它能否被3，5，7整除，并輸出以下信息之一：（1）

能同時被3，5，7整除；（2）

能被其中兩數(shù)（要指出哪兩個）整除；（3）

能被其中一個數(shù)（要指出哪一個）整除；（4）

不能被3，5，7任一個整除。k=(x1modi=０)+(x2modi=0)+(x3modi=0)main(){longn;intk;print(“Pleaseenteranumber:”);input(n);k=（nmod3=0）+（nmod5=0）+（nmod7=0）switch(k){case3:print(“\nAll”);break;case2:print(“\ntwo”);break;case1:print(“\none”);break;case0:print(“\nnone“);break;}

算法1：

main(){longn;intk;print(“Pleaseenteranumber:”);input(n);k=（nmod3=0）*1+（nmod5=0）*2+（nmod7=0）*4switch(k){case7:print(“All”);bresk;case6:print(“5and7”);break;case5:print(“3and7”);break;case4:print(“7”);break;case3:print(“3and5”);break;case2:print(“5”);break;case1:print(“3”);break;case0:print(“none“);break;}算法2：

算法說明：算法中k表示整除的情況值。算法1中，k的范圍是0——3可以表示四種情況，而算法2中，k的范圍是0——7可以表示八種情況。3．4優(yōu)化算法的數(shù)學(xué)模型3．4．1楊輝三角形的應(yīng)用3．4．2最大公約數(shù)的應(yīng)用3．4．3公倍數(shù)的應(yīng)用3．4．4裴波那契數(shù)列應(yīng)用3．4．5遞推關(guān)系求解方程什么是數(shù)學(xué)建模？已知有五個數(shù)，求前四個數(shù)與第五個數(shù)分別相乘后的最大數(shù)。給出兩個算法分別如下：1．認識數(shù)學(xué)模型和數(shù)學(xué)建模if(tmod2=1)1）一組循環(huán)移動的情況：數(shù)學(xué)建模就是把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學(xué)知識的這一應(yīng)用過程稱為數(shù)學(xué)建模。f(t)=g(t-1)（2）（1）

能同時被3，5，7整除；設(shè)數(shù)組定義為a[num]，則有a[0]—a[num-1]共無論因數(shù)屬于以下三種情況之一，都只算作一個因數(shù)，累乘一次case3:print(“3and5”);break;print(m[t]);2）實現(xiàn)將第i燈作相反處理的操作，可以用條件語句if表個for循環(huán)i枚舉的不是ni=mi—1，mi=3ni—1+2mi—1這樣，一組循環(huán)移動只需一次將數(shù)據(jù)存入輔助存儲空間，其后一次移動只需一次賦值，全部工作大約需要賦值n次就可完成。for(x=1;x<=4;x++)if(a*a=b*b+c*corb*b=a*a+c*corc*c=a*a+b*b)input(a[i]);max1(inta,b,c,d,e)max2(inta,b,c,d,e){intx;{intx

a=a*e;

if(a>b)

b=b*e;x=a;

c=c*e;else

d=d*e;x=b;

if(a>b)if(c>x)x=a;x=c;elseif(d>x)x=b;x=d;

if(c>x)x=x*e;x=c;print(x);

if(d>x)}x=d;print(x);}

操作算法乘法賦值條件判斷Max1473Max2143以上兩個算法基于的數(shù)學(xué)模型是不同的：一個算法先積再求最大值另一個算法先求最大值再求積（優(yōu)）

數(shù)學(xué)建模就是把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學(xué)知識的這一應(yīng)用過程稱為數(shù)學(xué)建模。

2．?dāng)?shù)學(xué)建模的基本方法歸納法：從分析問題的幾種簡單的、特殊的情況中，發(fā)現(xiàn)一般規(guī)律或作出某種猜想，從而找到解決問題的途徑。即從簡單到復(fù)雜，由個別到一般的一種研究方法。3．4．1楊輝三角形的應(yīng)用【例】求n次二項式各項的系數(shù)：已知二項式的展開式為：問題分析：若只用的數(shù)學(xué)組合數(shù)學(xué)的知識，直接建模k=0，1，2，3……n。用這個公式去計算n+1個系數(shù)，即使你考慮到了前后系數(shù)之間的數(shù)值關(guān)系：算法中也要有大量的乘法和除法運算，效率是很低的。數(shù)學(xué)知識是各階多項式的系數(shù)呈楊輝三角形的規(guī)律(a+b)01(a+b)111(a+b)2121(a+b)31331(a+b)414641(a+b)5……則求n次二項式的系數(shù)的數(shù)學(xué)模型就是求n階楊輝三角形。算法設(shè)計要點：求(a+b)n（n>1）的各項系數(shù)設(shè)(a+b)n的n+1個系數(shù)為c(i)，(a+b)n-1的系數(shù)設(shè)為c’(i)，則有：c(1)＝1；c(n+1)＝1(a+b)n的中間各項系數(shù)是(a+b)n-1的相應(yīng)兩項系數(shù)之和則有：

c(i)=c’(i)+c’(i-1)而當(dāng)n=1時，只有兩個系數(shù)c(1)和c(2)(值都為1)對任何n,(a+b)n的二項式系數(shù)可由(a+b)n-1的系數(shù)求得，直到n=1時，兩個系數(shù)有確定值，故可寫成遞歸子算法。

coeff(inta[],intn){if(n==1){a[1]=1;a[2]=1;}else{coeff(a,n-1);a[n+1]=1;for(i=n;i>=2;i--)a[i]=a[i]+a[i-1];a[1]=1;}}

main(){inta[100],i,n;input(n);for(i=1;i<=n;i=i+1)input(a[i]);coeff(a,n);for(i=1;i<=n;i=i+1)

print(a[i]);}//初始化，任意3．4．2最大公約數(shù)的應(yīng)用

【例】數(shù)組中有n個數(shù)據(jù)，要將它們順序循環(huán)向后移k位，即前面的元素向后移k位，后面的元素則循環(huán)向前移k位，例：1、2、3、4、5循環(huán)移3位后為：3、4、5、1、2?？紤]到n會很大，不允許用2*n以上個空間來完成此題。問題分析1：若題目中沒有關(guān)于存儲空間的限制，我們可以方便地開辟兩個一維數(shù)組，一個存儲原始數(shù)據(jù)，另一個存儲移動后的數(shù)據(jù)。b[(k+i)modn]=a[i];main(){inta[100],b[100],i,n,k;input(n,k);for(i=0;i<n;i=i+1)input(a[i]);for(i=0;i<n;i=i+1)

b[(k+i)modn]=a[i];for(i=0;i<n;i=i+1)print(b[i]);}這個算法的時間效率是n次移動（賦值）。有可能k>n，這樣移動會出現(xiàn)重復(fù)操作,為保證不出現(xiàn)重復(fù)移動的問題,可以在輸入數(shù)據(jù)后，執(zhí)行;

這個算法的移動（賦值）次數(shù)為k*n。當(dāng)n較大時不是一個好的算法。

問題分析2：空間受限制的情況下main(){inta[100],i,j,n,k,temp;input(n,k);for(i=0;i<n;i=i+1)input(a[i]);for(i=0;i<k;i=i+1){temp=a[n-1]；for(j=n-1;j>0;j=j-1)a[j]=a[j-1];a[0]=temp;}for(i=0;i<n;i=i+1)print(a[i]);}k=kmodn●將最后一個存儲空間的數(shù)據(jù),存儲在臨時存儲空間中；●其余數(shù)據(jù)逐個向后移動一位。共k次就能完成問題的要求。算法2如下：問題分析3利用一個臨時存儲空間，把每一個數(shù)據(jù)一次移動到位：1）一組循環(huán)移動的情況：

通過計算我們可以確定某個元素移動后的具體位置，如n=5,k=3時：

1、2、3、4、5循環(huán)移3位后為3、4、5、1、2。可通過計算得出0移到3的位置，3移到1的位置，1移到4的位置，4移到2的位置，2移到0的位置；一組移動（1-4-2-5-3-1）正好將全部數(shù)據(jù)按要求進行了移動。這樣只需要一個輔助變量，每個數(shù)據(jù)只需一次移動就可完成整個移動過程。如果算法就這樣按一組移動去解決問題，就錯了。因為還有其它情況。2）多組循環(huán)移動的情況：算法不能按一組移動去解決問題。當(dāng)n=6，k=3時0、1、2、3、4、5經(jīng)三組循環(huán)移動（0-3-0,1-4-1，2-5-2，）才能將全部數(shù)據(jù)操作完畢。

循環(huán)移動的組數(shù)，與k、n的是怎么樣的關(guān)系呢？當(dāng)N=6，K=2時,0、1、2、3、4、5經(jīng)二組循環(huán)移動(0-2-4-0,1-3-5-1,)，就能將全部數(shù)據(jù)移動完畢。數(shù)學(xué)模型：循環(huán)移動的組數(shù)等于n與k的最大公約數(shù)。算法設(shè)計：1）編寫函數(shù)，完成求n,k最大公約數(shù)m的功能2）進行m組循環(huán)移動。3）每組移動n/m次，和算法2一樣，通過計算可以確定某個元素移動后的具體位置。在移動之前，用臨時變量存儲需要被覆蓋的數(shù)據(jù)。算法3如下：main(){inta[100],b0,b1,i,j,n,k,m,tt;print(“inputthenumberofdata”);input(n);print(“inputthedistantofmoving”);input(k);for(i=0;i<n;i=i+1)input(a[i]);m=ff(n,k);//求最大公約數(shù)for(j=0;j<m;j=j+1){b0=a[j];//b0:暫時保存要移動的數(shù)據(jù)tt=j;for(i=0;i<n/m;i=i+1)//每組移動n/m次{tt=(tt+k)modn;

//b0要移到的目標(biāo)位置

b1=a[tt];//b1:暫時保存目標(biāo)位置上的數(shù)據(jù)a[tt]=b0;

//將移動的數(shù)據(jù)b0移動到目標(biāo)位置b0=b1;}//設(shè)定下一個要移動的數(shù)據(jù)b1給b0}for(i=0;i<n;i=i+1)print(a[i]);}ff(inta，intb){t=1;for(i=2；i<=aandi<=b；i++)while(amodi=0andbmodi=0){t=t*i;a=a/i;b=b/i;}return(t);}算法分析：每組循環(huán)移動都是從前向后進行的，一次移動需要兩次賦值，總體大約需要賦值2n次。能不能繼續(xù)提高效率為賦值n次呢？請考慮改進每組循環(huán)移動的方式為從后開始移動，以提高運行效率。以例子說明：n=6,k=2時，第一組循環(huán)移動0-2-4，在算法3中是這樣實現(xiàn)的：a[0]=>b0，a[2]=>b1,b0（a[0]）=>a[2]，b1=>b0；a[4]=>b1,b0（a[2]）=>a[4]，b1=>b0；a[0]=>b1,b0（a[4]）=>a[0]，b1=>b0；改進后（和算法2類似）：a[4]=>b；a[2]=>a[4],a[0]=>a[2],b=>a[0]。將每組最后一個數(shù)據(jù)元素存儲在輔助存儲空間，以后就可以安全地覆蓋后面的數(shù)組元素了（注意覆蓋順序）。這樣，一組循環(huán)移動只需一次將數(shù)據(jù)存入輔助存儲空間，其后一次移動只需一次賦值，全部工作大約需要賦值n次就可完成。請讀者嘗試完成。實驗P108T43．4．3公倍數(shù)的應(yīng)用

【例】編程完成下面給“余”猜數(shù)的游戲：你心里先想好一個1~100之間的整數(shù)x，將它分別除以3、5和7并得到三個余數(shù)。你把這三個余數(shù)告訴計算機，計算機能馬上猜出你心中的這個數(shù)。游戲過程如下：pleasethinkofanumberbetween1and100yournumberdividedby3hasaremainderof?1yournumberdividedby5hasaremainderof?0yournumberdividedby7hasaremainderof?5letmethinkamoment…yournumberwas40問題分析：算法的關(guān)鍵是：找出余數(shù)與求解數(shù)之間的關(guān)系，也就是建立問題的數(shù)學(xué)模型。數(shù)學(xué)模型：1）當(dāng)s=u+3*v+3*w時，s除以3的余數(shù)與u除以3的余數(shù)是一樣的。2）對s=cu+3*v+3*w，當(dāng)c除以3余數(shù)為1的數(shù)時,s除以3的余數(shù)與u除以3的余數(shù)也是一樣的。證明如下：c除以3余數(shù)為1，記c=3*k+1，則s=u+3*k*u+3*v+3*w，由1)的結(jié)論，上述結(jié)論正確。

記a，b，c分別為所猜數(shù)據(jù)d除以3，5，7后的余數(shù)，則d=70*a+21*b+15*c問題的數(shù)學(xué)模型:其中70稱作a的系數(shù)，21稱作b的系數(shù),15稱作c的系數(shù)。？由以上數(shù)學(xué)常識，a、b、c的系數(shù)必須滿足：1）b、c的系數(shù)能被3整除，且a的系數(shù)被3整除余1；這樣d除以3的余數(shù)與a相同。2）a、c的系數(shù)能被5整除，且b的系數(shù)被5整除余1；這樣d除以5的余數(shù)與b相同。3)a、b的系數(shù)能被7整除，且c的系數(shù)被7整除余1；這樣d除以7的余數(shù)與c相同。

由此可見：

c的系數(shù)是3和5的最公倍數(shù)且被7整除余1，正好是15；a的系數(shù)是7和5的最公倍數(shù)且被3整除余1，最小只能是70；b的系數(shù)是7和3的最公倍數(shù)且被5整除余1，正好是21。

算法設(shè)計：用以上模型求解的數(shù)d，可能比100大//減去3，5，7的最小公倍數(shù)。main(){inta,b,c,d;print(“pleasethinkofanumberbetween1and100.”);print(“yournumberdivdedby3hasaremainkerof”);input(a);print(“yournumberdivdedby5hasaremainkerof”);input(b);print(“yournumberdivdedby7hasaremainkerof”);input(c);print(“l(fā)etmethinkamoment…”);for(i=1,i<1500;i=i+1)；//消耗時間，讓做題者思考d=70*a+21*b+15*c;while(d>105)