數(shù)據(jù)結(jié)構(gòu)第06章-資料下載頁
2025-07-25 09:08本頁面
【正文】 ≤n)個(gè)人組成一個(gè)委員會(huì)，計(jì)算共有多少種構(gòu)成方法。 問題分析： 從 n個(gè)人中抽出 k(k≤n)個(gè)人的問題是一個(gè)組合問題。把 n個(gè)人固定位置后，從 n個(gè)人中抽出 k個(gè)人的問題可分解為兩部分之和：第一部分是第一個(gè)人包括在 k個(gè)人中，第二部分是第一個(gè)人不包括在 k個(gè)人中。對(duì)于第一部分，則問題簡化為從 n1個(gè)人中抽出 k1個(gè)人的問題；對(duì)于第二部分，則問題簡化為從 n1個(gè)人中抽出 k個(gè)人的問題。圖 67給出了 n=5, k=2時(shí)問題的分解示意圖。 36 圖 67 委員會(huì)問題分解示意圖 37 當(dāng) n=k或 k=0時(shí)，該問題可直接求解，數(shù)值均為 1，這是算法的遞歸出口。因此，委員會(huì)問題的 遞推定義式 為： 38 int Comm(int n, int k) { if(n 1 || k 0 || k n) return 0。 if(k == 0) return 1。 if(n == k) return 1。 return Comm(n1, k1) + Comm(n1, k)。 } 39 例 67 求兩個(gè)正整數(shù) n和 m最大公約數(shù)的 遞推定義式 為： 要求： （ 1） 編寫求解該問題的遞歸算法； （ 2） 分析當(dāng)調(diào)用語句為 Gcd(30, 4)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果； （ 3） 分析當(dāng)調(diào)用語句為 Gcd(97, 5)時(shí)算法的執(zhí)行過程和執(zhí)行結(jié)果； （ 4） 編寫求解該問題的循環(huán)結(jié)構(gòu)算法 。 40 解：（ 1）遞歸算法如下： int Gcd(int n, int m) { if(n 0 || m 0) exit(0)。 if(m == 0) return n。 else if(m n) return Gcd(m, n)。 else return Gcd(m, n % m)。 } 41 （ 2）調(diào)用語句為 Gcd(30, 4)時(shí)，因 mn，遞歸調(diào)用Gcd(4, 2)；因 mn，遞歸調(diào)用 Gcd(2, 0)；因 m=0，到達(dá)遞歸出口，函數(shù)最終返回值為 n=2，即 30和 4的最大公約數(shù)為 2。 （ 3）調(diào)用語句為 Gcd(5,97)時(shí)，因 mn，遞歸調(diào)用Gcd(97, 5)；因 mn，遞歸調(diào)用 Gcd(5, 2)；因 mn，遞歸調(diào)用 Gcd(2, 1)；因 mn，遞歸調(diào)用 Gcd(1, 0)；因m=0，到達(dá)遞歸出口，函數(shù)最終返回值為 n=1，即 5和 97的最大公約數(shù)為 1。 42 回溯法及其設(shè)計(jì)舉例 回溯法是遞歸算法的一種特殊形式，回溯法的 基本思想是： 對(duì)一個(gè)包括有很多結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有若干個(gè)搜索分支的問題，把原問題分解為對(duì)若干個(gè)子問題求解的算法。當(dāng)搜索到某個(gè)結(jié)點(diǎn)、發(fā)現(xiàn)無法再繼續(xù)搜索下去時(shí)，就讓搜索過程回溯退到該結(jié)點(diǎn)的前一結(jié)點(diǎn)，繼續(xù)搜索這個(gè)結(jié)點(diǎn)的其他尚未搜索過的分支； 如果發(fā)現(xiàn)這個(gè)結(jié)點(diǎn)也無法再繼續(xù)搜索下去時(shí)，就讓搜索過程回溯（即退回）到這個(gè)結(jié)點(diǎn)的前一結(jié)點(diǎn)繼續(xù)這樣的搜索過程；這樣的搜索過程一直進(jìn)行到搜索到問題的解或搜索完了全部可搜索分支沒有解存在為止。 43 1) 習(xí)題 66， 68 ， 69 習(xí)題 610， 612 ， 615 作業(yè)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1