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