1、關(guān)于循環(huán)與遞歸第一張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月第三章 算法基本工具和優(yōu)化技巧 利用算法的基本機(jī)制循環(huán)和遞歸設(shè)計(jì)算法利用算法的基本操作提高算法效率的技巧利用數(shù)組提高算法質(zhì)量建立高效的數(shù)學(xué)模型本章主要講解如何充分利用這些基本的程序設(shè)計(jì)技術(shù)設(shè)計(jì)高質(zhì)量的算法，在程序設(shè)計(jì)與算法設(shè)計(jì)之間起承上啟下的作用第二張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月3.1.1 循環(huán)設(shè)計(jì)要點(diǎn)3.1.2 遞歸設(shè)計(jì)要點(diǎn)3.1.3 遞歸與循環(huán)的比較3.1 循環(huán)與遞歸第三張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月311 循環(huán)設(shè)計(jì)要點(diǎn) 1設(shè)計(jì)中要注意算法的效率 2“自頂向下”的設(shè)計(jì)方法 3由具體到抽象設(shè)計(jì)循環(huán)結(jié)構(gòu) 第四張

2、，PPT共五十五頁(yè)，創(chuàng)作于2022年6月 循環(huán)體的特點(diǎn)是：“以不變應(yīng)萬(wàn)變”。 所謂“不變”是指循環(huán)體內(nèi)運(yùn)算的表現(xiàn)形式是不變的,如變量，控制結(jié)構(gòu)，而每次具體的執(zhí)行內(nèi)容數(shù)據(jù)卻是不盡相同的。在循環(huán)體內(nèi)用不變的運(yùn)算表現(xiàn)形式去描述各種相似的重復(fù)運(yùn)算。1循環(huán)設(shè)計(jì)中要注意算法的效率第五張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月【例1】求1/1!-1/3!+1/5!-1/7!+（-1）n+1/(2n-1)!分析：此問(wèn)題中既有累加又有累乘，準(zhǔn)確地說(shuō)累加的對(duì)象是累乘的結(jié)果。數(shù)學(xué)模型1：Sn=Sn-1+（-1）n+1/(2n-1)!算法設(shè)計(jì)1：多數(shù)初學(xué)者會(huì)直接利用題目中累加項(xiàng)通式，構(gòu)造出循環(huán)體不變式為： S=S+（

3、-1）n+1/(2n-1)!需要用二重循環(huán)來(lái)完成算法，算法1如下：第六張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月算法如下：求（-1）n+1 for(j=1;j=i+1;j=j+1) sign = sign *(-1);s=s+ sign/t; print(“Snm=”,s);main( )int i,n,j,sign=1;float s,t=1; input(n);s=1； for(i=2;i=n;i=i+1) t=1; 求階乘 for(j=1;j=2*i-1;j=j+1)t=t*j; sign =1; 第七張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月算法分析：以上算法是二重循環(huán)來(lái)完成 ，但算法

4、的效率卻太低是O（n2）。當(dāng)前一次循環(huán)已求出7！，當(dāng)這次要想求9！時(shí)，沒(méi)必要再?gòu)?去累乘到9，只需要充分利用前一次的結(jié)果，用7！*8*9即可得到9！，模型為An=An-1*1/(2*n-2)*(2*n-1)。另外運(yùn)算sign = sign *(-1);總共也要進(jìn)行n*(n-1)/2次乘法，這也是沒(méi)有必要的。下面我們就進(jìn)行改進(jìn)。第八張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月數(shù)學(xué)模型2：Sn=Sn-1+（-1）n+1An； An=An-1 *1/(2*n-2)*(2*n-1)main( )int i,n, sign; float s,t=1; input(n);s=1；sign=1; for(i=

5、2;i=n;i=i+1) 或 for(i=1;i=n-1;i=i+1) sign=-sign; sign=-sign;t= t*(2*i-2)*(2*i-1); t= t*2*i*(2*i+1);s=s+ sign/t; s=s+ sign/t; print(“Sum=”,s);第九張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月算法分析：按照數(shù)學(xué)模型2，只需一重循環(huán)就能解決問(wèn)題算法的時(shí)間復(fù)雜性為O（n）。 算法說(shuō)明2第十張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月2“自頂向下”的設(shè)計(jì)方法 自頂向下的方法是從全局走向局部、從概略走向詳盡的設(shè)計(jì)方法。自上而下是系統(tǒng)分解和細(xì)化的過(guò)程?！纠?】編算法找出10

6、00以內(nèi)所有完數(shù)例如，28的因子為1、2、4、7，14，而28=1+2+4+7+14。因此28是“完數(shù)”。編算法找出1000之內(nèi)的所有完數(shù)，并按下面格式輸出其因子：28 its factors are 1，2，4，7，14。第十一張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月1）這里不是要質(zhì)因數(shù)，所以找到因數(shù)后也無(wú)需將其從數(shù)據(jù)中“除掉”。2）每個(gè)因數(shù)只記一次，如8的因數(shù)為1，2，4而不是1，2，2，2（注：本題限定因數(shù)不包括這個(gè)數(shù)本身）第十二張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月1）頂層算法for(i=2;i=n;i=i+1) 判斷i是否是“完數(shù)”; 是“完數(shù)”則按格式輸出;2）判斷i是否是“

