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

1、算法基本工具和優(yōu)化技巧計(jì)算機(jī)完成工作的實(shí)質(zhì)是機(jī)械化的操作，而算法設(shè)計(jì)的目標(biāo)是把人腦解決問題的想法規(guī)范化地描述成機(jī)械化操作。 計(jì)算機(jī)語言提供給算法的機(jī)械化操作：計(jì)算、I/O、流程控制、不同存儲(chǔ)模式（變量、數(shù)組、結(jié)構(gòu)體、文件等）。本部分就是要講解如何充分利用基本的機(jī)械化操作設(shè)計(jì)高質(zhì)量的算法，在程序設(shè)計(jì)與算法設(shè)計(jì)之間起承上啟下的作用。1循環(huán)與遞歸將大量重復(fù)處理大量數(shù)據(jù)的步驟抽象成循環(huán)或遞歸模式，設(shè)計(jì)出可以針對(duì)不同規(guī)模解決問題的算法。2循環(huán)設(shè)計(jì)中要注意算法的效率循環(huán)體的特點(diǎn)是：“以不變應(yīng)萬變”。 所謂“不變”是指循環(huán)體內(nèi)運(yùn)算的表現(xiàn)形式是不變的，而每次具體的執(zhí)行內(nèi)容卻是不盡相同的。在循環(huán)體內(nèi)用不變的運(yùn)算

2、表現(xiàn)形式去描述各種相似的重復(fù)運(yùn)算。3【例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( )int i,n, sign; float s,t=1; cinn; s=1；for(i=2;i=n;i+) t= (-1)*t*(2*i-2)*(2*i-1); s=s+ 1/t; cout“Sum=”s;4“自頂向下”的設(shè)計(jì)方法【例2】編算法找出1000以內(nèi)所有完數(shù)例如，28的因子為1、2、4、7，14，而28=1+2+4+7+14。因此28是“完數(shù)”。編算法找出1000

