算法的基本工具和優(yōu)化技巧

算法的基本工具和優(yōu)化技巧第一頁，共四十五頁，編輯于2023年，星期三循環(huán)與遞歸將大量重復(fù)處理大量數(shù)據(jù)的步驟抽象成循環(huán)或遞歸模式，設(shè)計出可以針對不同規(guī)模解決問題的算法。第二頁，共四十五頁，編輯于2023年，星期三循環(huán)設(shè)計中要注意算法的效率循環(huán)體的特點是：“以不變應(yīng)萬變”。所謂“不變”是指循環(huán)體內(nèi)運算的表現(xiàn)形式是不變的，而每次具體的執(zhí)行內(nèi)容卻是不盡相同的。在循環(huán)體內(nèi)用不變的運算表現(xiàn)形式去描述各種相似的重復(fù)運算。第三頁，共四十五頁，編輯于2023年，星期三【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）n+1/(2n-1)!

數(shù)學(xué)模型2：Sn=Sn-1+An；

An=(-1)*An-1*((2*n-2)*(2*n-1))main(){inti,n,sign;floats,t=1;cin>>n;s=1；for(i=2;i<=n;i++){t=(-1)*t*(2*i-2)*(2*i-1)};s=s+1/t;}cout<<“Sum=”<<s;}第四頁，共四十五頁，編輯于2023年，星期三“自頂向下”的設(shè)計方法【例2】編算法找出1000以內(nèi)所有完數(shù)例如，28的因子為1、2、4、7，14，而28=1+2+4+7+14。因此28是“完數(shù)”。編算法找出1000之內(nèi)的所有完數(shù)，并按下面格式輸出其因子：28第五頁，共四十五頁，編輯于2023年，星期三1）頂層算法

for(i=2;i<=n;i++){判斷i是否是完數(shù)；是完數(shù)則按格式輸出;}

2）判斷i是否是完數(shù)for(j=2;j<i;j++)

找i的因子，并累加如果累加值等于i，i是完數(shù)

第六頁，共四十五頁，編輯于2023年，星期三3）進(jìn)一步細(xì)化——判斷i是否“完數(shù)”算法s=1for(j=2;j<i;j++)if(i%j=0)s=s+j;if（s==i）i是“完數(shù)”;