7、完數(shù)”的算法 for(j=2;ji;j=j+1)找i的因子，并累加，如果累加值等于i,i 是“完數(shù)”第十三張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月3）進(jìn)一步細(xì)化判斷i是否“完數(shù)”算法s=1for(j=2;ji;j=j+1) if (i mod j=0) (j是i的因素) s=s+j;if （s=i） i是“完數(shù)”;第十四張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月 定義數(shù)組a，s=1; k=0;for(j=2;ji;j=j+1) if (i mod j=0) (j是i的因素) s=s+j; ak=j;k=k+1;if （s=i） 按格式輸出結(jié)果4）考慮輸出格式判斷i是否“完數(shù)”算法考慮到要按格

8、式輸出結(jié)果，應(yīng)該開(kāi)辟數(shù)組存儲(chǔ)數(shù)據(jù)i的所有因子，并記錄其因子的個(gè)數(shù)，因此算法細(xì)化如下：第十五張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月算法如下：main( )int i,k,j,s,a20;for(i=1;i=1000;i+) s=1; /*兩個(gè)賦初值語(yǔ)句s=1,k=0 k=0; 一定要位于外部循環(huán)的內(nèi)部*/ for(j=2;ji;j+) if (i mod j)=0) s=s+j; ak=j; k+; if(i=s) print(s, “its factors are :”,1); for(j=0;ik;j+) print(“,”,ak); 第十六張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月【例

9、3】求一個(gè)矩陣的鞍點(diǎn) (即在行上最小而在列上最大的點(diǎn))。算法設(shè)計(jì)：1）在第一行找最小值，并記錄其列號(hào)。2）然后驗(yàn)證其是否為所在列的最大值，如果是，則找到問(wèn)題的解；否則，則繼續(xù)在下一行找最小值 。第十七張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月for(i=0;in;i=i+1) 找第i行上最小的元素t及所在列minj; 檢驗(yàn)t是否第minj 列的最大值，是則輸出鞍點(diǎn);t=ai0; minj=1;for(j=1;jn;j=j+1)if(aijt)t=aij; minj=j;1）頂層算法 2）找第i行上最小的元素t及所在列minj 第十八張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月3）檢驗(yàn)t是否第mi

10、nj列的最大值，是，則輸出鞍點(diǎn);for(k=0;kt) break;if(kn) continue;print(“the result is a“,i ，“” ,minj, “=”，t);考慮到會(huì)有無(wú)解的情況，設(shè)置標(biāo)志量kz，kz=0代表無(wú)解，找到一個(gè)解后，kz被賦值為1，就不再繼續(xù)找鞍點(diǎn)的工作。請(qǐng)考慮是否有多解的可能性嗎？若有，請(qǐng)改寫算法，找出矩陣中所有的鞍點(diǎn)。第十九張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月算法如下：buck( )int a1010; int i,j,k,minj,t,n=10,kz=0;/*minj代表當(dāng)前行中最小值的列下標(biāo)；設(shè)置標(biāo)志量kz*/readmtr(a,n);p

11、rntmtr(a,n);for(i=0;in;i+) t=ai0; minj=1; for(j=1;jn;j+) if(aijt) t=aij;minj=j; for(k=0;kaiminj) break; if(kn) continue; print(“the result is a“,i ,“”,minj,“=”，aiminj); kz=1; break; if(kz=0) print(“no solution!”); 能否不用continue達(dá)到目的第二十張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月 對(duì)于不太熟悉的問(wèn)題，其數(shù)學(xué)模型或“機(jī)械化操作步驟”的不易抽象，下面看一個(gè)由具體到抽象設(shè)計(jì)循

12、環(huán)細(xì)節(jié)的例題。【例4】編寫算法：打印具有下面規(guī)律的圖形。 1 5 2 8 6 3 10 9 7 4 3由具體到抽象設(shè)計(jì)循環(huán)結(jié)構(gòu)第二十一張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月容易發(fā)現(xiàn)圖形中自然數(shù)在矩陣中排列的規(guī)律，題目中1，2，3，4所在位置我們稱為第1層（主對(duì)角線），例圖中5，6，7所在位置我們稱為第二層，。一般地，第一層有n個(gè)元素，第二層有n-1個(gè)元素基于以上數(shù)據(jù)變化規(guī)律，以層號(hào)作為外層循環(huán)，循環(huán)變量為i（范圍為1n）；以層內(nèi)元素從左上到右下的序號(hào)作為內(nèi)循環(huán)，循環(huán)變量為j（范圍為1n+1-i）。這樣循環(huán)的執(zhí)行過(guò)程正好與“擺放”自然數(shù)的順序相同。用一個(gè)變量k模擬要“擺放”的數(shù)據(jù)，下面的問(wèn)題

