程序設(shè)計(jì)常用算法

程序設(shè)計(jì)常用算法

程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第1頁(yè)。算法與程序設(shè)計(jì)算法—解決現(xiàn)實(shí)問(wèn)題的方法或手段如：求解一元二次方程的解程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第2頁(yè)。常見(jiàn)算法1、窮舉法2、遞歸法3、迭代法4、遞推法程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第3頁(yè)。1、窮舉法窮舉法（列舉法或枚舉法），是蠻力策略的具體體現(xiàn)，是一種簡(jiǎn)單而直接地解決問(wèn)題的方法程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第4頁(yè)。百雞問(wèn)題

中國(guó)古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的“百錢買百雞問(wèn)題”雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問(wèn)翁、母、雛各幾何？程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第5頁(yè)。百雞問(wèn)題問(wèn)題分析與算法設(shè)計(jì)

設(shè)雞翁、雞母、雞雛的個(gè)數(shù)分別為x,y,z，題意給定共100錢要買百雞，若全買公雞最多買20只，顯然x的值在0~20之間；同理，y的取值范圍在0~33之間，可得到下面的不定方程：5x+3y+z/3=100x+y+z=100程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第6頁(yè)。百雞問(wèn)題intmain(){

intx,y,z,j=0;printf("Folleingarepossibleplanstobuy100fowlswith100Yuan.\n");for(x=0;x<=20;x++)/*外層循環(huán)控制雞翁數(shù)*/for(y=0;y<=33;y++)/*內(nèi)層循環(huán)控制雞母數(shù)y在0~33變化*/{z=100-x-y;/*內(nèi)外層循環(huán)控制下，雞雛數(shù)z的值受x,y的值的制約*/if(z%3==0&&5*x+3*y+z/3==100)/*驗(yàn)證取z值的合理性及得到一組解的合理性*/printf("%2d:cock=%2dhen=%2dchicken=%2d\n",++j,x,y,z);}}程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第7頁(yè)。窮舉框架窮舉通常應(yīng)用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)在循環(huán)體中，根據(jù)所求解的具體條件，應(yīng)用選擇結(jié)構(gòu)實(shí)施判斷篩選，求得所要求的解窮舉法的框架描述：

n=0;for(k=<區(qū)間下限>;k<=<區(qū)間上限>;k++)//根據(jù)指定范圍實(shí)施窮舉

if(<約束條件>)//根據(jù)約束條件實(shí)施篩選

{printf(<滿足要求的解>);//輸出滿足要求的解

n++;//統(tǒng)計(jì)解的個(gè)數(shù)

}

程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第8頁(yè)。窮舉應(yīng)用1、找出n個(gè)自然數(shù)（1,2,3,…,n）中r個(gè)數(shù)的組合。例如，當(dāng)n=5，r=3時(shí)，求出組合總數(shù)及每一個(gè)組合。2、幾十年前全世界就流行一種數(shù)字游戲，至今仍有人樂(lè)此不疲。在中國(guó)我們把這種游戲稱為“算24點(diǎn)”。您作為游戲者將得到4個(gè)1～9之間的自然數(shù)作為操作數(shù)，而您的任務(wù)是對(duì)這4個(gè)操作數(shù)進(jìn)行適當(dāng)?shù)乃阈g(shù)運(yùn)算，要求運(yùn)算結(jié)果等于24。程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第9頁(yè)。2、遞歸法

遞歸法求解問(wèn)題，通?？梢詫⒁粋€(gè)比較大的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相類似的規(guī)模較小的問(wèn)題來(lái)求解，進(jìn)而最終導(dǎo)致原問(wèn)題的解決。1若n=0

n!=n×(n-1)!

若n>0程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第10頁(yè)。遞歸定義

1n=0n！=n(n-1)!n>0階乘函數(shù)intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第11頁(yè)。Fibonacci數(shù)列一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來(lái)。如果所有兔都不死，已知事先給出一對(duì)兔子，那么一年以后可以繁殖多少對(duì)兔子？1個(gè)月，小兔子沒(méi)有繁殖能力，所以還是1對(duì);2個(gè)月，生下一對(duì)小兔共有2對(duì);3個(gè)月，老兔子又生下1對(duì)，因?yàn)樾⊥米舆€沒(méi)有繁殖能力，所以一共是3對(duì);依次類推可以列出下表：月數(shù)：1、2、3、4、5、6、7、8、9、10、11、12兔子：1、2、3、5、8、13、21、34、55、89、144、