第七頁，共四十五頁，編輯于2023年，星期三算法如下：main(){inti,k,j,s;for(i=1;i<=1000;i++){s=1;/*兩個賦初值語句s=1for(j=2;j<i;j++)if(i%j)==0)s=s+j;if(i==s)cout<<s<<endl;}}

第八頁，共四十五頁，編輯于2023年，星期三

在算法中，遞歸一詞用于表示直接或間接的調(diào)用自身的算法。

特別的，用函數(shù)自身給出定義的函數(shù)被稱之為遞歸函數(shù)。

第九頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院什么是遞歸？

其實，我們在生活中經(jīng)常運用遞歸的方式來思考問題，如參考下面這個例子：例1：第5個人的年齡比第4個人的年齡大2歲，第4個人的年齡比第3個人的年齡大2歲，第3個人的年齡比第2個人的年齡大2歲，第2個人的年齡比第1個人的年齡大2歲，第1個的年齡10歲。第5個人的年該該是多少呢？第十頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院

著名的意大利數(shù)學(xué)家斐波那契(Fibonacci)在他的著作《算盤書》中提出了一個“兔子問題”：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養(yǎng)了一對小兔子，問到年底時將有多少對兔子?

(當(dāng)然得假設(shè)兔子沒有死亡而且嚴(yán)格按照上述規(guī)律長大與繁殖)我們需要研究表中的規(guī)律，找出一般的方法，去解決這個問題。第十一頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院“兔子問題”很容易列出一條遞推式而得到解決。假設(shè)第N個月的兔子數(shù)目是F(N)，我們有：

這是因為每月的大兔子數(shù)目一定等于上月的兔子總數(shù)，而每個月的小兔子數(shù)目一定等于上月的大兔子數(shù)目(即前一個月的兔子的數(shù)目)。第十二頁，共四十五頁，編輯于2023年，星期三遞歸設(shè)計要點直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。遞歸是一種比迭代循環(huán)更強(qiáng)、更好用的循環(huán)結(jié)構(gòu)。只需要找出遞歸關(guān)系和最小問題的解。遞歸方法只需少量的步驟就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了算法的代碼量。第十三頁，共四十五頁，編輯于2023年，星期三遞歸的關(guān)鍵在于找出遞歸方程式和遞歸終止條件。遞歸定義：使問題向邊界條件轉(zhuǎn)化的規(guī)則。遞歸定義必須能使問題越來越簡單。遞歸邊界條件：也就是所描述問題的最簡單情況，它本身不再使用遞歸的定義。第十四頁，共四十五頁，編輯于2023年，星期三遞歸算法解題通常有三個步驟：1）分析問題、尋找遞歸：找出大規(guī)模問題與小規(guī)模問題的關(guān)系，這樣通過遞歸使問題的規(guī)模逐漸變小。2）設(shè)置邊界、控制遞歸：找出停止條件，即算法可解的最小規(guī)模問題。3）設(shè)計函數(shù)、確定參數(shù)：和其它算法模塊一樣設(shè)計函數(shù)體中的操作及相關(guān)參數(shù)。常見的遞歸算法階乘Fibonacci數(shù)列著名的漢諾塔問題二叉樹的3種遍歷第十五頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院故事： 相傳在古代印度的Bramah廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中恪守下述規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上面。有人會覺得這很簡單，真的動手移盤就會發(fā)現(xiàn)，如以每秒移動一只盤子的話，按照上述規(guī)則將64只盤子從一個柱子移至另一個柱子上，所需時間約為5800億年。第十六頁，共四十五頁，編輯于2023年，星期三Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。第十七頁，共四十五頁，編輯于2023年，星期三在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。當(dāng)n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n＞1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。Hanoi塔問題

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}第十八頁，共四十五頁，編輯于2023年，星期三【例】任給十進(jìn)制的正整數(shù)，請從低位到高位逐位輸出各位數(shù)字。

循環(huán)算法設(shè)計：f1(n){while(n>=10){cout<<n%10;n=n/10;}cout<<n;}第十九頁，共四十五頁，編輯于2023年，星期三遞歸算法設(shè)計：1）同上，算法從低位到高位逐位求出各位數(shù)字并輸出，求個位數(shù)字的算式為n%10，下一步則是遞歸地求n/10的個位數(shù)字。2）當(dāng)n<10時，n為一位數(shù)停止遞歸。遞歸算法如下：f2(n){if(n<10)cout<<n;else{cout<<n%10;f(n/10);}}第二十頁，共四十五頁，編輯于2023年，星期三【例】任給十進(jìn)制的正整數(shù)，請從高位到低位逐位輸出各位數(shù)字。循環(huán)算法設(shè)計：本題目中要求“從高位到低位”逐位輸出各位數(shù)字，但由于我們并不知道正整數(shù)的位數(shù)，算法還是“從低位到高位”逐位求出各位數(shù)字比較方便。這樣就不能邊計算邊輸出，而需要用數(shù)組保存計算的結(jié)果，最后倒著輸出。第二十一頁，共四十五頁，編輯于2023年，星期三循環(huán)算法如下：f3(n){intj,i=0,a[16];while(n>=10){a[i]=n%10;i=i+1;n=n/10;}a[i]=n;for(j=i;j>=0;j--)cout<<n;}第二十二頁，共四十五頁，編輯于2023年，星期三遞歸算法設(shè)計：

與f2不同，遞歸算法是先遞歸地求n/10的個位數(shù)字，然后再求個位數(shù)字n的個位數(shù)字并輸出。這樣輸出操作是在回溯時完成的。遞歸停止條件與f2相同為n<10。遞歸算法如下：f4(n){if(n<10)cout<<n;else{f(n/10);cout<<n%10;}}第二十三頁，共四十五頁，編輯于2023年，星期三例4排列問題設(shè)計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。分析：n=1輸出：r1n=2輸出：r1r2r2r1n=3輸出：r1r2r3r1r3r2r2r1r3r2r3r1r3r1r2r3r2r1分析r3，全部排列可以分為三類：（1）r1類：r1后跟r2r3的全排列（2）r2類：r2后跟r1r3的全排列（3）r3類：r3后跟r1r2的全排列將（1）中r1r2互換位置，得到（2）；將（1）中r1r3互換位置，得到（3）；它說明可以用循環(huán)的方式重復(fù)執(zhí)行交換位置，后面跟隨剩余序列的所有排列，對剩余序列再使用這個方法，這就是遞歸調(diào)用，當(dāng)后跟的元素沒有時就得到遞歸的邊界。第二十四頁，共四十五頁，編輯于2023年，星期三遞歸小結(jié)優(yōu)點：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。第二十五頁，共四十五頁，編輯于2023年，星期三

由于遞歸算法的實現(xiàn)包括遞歸和回溯兩步，當(dāng)問題需要“后進(jìn)先出”的操作時，還是用遞歸算法更有效。如數(shù)據(jù)結(jié)構(gòu)課程中二叉樹的各種遍歷、圖的深度優(yōu)先等算法都是如此。所以不能僅僅從效率上評價兩個控制重復(fù)機(jī)制的好壞。事實上，無論把遞歸作為一種算法的策略，還是一種實現(xiàn)機(jī)制，對我們設(shè)計算法都有很好的幫助。第二十六頁，共四十五頁，編輯于2023年，星期三例7判斷s字符串是否為回文的遞歸函數(shù)intishuiwen(char*s,intn){ if(n==0||n==1)return1; else {if(*s==*(s+n-1))ishuiwen(s+1,n-2); elsereturn0; }}第二十七頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院

遞推是計算機(jī)數(shù)值計算中的一個重要算法，可以將復(fù)雜的運算化為若干重復(fù)的簡單運算，充分發(fā)揮計算機(jī)長于重復(fù)處理的特點，現(xiàn)舉一例遞推第二十八頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院猴子吃桃。有一群猴子摘來了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問猴子們摘來了多少桃子？a9=2a8=(a9+1)*2第二十九頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院作業(yè)：1、運動會開了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。第三十頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院作業(yè)：2、國王分財產(chǎn)。某國王臨終前給兒子們分財產(chǎn)。他把財產(chǎn)分為若干份，然后給第一個兒子一份，再加上剩余財產(chǎn)的1/10；給第二個兒子兩份，再加上剩余財產(chǎn)的1/10；……；給第i個兒子i份，再加上剩余財產(chǎn)的1/10。每個兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國王是“一碗水端平”的。請用程序回答，老國王共有幾個兒子？財產(chǎn)共分成了多少份？第三十一頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院作業(yè)：3、出售金魚。第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？第三十二頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院作業(yè)：4、某路公共汽車，總共有八站，從一號站發(fā)軒時車上已有n位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來了乘客比前一站少一個……，到了終點站車上還有乘客六人，問發(fā)車時車上的乘客有多少？第三十三頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院作業(yè)：5、小華讀書。第一天讀了全書的一半加二頁，第二天讀了剩下的一半加二頁，以后天天如此……，第六天讀完了最后的三頁，問全書有多少錢頁？第三十四頁，共四十五頁，編輯于2023年，星期三天津城市建設(shè)學(xué)院作業(yè)：6、日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個問題：父親將2520個桔子分給六個兒子。分完后父親說：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結(jié)果大家手中的桔子正好一樣多。問六兄弟原來手中各有多少桔子？第三十五頁，共四十五頁，編輯于2023年，星期三科目及格學(xué)生學(xué)號語文1，9，6，8，4，3，7代數(shù)5，2，9，1，3，7外語8，1，6，7，3，5，4，9

枚舉法：

一次考試共考了語文、代數(shù)和外語三科。某小組共有九人，考后各科及格名單如下表，請編寫算法找出三科全及格的學(xué)生的名單（學(xué)號）。第三十六頁，共四十五頁，編輯于2023年，星期三求X，使X2為一個各位數(shù)字互不相同的九位數(shù)。（枚舉法）分析：只能用枚舉法嘗試完成此題。由X2為一個九位數(shù)，估算X應(yīng)在10000——32000之間。1）

用一個10個元素的狀態(tài)數(shù)組p，記錄數(shù)字0——9在X2中出現(xiàn)的情況。數(shù)組元素都賦初值為0，表示數(shù)字0——9沒有被使用過。

2）

對嘗試的每一個數(shù)x，求x*x,并取其各位數(shù)字，數(shù)字作為數(shù)組的下標(biāo)，若對應(yīng)元素為0，則該數(shù)字第一次出現(xiàn)，將對應(yīng)的元素賦為1，表示該數(shù)字已出現(xiàn)一次。否則，若對應(yīng)元素為1，則說明有重復(fù)數(shù)字，結(jié)束這次嘗試。

3）容易理解當(dāng)狀態(tài)數(shù)組p中有9個元素為1時，就找到了問題的解。但這樣判定有解，需要掃描一遍數(shù)組p。為避免這個步驟，設(shè)置一個計數(shù)器k，在取x*x各個位數(shù)字的過程中記錄不同的數(shù)字的個數(shù)，當(dāng)k=9時就找到了問題的解。第三十七頁，共四十五頁，編輯于2023年，星期三main(){longx,y1,y2;intp[10],2,i,t,k,num=0;for(x=10000;x<32000;x++){for(i=0;i<=9;i=i+1)p[i]=0;y1=x*x;y2=y1;k=0;for(i=1;i<=9；i++){t=y2%10;y2=y2/10;if(p[t]==0){k=k+1;p[t]=1;}elsebreak;}if(k==9){num=num+1;cout<<“No.”<<num<<“：=”<<x<<“n2=”<<y1);}}}第三十八頁，共四十五頁，編輯于2023年，星期三警察局抓了a，b，c，d四名偷竊嫌疑犯，其中只有一人是小偷。審問中

a說：“我不是小偷?！?/p>

b說：“c是小偷?！?/p>

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

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

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

問到底誰是小偷？

信息數(shù)字化第三十九頁，共四十五頁，編輯于2023年，星期三算法設(shè)計：用變量x存放小偷的編號，則x的取值范圍從1取到4，就假設(shè)了他們中的某人是小偷的所有情況。四個人所說的話就可以分別寫成：

a說的話：x<>1b說的話：x=3c說的話：x=4d說的話：x<>4或not(x=4)

注意:在x的枚舉過程中，當(dāng)這四個邏輯式的值相加等于3時，即表示“四個人中三人說的是真話，一人說的是假話”。

第四十頁，共四十五頁，編輯于2023年，星期三算法如下：main(){intx;for(x=1;x<=4;x++)if((x<>1)+(x==3)+(x==4)+(x<>4)==3)cout<<chr(64+x)<<“isathief.”;

}運行結(jié)果：

cisathief.第四十一頁，共四十五頁，編輯于2023年，星期三三位老師對某次數(shù)學(xué)競賽進(jìn)行了預(yù)測。他們的預(yù)測如下：甲說：學(xué)生A得第一名，學(xué)生B得第三名。

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

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

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

第四十二頁，共四十五頁，編輯于2023年，星期三算法設(shè)計：

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