3、之內(nèi)的所有完數(shù)，并按下面格式輸出其因子：2851）頂層算法 for(i=2;i=n;i+) 判斷i是否是完數(shù)； 是完數(shù)則按格式輸出;2）判斷i是否是完數(shù)for(j=2;ji;j+) 找i的因子，并累加如果累加值等于i，i是完數(shù)63）進(jìn)一步細(xì)化判斷i是否“完數(shù)”算法s=1for(j=2;ji;j+) if (i % j=0) s=s+j;if （s=i） i是“完數(shù)”;7算法如下：main( )int i,k,j,s;for(i=1;i=1000;i+) s=1; /*兩個(gè)賦初值語句s=1 for(j=2;ji;j+) if (i % j)=0) s=s+j; if(i=s) couts 0)

4、hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 18【例】任給十進(jìn)制的正整數(shù)，請(qǐng)從低位到高位逐位輸出各位數(shù)字。循環(huán)算法設(shè)計(jì)：f1(n) while(n=10) cout n %10; n=n/10; coutn;19遞歸算法設(shè)計(jì)：1）同上，算法從低位到高位逐位求出各位數(shù)字并輸出，求個(gè)位數(shù)字的算式為 n % 10，下一步則是遞歸地求n/10的個(gè)位數(shù)字。2）當(dāng)n10時(shí)，n為一位數(shù)停止遞歸。遞歸算法如下：f2(n) if(n10) coutn; else cout=10) ai=n % 10; i=i+1;n=n/10; ai=n;for(j

5、=i;j=0;j-)coutn;22遞歸算法設(shè)計(jì)： 與f2不同，遞歸算法是先遞歸地求n/10的個(gè)位數(shù)字，然后再求個(gè)位數(shù)字n的個(gè)位數(shù)字并輸出。這樣輸出操作是在回溯時(shí)完成的。遞歸停止條件與f2相同為n10。遞歸算法如下：f4(n) if(n10) coutn; else f(n/10); cout n %10; 23例4排列問題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。分析：n=1 輸出：r1 n=2 輸出：r1r2 r2r1 n=3 輸出：r1r2r3 r1r3r2 r2r1r3 r2r3r1 r3r1r2 r3r2r1分析r3，全部排列可以分為三類： （1）r1類：r1后跟r2r3

6、的全排列 （2）r2類：r2后跟r1r3的全排列 （3）r3類：r3后跟r1r2的全排列將（1）中r1r2互換位置，得到（2）；將（1）中r1r3互換位置，得到（3）；它說明可以用循環(huán)的方式重復(fù)執(zhí)行交換位置，后面跟隨剩余序列的所有排列，對(duì)剩余序列再使用這個(gè)方法，這就是遞歸調(diào)用，當(dāng)后跟的元素沒有時(shí)就得到遞歸的邊界。24遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。25 由于遞歸算法的實(shí)現(xiàn)包括遞歸和回溯兩步，當(dāng)問題需要“后進(jìn)先出”的操作時(shí)，還是

7、用遞歸算法更有效。如數(shù)據(jù)結(jié)構(gòu)課程中二叉樹的各種遍歷、圖的深度優(yōu)先等算法都是如此。所以不能僅僅從效率上評(píng)價(jià)兩個(gè)控制重復(fù)機(jī)制的好壞。 事實(shí)上，無論把遞歸作為一種算法的策略，還是一種實(shí)現(xiàn)機(jī)制，對(duì)我們?cè)O(shè)計(jì)算法都有很好的幫助。26例7 判斷s字符串是否為回文的遞歸函數(shù)int ishuiwen(char *s,int n)if(n=0 |n=1) return 1;else if(*s=*(s+n-1) ishuiwen(s+1,n-2);else return 0; 27天津城市建設(shè)學(xué)院遞推是計(jì)算機(jī)數(shù)值計(jì)算中的一個(gè)重要算法，可以將復(fù)雜的運(yùn)算化為若干重復(fù)的簡單運(yùn)算，充分發(fā)揮計(jì)算機(jī)長于重復(fù)處理的特點(diǎn)，現(xiàn)舉一

8、例遞 推28天津城市建設(shè)學(xué)院猴子吃桃。有一群猴子摘來了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問猴子們摘來了多少桃子？a9=2a8=(a9+1)*229天津城市建設(shè)學(xué)院作業(yè)：1、運(yùn)動(dòng)會(huì)開了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。30天津城市建設(shè)學(xué)院作業(yè)：2、國王分財(cái)產(chǎn)。某國王臨終前給兒子們分財(cái)產(chǎn)。他把財(cái)產(chǎn)分為若干份，然后給第一個(gè)兒子一份，再加上剩余財(cái)產(chǎn)的1/10；給第二

9、個(gè)兒子兩份，再加上剩余財(cái)產(chǎn)的1/10；給第i個(gè)兒子i份，再加上剩余財(cái)產(chǎn)的1/10。每個(gè)兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國王是“一碗水端平”的。請(qǐng)用程序回答，老國王共有幾個(gè)兒子？財(cái)產(chǎn)共分成了多少份？31天津城市建設(shè)學(xué)院作業(yè)：3、出售金魚。第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時(shí)不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？32天津城市建設(shè)學(xué)院作業(yè)：4、某路公共汽車，總共有八站，從一號(hào)站發(fā)軒時(shí)車上已有n

10、位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來了乘客比前一站少一個(gè)，到了終點(diǎn)站車上還有乘客六人，問發(fā)車時(shí)車上的乘客有多少？33天津城市建設(shè)學(xué)院作業(yè)：5、小華讀書。第一天讀了全書的一半加二頁，第二天讀了剩下的一半加二頁，以后天天如此，第六天讀完了最后的三頁，問全書有多少錢頁？34天津城市建設(shè)學(xué)院作業(yè)：6、日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問題：父親將2520個(gè)桔子分給六個(gè)兒子。分完 后父親說：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1

11、/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結(jié)果大家手中的桔子正好一樣多。問六兄弟原來手中各有多少桔子？35科目及格學(xué)生學(xué)號(hào)語文1，9，6，8，4，3，7代數(shù)5，2，9，1，3，7外語8，1，6，7，3，5，4，9枚舉法：一次考試共考了語文、代數(shù)和外語三科。某小組共有九人，考后各科及格名單如下表，請(qǐng)編寫算法找出三科全及格的學(xué)生的名單（學(xué)號(hào)）。36求X，使X2為一個(gè)各位數(shù)字互不相同的九位數(shù)。（枚舉法）分析：只能用枚舉法嘗試完成此題。由X2為一個(gè)九位數(shù)，估算X應(yīng)在1000032000之間。1） 用一個(gè)10 個(gè)

12、元素的狀態(tài)數(shù)組p，記錄數(shù)字09在X2中出現(xiàn)的情況。數(shù)組元素都賦初值為0，表示數(shù)字09沒有被使用過。 2） 對(duì)嘗試的每一個(gè)數(shù)x，求x*x,并取其各位數(shù)字，數(shù)字作為數(shù)組的下標(biāo)，若對(duì)應(yīng)元素為0，則該數(shù)字第一次出現(xiàn)，將對(duì)應(yīng)的元素賦為1，表示該數(shù)字已出現(xiàn)一次。否則，若對(duì)應(yīng)元素為1，則說明有重復(fù)數(shù)字，結(jié)束這次嘗試。 3） 容易理解當(dāng)狀態(tài)數(shù)組p中有9個(gè)元素為1時(shí)，就找到了問題的解。但這樣判定有解，需要掃描一遍數(shù)組p。為避免這個(gè)步驟，設(shè)置一個(gè)計(jì)數(shù)器k，在取x*x各個(gè)位數(shù)字的過程中記錄不同的數(shù)字的個(gè)數(shù)，當(dāng)k=9時(shí)就找到了問題的解。37main( )long x, y1, y2; int p10, 2, i, t

13、, k, num=0; for (x=10000;x32000; x+) for(i=0; i=9; i=i+1) pi=0; y1=x*x ; y2=y1; k=0; for(i=1; i=9；i+) t=y2 % 10; y2=y2/10; if(pt=0) k=k+1; pt=1; else break; if(k=9) num=num+1; cout“No.”num “：=”x“n2=” y1); 38警察局抓了a，b，c，d四名偷竊嫌疑犯，其中只有一人是小偷。審問中 a說：“我不是小偷。” b說：“c是小偷。” c說：“小偷肯定是d。” d說：“c在冤枉人?！爆F(xiàn)在已經(jīng)知道四個(gè)人中三人

14、說的是真話，一人說的是假話，問到底誰是小偷？信息數(shù)字化39算法設(shè)計(jì)：用變量x存放小偷的編號(hào)，則x的取值范圍從1取到4，就假設(shè)了他們中的某人是小偷的所有情況。四個(gè)人所說的話就可以分別寫成： a說的話：x1 b說的話：x=3 c說的話：x=4 d說的話：x4或not(x=4) 注意:在x的枚舉過程中，當(dāng)這四個(gè)邏輯式的值相加等于3時(shí)，即表示“四個(gè)人中三人說的是真話，一人說的是假話”。 40算法如下：main( ) int x; for(x=1;x=4;x+) if(x1)+(x=3)+(x=4)+(x4)=3) coutchr(64+x)“is a thief .”; 運(yùn)行結(jié)果： c is a th

15、ief .41三位老師對(duì)某次數(shù)學(xué)競賽進(jìn)行了預(yù)測。他們的預(yù)測如下：甲說：學(xué)生A得第一名，學(xué)生B得第三名。乙說：學(xué)生C得第一名，學(xué)生D得第四名。丙說：學(xué)生D得第二名，學(xué)生A得第三名。競賽結(jié)果表明，他們都說對(duì)了一半，說錯(cuò)了一半，并且無并列名次，試編程輸出A、B、C、D各自的名次。42算法設(shè)計(jì)： 1）用a，b，c，d 代表四個(gè)同學(xué)，其存儲(chǔ)的值代表他們的名 次。 設(shè)置第一層計(jì)數(shù)循環(huán)a的范圍從1到4； 設(shè)置第二層計(jì)數(shù)循環(huán)b的范圍從1到4； 設(shè)置內(nèi)計(jì)數(shù)循環(huán)c的范圍從1到4； 由于無并列名次，名次的和為1+2+3+4=10，由此可計(jì)算 出d的名次值為10-a-b-c。 2）問題的已知內(nèi)容，可以表示成以下幾個(gè)條件式： (1) (a=1)+(b=3)=1 (2) (c=1)+(d=4)=1 (3) (d=2)+(a=3)=1 若三個(gè)條件均滿足，則輸出結(jié)果，若不滿足，繼續(xù)循環(huán) 搜索，直至循環(huán)正常結(jié)束。 43算法如下：main( )int a,b,c,d;for( a=1;a=4;a+) for( b=1;b=4;b+) if (ab) for( c=1;c=4;c+) if (ca & cb) d=10-a-b-c; if (da & db & dc ) if(a=1)+(b=3)=1 & (c=1)+(d=4)=1 & (d=2)+(a=3)=1) cout “a,b,c,d=”abcd;