程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第12頁(yè)。使用遞歸的條件1.遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)當(dāng)邊界條件滿足時(shí)，遞歸返回2.考慮使用遞歸算法編寫(xiě)程序時(shí)，應(yīng)滿足兩點(diǎn)：該問(wèn)題能夠被遞歸形式描述存在遞歸結(jié)束的邊界條件

遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。用遞歸思想寫(xiě)出的程序往往十分簡(jiǎn)潔易懂。

程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第13頁(yè)。3、迭代法迭代法也稱輾轉(zhuǎn)法一種不斷用變量的舊值遞推新值的過(guò)程。與迭代法相對(duì)應(yīng)的是直接法（或者稱為一次解法），即一次性解決問(wèn)題。

迭代法又分為精確迭代和近似迭代?！岸址ā焙汀芭ｎD迭代法”屬于近似迭代法。迭代算法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第14頁(yè)。迭代應(yīng)用例

一個(gè)飼養(yǎng)場(chǎng)引進(jìn)一只剛出生的新品種兔子，這種兔子從出生的下一個(gè)月開(kāi)始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，問(wèn)到第12個(gè)月時(shí)，該飼養(yǎng)場(chǎng)共有兔子多少只？分析：這是一個(gè)典型的遞推問(wèn)題。我們不妨假設(shè)第1個(gè)月時(shí)兔子的只數(shù)為u1，第2個(gè)月時(shí)兔子的只數(shù)為u2，第3個(gè)月時(shí)兔子的只數(shù)為u3，……根據(jù)題意，“這種兔子從出生的下一個(gè)月開(kāi)始，每月新生一只兔子”，則有

u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，……程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第15頁(yè)。迭代應(yīng)用u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，……根據(jù)這個(gè)規(guī)律，可以歸納出下面的遞推公式：

un

＝u(n－1)×2(n≥2)

對(duì)應(yīng)un和u(n－1)，定義兩個(gè)迭代變量y和x，可將上面的遞推公式轉(zhuǎn)換成如下迭代關(guān)系：

y=x*2

x=y讓計(jì)算機(jī)對(duì)這個(gè)迭代關(guān)系重復(fù)執(zhí)行11次，就可以算出第12個(gè)月時(shí)的兔子數(shù)。參考程序如下：

x=1

for（i=2；i<=12;i++){

y=x*2

x=y}

printx

end

程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第16頁(yè)。迭代實(shí)例阿米巴用簡(jiǎn)單分裂的方式繁殖，它每分裂一次要用3分鐘。將若干個(gè)阿米巴放在一個(gè)盛滿營(yíng)養(yǎng)參液的容器內(nèi)，45分鐘后容器內(nèi)充滿了阿米巴。已知容器最多可以裝阿米巴220,220個(gè)。試問(wèn)，開(kāi)始的時(shí)候往容器內(nèi)放了多少個(gè)阿米巴？請(qǐng)編程序算出。程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第17頁(yè)。4、遞推法遞推算法是一種簡(jiǎn)單的算法，即通過(guò)已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果的算法。遞推算法分為順推和逆推兩種。

程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第18頁(yè)。思考：1、在西方，星期五和數(shù)字13都代表著壞運(yùn)氣，兩個(gè)不幸的個(gè)體最后結(jié)合成超級(jí)不幸的一天。所以，不管哪個(gè)月的十三日又恰逢星期五就叫“黑色星期五”。要求：輸入年份，輸出是：判斷該年是否包含黑色星期五，如包含，給出具體日期程序設(shè)計(jì)常用算法全文共20頁(yè)，當(dāng)前為第19頁(yè)。2、小明去銀行存錢，拿了一堆硬幣。已知1角的硬幣厚度為1.8mm，5角的硬幣厚1.5mm，1元的硬幣為2.0mm。小