C#第5章C#程序的算法選講

1范鑫燁fanxinye@辦公室：實(shí)驗(yàn)樓B304

面向?qū)ο蟮某绦蛟O(shè)計(jì)—C#程序設(shè)計(jì)第五章C#程序算法選講關(guān)于算法的書(shū)籍很多，如著名的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》（TheArtOfComputerProgramming)、《算法導(dǎo)論》（IntroductionToAlgorithms）。常用算法舉例1.遞推法2.遞歸法3.窮舉法4.貪心算法5.迭代法6.數(shù)值積分21、遞推法遞推：一種用若干步可重復(fù)的簡(jiǎn)運(yùn)算（規(guī)律）來(lái)描述復(fù)雜問(wèn)題的方法。通過(guò)已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果的算法。

把一個(gè)復(fù)雜的計(jì)算過(guò)程轉(zhuǎn)化為簡(jiǎn)單過(guò)程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。該算法利用了計(jì)算機(jī)速度快和不知疲倦的機(jī)器特點(diǎn)。如Fibonacci數(shù)列為：1，1，2，3，5，8，……。3實(shí)例1：遞推法Fibonacci數(shù)列第n項(xiàng)值初始：f1=1,f2=1；

循環(huán)：從i=3開(kāi)始，f3=f1+f2，再讓f2=f3,f1=f2迭代后,進(jìn)行下次循環(huán)；4

privatevoidbutton1_Click(objectsender,EventArgse){intf1=1,f2=1,f3=0;intn=Convert.ToInt16(textBox1.Text);if(n==1||n==2)f3=1;else

{

for(inti=3;i<=n;i++)

{

f3=f1+f2;

f1=f2;

f2=f3;

}

}

textBox2.Text=Convert.ToString(f3);

}5實(shí)例2：遞推法猴子吃桃猴子吃桃：小猴在一天摘了若干個(gè)桃子，當(dāng)天吃掉一半多一個(gè)；第二天接著吃了剩下的桃子的一半多一個(gè)；以后每天都吃尚存桃子的一半零一個(gè)，到第10天早上要吃時(shí)只剩下一個(gè)了，問(wèn)小猴那天共摘下了多少個(gè)桃子？設(shè)第n天的桃子為xn，那么它前一天的桃子數(shù)xn-1

：6privatevoidbutton1_Click(objectsender,EventArgse){

intlastn=1;//前一天桃子數(shù)，第10天早晨有1個(gè)

textBox1.Text="1"+“\n";

for(inti=9;i>0;--i)

{

lastn=(lastn+1)*2;

textBox1.Text+=lastn.ToString()+"\r\n";

}

}72、遞歸法程序調(diào)用自身的編程技巧稱為遞歸。C#中可定義方法（或靜態(tài)方法），該方法內(nèi)部調(diào)用自身。遞歸可以把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解。遞歸問(wèn)題：能用自身結(jié)構(gòu)描述自身的問(wèn)題，例:階乘。privateintFact(intn){…n=n*Fact(n-1);…}8在遞歸處理中，用棧來(lái)實(shí)現(xiàn)。棧中存放形參、局部變量、返回地址。遞推過(guò)程：每調(diào)用自身，當(dāng)前參數(shù)壓棧，直到達(dá)到遞歸結(jié)束條件?；貧w過(guò)程：不斷從棧中彈出當(dāng)前的參數(shù)，直到?？?。遞推回歸9實(shí)例3：遞歸法求Fibonacci數(shù)列第n項(xiàng)值publicstaticintFibonacci(inti)

{

//計(jì)算數(shù)列{1,1,2,3,5,8.......}第i項(xiàng)值if

(i

==

0)

return

0;if

(i

==

1)

return

1;elsereturnFibonacci(i-1)+Fibonacci(i-2);

}privatevoidbutton1_Click(objectsender,EventArgse){intn=Convert.ToInt16(textBox1.Text);textBox2.Text=Fibonacci(n).ToString();}103、窮舉法窮舉法，也稱列舉法、枚舉法、試湊法、暴力破解法。即將可能出現(xiàn)的各種情況一一測(cè)試，判斷是否滿足條件，一般采用循環(huán)來(lái)實(shí)現(xiàn)。如密碼的破譯，即將密碼進(jìn)行逐個(gè)推算直到找出真正的密碼為止。例如一個(gè)已知是四位并且全部由數(shù)字組成的密碼，其可能共有10000種組合，因此最多嘗試10000次就能找到正確的密碼。理論上利用這種方法可以破解任何一種密碼，問(wèn)題只在于如何縮短試誤時(shí)間。因此有些人運(yùn)用計(jì)算機(jī)來(lái)增加效率，有些人輔以字典來(lái)縮小密碼組合的范圍。11實(shí)例4：窮舉法求水仙花數(shù)“水仙花數(shù)”是指一種三位整數(shù)，它各位數(shù)字的立方和等于該數(shù)本身。編程將所有的水仙花數(shù)顯示在文本框1上，并在文本框2中顯示個(gè)數(shù)。水仙花數(shù)共有4個(gè)：153、370、371和407。12privatevoidbutton1_Click(objectsender,EventArgse){intnum，i=0;inta,b,c;//百、十、個(gè)位上的數(shù)for(num=100;num<1000;num++){a=num/100;//取百位上的數(shù)

b=(num-a*100)/10;//取十位上的數(shù)

c=num-a*100-b*10;//取個(gè)位上的數(shù)

if(num==a*a*a+b*b*b+c*c*c)

{textBox1.Text+=num.ToString()+"";

i++;}

}textBox2.Text=i.ToString();

}