13、就是怎么樣將數(shù)據(jù)存儲(chǔ)到對(duì)應(yīng)的數(shù)組元素。算法設(shè)計(jì)：第二十二張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月 數(shù)組元素的存取，只能是按行、列號(hào)操作的。所以下面用由具體到抽象設(shè)計(jì)循環(huán)的“歸納法”，找出數(shù)組元素的行號(hào)、列號(hào)與層號(hào)i及層內(nèi)序號(hào)j的關(guān)系：1.每層內(nèi)元素的列號(hào)都與其所在層內(nèi)的序號(hào)j是相同的。因?yàn)槊繉拥男蛱?hào)是從第一列開(kāi)始向右下進(jìn)行。2.元素的行與其所在的層號(hào)及在層內(nèi)的序號(hào)均有關(guān)系,具體地：第一層行號(hào)1n，行號(hào)與j同；第二層行號(hào)2n，行號(hào)比j大1；第三層行號(hào)3n，行號(hào)比j大2；行號(hào)起點(diǎn)隨層號(hào)i增加而增加，層內(nèi)其它各行的行號(hào)又隨層內(nèi)序號(hào)j增加而增加，由于編號(hào)起始為1，i層第j個(gè)數(shù)據(jù)的列下標(biāo)為i-1+j。

14、綜合以上分析,i層第 j個(gè)數(shù)據(jù)對(duì)應(yīng)的數(shù)組元素是ai-1+jj。 第二十三張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月main( )int i,j,a100100,n,k; input(n); k=1;for(i=1;i=n;i=i+1) for( j=1;j=n+1-i;j=j+1) ai-1+jj=k; k=k+1;for(i=1;i=n;i=i+1) print( “換行符”); for( j=1;j0) /*0階的漢諾塔問(wèn)題當(dāng)作停止條件*/ 2) hanoi(n-1,a,c,b); 3) 輸出 “ Move dise” ,n.”from pile”,a,” to”b); 4) haboi(

15、n-1,c,b,a); 5) endif 第三十三張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月【例2】整數(shù)的分劃問(wèn)題 對(duì)于一個(gè)正整數(shù)n的分劃就是把n寫成一系列正整數(shù)之和的表達(dá)式。例如，對(duì)于正整數(shù)n=6，它可以分劃為： 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1 根據(jù)例子發(fā)現(xiàn)“包括第一行以后的數(shù)據(jù)不超過(guò)6，包括第二行的數(shù)據(jù)不超過(guò)5，第六行的數(shù)據(jù)不超過(guò)1”。 因此，定義一個(gè)函數(shù)Q(n,m)，表示整數(shù)n的“任何被加數(shù)都不超過(guò)m”的分劃的數(shù)目，n的所有分劃的數(shù)目P(n)=Q(n,n)。第三十四張，PPT

16、共五十五頁(yè)，創(chuàng)作于2022年6月模型建立： 一般地Q(n.m)有以下遞歸關(guān)系： 1)Q(n,n)=1+Q(n,n-1) （m=n）Q(n,n-1)表示n的所有其他分劃，即最大被加數(shù)m=n-1的劃分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn) Q(n,n-1)表示被加數(shù)中不包含m的分劃的數(shù)目； Q(n-m,m)表示被加數(shù)中包含(注意不是小于)m的分劃的數(shù)目，遞歸的停止條件：1)Q(n,1)=1，表示當(dāng)最大的被加數(shù)是1時(shí)，該整數(shù)n只有一種分劃，即n個(gè)1相加； 2)Q(1,m)=1，表示整數(shù)n=1只有一個(gè)分劃，不管最大被加數(shù)的上限m是多大。 第三十五張，PPT共五十五頁(yè)，創(chuàng)作于2

17、022年6月算法如下：Divinteger(n, m) if （n 1 or m n） Error(“輸入?yún)?shù)錯(cuò)誤”)； /*n，m1 Q(n,m)是無(wú)意義的*/ else if （n = 1 or m = 1） return（1）； else if （n =10) print( n mod 10); n=n10;print(n);第三十九張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月遞歸算法如下：f2(n) if(n=10) ai=n mod 10; i=i+1; n=n10; ai=n;for(j=i;j=0;j=j-1)print(aj);循環(huán)算法如下：第四十二張，PPT共五十五頁(yè)，創(chuàng)作于2

18、022年6月與f2不同，遞歸算法是先遞歸地求n10的個(gè)位數(shù)字，然后再求個(gè)位數(shù)字n的個(gè)位數(shù)字并輸出。這樣輸出操作是在回溯時(shí)完成的。遞歸停止條件與f2相同為n10。遞歸算法如下：f4(n) if(n=n;i-) for(j=1;j=n;j-) for(k=1;k=n;k-) if(ij)and(ik)and(ij)and(jk) t=t+1; print(i,j,k); print(total=,t); 第四十七張，PPT共五十五頁(yè)，創(chuàng)作于2022年6月constitute2（）int n=5,r=3,i,j,k,t;t=0;for(i=1;i=n-r+1; i=i+1) for(j=i+1;j= n-r+2;j=j+1) for(k=j+1;k=k;i-) ak=i; if (k1) comb(i-1,k-1); else for (j=a0;j0;j-) print(aj); print(“換行符”); constitute3( )int n,r; print(“n,r=”); input(n,r); if（rn） print(“Input n,r error!”); else a