大學(xué)計算機(jī)-計算思維視角 課件 4.2 典型算法舉例

典型算法舉例算法與程序設(shè)計章名：節(jié)名：窮舉法遞歸123排序為了提高計算機(jī)的工作效率，人們通過長時間的研究開發(fā)，總結(jié)了一些典型算法，在應(yīng)用中非常普遍。窮舉水仙花數(shù)破譯密碼百元買百雞遞歸漢諾塔求階乘排序插入排序冒泡排序選擇排序快速排序堆排序……典型算法舉例窮舉法（又稱“枚舉法”）基本思想是：按問題本身的性質(zhì)，通過多重循環(huán)，一一列舉各種可能的情況，并判斷哪一種可能是符合要求的解（不能遺漏，也不能重復(fù)），并在逐一列舉的過程中，檢驗每個可能的解是否是問題的真正解，若是，我們采用這個解，否則拋棄它。

窮舉法例：雞翁一，值錢五、雞母一，值錢三、雞雛三，值錢一，百錢買百雞，問雞翁、雞母、雞雛各幾個?分析:設(shè)雞翁、雞母、雞雛的數(shù)量分別為cocks、hens、chicks，則可得如下模型：5*cocks+3*hens+chicks/3.0=100cocks+hens+chicks=100窮舉法舉例-百元買百雞百雞問題算法描述:公雞的數(shù)目從0遍歷到20母雞的數(shù)目從0遍歷到33小雞的數(shù)目從0遍歷到100如果5*cocks+3*hens+chicks/3.0=100并且cocks+hens+chicks=100則輸出公雞的數(shù)目、母雞的數(shù)目、小雞的數(shù)目。窮舉法舉例-百元買百雞用自身的結(jié)構(gòu)來描述自身，稱為遞歸。是利用問題本身所具有的某種遞推關(guān)系求解問題的一種方法。思考：什么時候需要采用遞歸方法？問題分解遞歸遞歸舉例——階乘問題遞歸舉例——階乘問題遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反。排序含義：按數(shù)據(jù)隊列的某個關(guān)鍵字，重新按一定規(guī)律排列其隊列（升序/降序）。實(shí)現(xiàn)排序的方法：選擇法冒泡法（氣泡上浮法）插入法……排序在一組數(shù)中，自前而后對相鄰的兩個數(shù)依次進(jìn)行比較和調(diào)整，讓需要的數(shù)往后冒，不需要的數(shù)往下沉。關(guān)鍵：每當(dāng)相鄰的兩數(shù)比較，發(fā)現(xiàn)它們的排序與要求相反時，就將它們互換。算法名字由來:越大的元素會經(jīng)過交換慢慢“浮”到數(shù)列的頂端。排序舉例-冒泡排序比較、判斷--交換--不交換①第1個數(shù)與第2個數(shù)比較，冒出一個大數(shù)放到第2個位置；當(dāng)前數(shù)與它后面的數(shù)比較，再冒出一個大數(shù)放到后面位置；②依次進(jìn)行，從1～9，直到產(chǎn)生了第1個大數(shù)；③重復(fù)①②步，從1～8；④依次類推，直至找到第9個高分排在第2位。排序舉例-冒泡排序窮舉法利用計算機(jī)高速運(yùn)算的優(yōu)點(diǎn)，列舉所有可