13中國(guó)古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的“百錢(qián)買(mǎi)百雞問(wèn)題”：雞翁一，值錢(qián)五，雞母一，值錢(qián)三，雞雛三，值錢(qián)一，百錢(qián)買(mǎi)百雞，問(wèn)翁、母、雛各幾何？編程列出所有可能的購(gòu)雞方案。設(shè)雞翁、雞母、雞雛各為x、y、z只，根據(jù)題目要求，列出方程為：x+y+z=1005x+3y+z/3=100三個(gè)未知數(shù)，兩個(gè)方程，此題有若干個(gè)解。解決此類問(wèn)題采用“試湊法”，把每一種情況都考慮到。三個(gè)未知數(shù)利用三重循環(huán)來(lái)實(shí)現(xiàn)。實(shí)例5：窮舉法百錢(qián)買(mǎi)百雞14privatevoidbutton1_Click(objectsender,EventArgse){for(intx=0;x<=100;x++)//雞翁x{for(inty=0;y<=100;y++)//雞母y{for(intz=0;z<=100;z+=3)//雞雛z{if((x+y+z==100)&&(x*5+y*3+z/3==100)){textBox1.Text+="雞翁:"+x.ToString()+"雞母:"+y.ToString()+"雞雛:"+z.ToString()+"\r\n"

;}}}}154、貪心算法貪婪算法是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，比窮舉節(jié)省時(shí)間。它采用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題,通過(guò)每一步貪心選擇,可得到問(wèn)題的一個(gè)最優(yōu)解。16實(shí)例6：貪心算法找零錢(qián)一小孩用1美元買(mǎi)了價(jià)值少于1美元的糖，售貨員希望用數(shù)目最少的硬幣找給小孩。（硬幣面值為25美分、10美分、5美分、及1美分。）售貨員分步驟組成要找的零錢(qián)數(shù)，每次加入一個(gè)硬幣。選擇硬幣時(shí)所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢(qián)數(shù)盡量增大，但所選擇的硬幣值和不超過(guò)找零總數(shù)。67美分2個(gè)25美分1個(gè)10美分1個(gè)5美分2個(gè)1美分17privatevoidbutton1_Click(objectsender,EventArgse){textBox2.Text="";int[]m={25,10,5,1};//硬幣面值

intn=Convert.ToInt16(textBox1.Text);//找零數(shù)

int[]num=newint[m.Length];//硬幣種類數(shù)組

num=zhaoling(m,n);//各種個(gè)數(shù)賦值

for(inti=0;i<m.Length;i++)textBox2.Text+=num[i]+"枚"+m[i]+"面值"+";";

}

publicstaticint[]zhaoling(int[]m,intn){intk=m.Length;int[]num=newint[k];for(inti=0;i<k;i++){num[i]=n/m[i];//模、硬幣數(shù)n=n%m[i];//余數(shù)}returnnum;}185、迭代法迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過(guò)程。迭代算法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法，利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令時(shí)，都從變量的原值推出它的一個(gè)新值。典型的應(yīng)用是高次方程求根：二分迭代法191)二分迭代法高次方程求根二分迭代法求一元高次方程的解。步驟：找y=f(x)的一個(gè)有根單調(diào)區(qū)間[x1,x2];選區(qū)間中點(diǎn)x3=(x1+x2)/2，如f(x1)*f(x3)<0，說(shuō)明根在[x1,x3]內(nèi)，x2=x3;否則在[x3,x2],x1=x3；對(duì)有根區(qū)間繼續(xù)進(jìn)行上述操作，當(dāng)剩余區(qū)間|x2-x1|足夠?。M足某一給定精度）時(shí)，則認(rèn)為區(qū)間的中點(diǎn)是方法的數(shù)值解。20實(shí)例7：二分迭代法求高次方程根,

x3-x-1=0在區(qū)間[0,2]中的數(shù)值解（精度e=10-6）privatevoidbutton1_Click(objectsender,EventArgse){doublex1=0,x2=2,x3=0;while(x2-x1>0.00000001)//判斷是否滿足精度要求{x3=(x1+x2)/2;if((x1*x1*x1-x1-1)*(x3*x3*x3-x3-1)<0)

x2=x3;else

x1=x3;//改變區(qū)間

}textBox1.Text=x3.ToString();}216、數(shù)值積分多數(shù)函數(shù)f找不到其原函數(shù)F，計(jì)算機(jī)可以編程求其數(shù)值解。定積分的幾何意義是求函數(shù)曲線和x軸、x=a、x=b三條直線所圍成區(qū)域的面積。位于x軸上