1%%-第1章(中科大) 基礎(chǔ)算法思想

零基礎(chǔ)學(xué)算法

第1章：基礎(chǔ)算法思想課程安排編程的靈魂：數(shù)據(jù)結(jié)構(gòu)+算法算法的作用遞推算法枚舉(窮舉)算法遞歸算法分治算法貪婪算法試探算法模擬算法算法的評(píng)價(jià)1.1編程的靈魂：數(shù)據(jù)結(jié)構(gòu)+算法由上面的公式可以看出，程序設(shè)計(jì)中數(shù)據(jù)結(jié)構(gòu)和算法是最重要的，是編程的靈魂。數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)，算法總是要依賴(lài)于某種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。往往是在發(fā)展一種算法的時(shí)候，構(gòu)建了適合于這種算法的數(shù)據(jù)結(jié)構(gòu)。一種數(shù)據(jù)結(jié)構(gòu)如果脫離了算法，也就沒(méi)有存在的價(jià)值了。1.2算法的作用1.2.1算法的作用

解決任何一個(gè)實(shí)際問(wèn)題，都不可避免地涉及到算法的問(wèn)題，例如本章開(kāi)頭提到的存錢(qián)問(wèn)題，再如節(jié)假日公司值班人員的排班等，都需要通過(guò)一定的算法，得到一個(gè)最優(yōu)（或較優(yōu)）的方案。1.2.2實(shí)例：看商品猜價(jià)格

首先出示一件價(jià)格在999元以?xún)?nèi)的商品，參與者要猜出這件商品的價(jià)格。在猜價(jià)格的過(guò)程中，主持人會(huì)根據(jù)參與者給出的價(jià)格，相應(yīng)地給出“高了”或“低了”的提示。1.3遞推算法

遞推算法使用“步步為營(yíng)”的方法，不斷利用已有的信息推導(dǎo)出新的東西。順推法：是指從已知條件出發(fā)，逐步推算出要解決問(wèn)題的方法。例如：斐波拉契數(shù)列就可以通過(guò)順推法不斷遞推算出新的數(shù)據(jù)。逆推法：是從已知的結(jié)果出發(fā)，用迭代表達(dá)式逐步推算出問(wèn)題開(kāi)始的條件，即順推法的逆過(guò)程。1.3.1算法思路1.3.2順推實(shí)例1.3遞推算法1.3.3逆推實(shí)例若在第48月小龍大學(xué)畢業(yè)時(shí)連本帶息要取1000元，則要先求出第47個(gè)月時(shí)銀行存款的錢(qián)數(shù)第47月月末存款=1000/(1+0.0171/12)；第46月月末存款=(第47月月末存款+1000)/(1+0.0171/12)依次類(lèi)推，可以求出第45月、第44月……的月末存款的數(shù)值第45月月末存款=(第46月月末存款+1000)/(1+0.0171/12)第44月月末存款=(第45月月末存款+1000)/(1+0.0171/12)

…………第2月月末存款=(第3月月末存款+1000)/(1+0.0171/12)第1月月末存款=(第2月月末存款+1000)/(1+0.0171/12)1.3遞推算法1.4枚舉(窮舉)算法枚舉法的本質(zhì)就是從所有候選答案中去搜索正確的解，使用該算法需要滿(mǎn)足兩個(gè)條件：（1）可預(yù)先確定候選答案的數(shù)量；（2）候選答案的范圍在求解之前必須有一個(gè)確定的集合。1.4.1算法思路1.4枚舉(窮舉)算法1.4.2實(shí)例：填數(shù)游戲

由于算術(shù)表達(dá)式的特殊性，在編程求解這個(gè)算式時(shí)，需要注意以下幾點(diǎn)：當(dāng)填入除號(hào)時(shí)，要求右側(cè)的數(shù)不能為0。乘除的運(yùn)算級(jí)別比加減高。

1.4枚舉(窮舉)算法1.4.3實(shí)例：填運(yùn)算符1.5遞歸算法

遞歸算法，就是一種直接或者間接地調(diào)用自身的算法。遞歸算法的具體實(shí)現(xiàn)過(guò)程一般通過(guò)函數(shù)或子過(guò)程來(lái)完成，在函數(shù)或子過(guò)程的內(nèi)部，編寫(xiě)代碼直接或者間接地調(diào)用自己，即可完成遞歸操作。1.5.1算法思路1.5.2求階乘1.5遞歸算法

6!=6*5*4*3*2*11.5.3實(shí)例：數(shù)制轉(zhuǎn)換1.5遞歸算法

(121)10=(1111001)21.6分治算法1.6.1算法思路

使用分治法設(shè)計(jì)程序時(shí)，一般可按以下步驟進(jìn)行：（1）分解：將要求解的問(wèn)題劃分成若干規(guī)模較小的同類(lèi)問(wèn)題；（2）求解：當(dāng)子問(wèn)題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決；（3）合并：按求解問(wèn)題的要求，將子問(wèn)題的解逐層合并，即可構(gòu)成最終的解。1.6.2實(shí)例：乒乓球比賽賽程安排1.7貪婪算法1.7.1算法思路

貪婪算法基本思路：從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，就停止算法，給出近似解。由貪婪算法的特點(diǎn)和思路可看出，該算法存在以下問(wèn)題：不能保證最后的解是最優(yōu)的；不能用來(lái)求最大或最小解問(wèn)題；只能求滿(mǎn)足某些約束條件的可行解的范圍。1.7.2實(shí)例：換零錢(qián)

人民幣有100、50、10、5、2、1、0.5、0.2、0.1等多種面額（單位為元）。在補(bǔ)零錢(qián)時(shí)，可有多種方案，例如需補(bǔ)零錢(qián)68.90元，至少可有以下方案：1張50、1張10、1張5、3張1、1張0.5、2張0.2；1張50、1張10、1張5、3張1、1張0.5、4張0.1；6張10、1張5、3張1、1張0.5、2張0.2。1.8試探算法1.8.1算法思路

為了求得問(wèn)題的解，先選擇某一種可能情況進(jìn)行試探，在試探過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇的假設(shè)情況是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前試探，如此反復(fù)進(jìn)行，直至得到解或證明無(wú)解。1.8.2實(shí)例：生成彩票號(hào)碼組合假設(shè)有一種彩票，每注由7個(gè)1~29的數(shù)字組成，且這7個(gè)數(shù)字不能相同，編寫(xiě)程序生成所有的號(hào)碼組合。1.9模擬算法1.9.1算法思路

在程序設(shè)計(jì)語(yǔ)言中，可使用隨機(jī)函數(shù)來(lái)模擬自然界中發(fā)生的不可預(yù)測(cè)情況。C語(yǔ)言中使用srand()和rand()函數(shù)可生成隨機(jī)數(shù)。1.9.2實(shí)例：猜數(shù)游戲使用模擬法編寫(xiě)一個(gè)猜數(shù)游戲，由計(jì)算機(jī)隨機(jī)生成一個(gè)1~100之內(nèi)的整數(shù)，然后由用戶(hù)來(lái)猜這個(gè)數(shù)，根據(jù)用戶(hù)猜測(cè)的次數(shù)分別給出不同的提示文字。1.9.3實(shí)例：模擬擲骰子游戲由用戶(hù)輸入骰子數(shù)量和參賽人數(shù)，然后由計(jì)算機(jī)隨機(jī)生成每一粒骰子的數(shù)量，再累加起來(lái)就得到每一個(gè)選手的總點(diǎn)數(shù)。1.10算法的評(píng)價(jià)1.10.1算