北京大學(xué)教程w1枚舉基本思想

1、1枚舉 基本思想郭煒程序設(shè)計(jì)實(shí)習(xí)枚舉基于已有知識進(jìn)行猜測的一種問題求解策略例如: 求小于N的最大素?cái)?shù) 找不到一個(gè)數(shù)學(xué)公式, 使得根據(jù)N就可以計(jì)算出這個(gè)素?cái)?shù) N-1是素?cái)?shù)嗎? N-2是素?cái)?shù)嗎? N-K是素?cái)?shù)的充分必要條件:N-K不能被任何一個(gè)大于1, 小于N-K的素?cái)?shù)整除N-K是否是素?cái)?shù)的問題àà轉(zhuǎn)化為求小于N-K的全部素?cái)?shù)2枚舉解決辦法 2是素?cái)?shù), 記為PRIM0 根據(jù)PRIM0, PRIM1 , , PRIMk, 尋找比PRIMk大的最小素?cái)?shù)PRIMk+1 如果PRIMk+1大于N, 則PRIMk是我們需要找的素?cái)?shù),否則繼續(xù)尋找3枚舉的思想: 猜測枚舉從可能的集合中一 一

2、列舉各元素 根據(jù)所知道的知識, 給一個(gè)猜測的 2是素?cái)?shù)枚舉算法 對問題可能解集合的每一項(xiàng) 根據(jù)問題給定的檢驗(yàn)條件判定哪些是成立的 使條件成立的即是問題的解4枚舉的思想: 猜測枚舉過程猜測的是否正確à 2是小于N的最大素?cái)?shù)嗎? 進(jìn)行新的猜測: 有兩個(gè)關(guān)鍵因素要注意 猜測的結(jié)果必須是前面的猜測中沒有出現(xiàn)過的. 每次猜測是素?cái)?shù)一定比已經(jīng)找到的素?cái)?shù)大 猜測的過程中要及早排除錯(cuò)誤的才可能是素?cái)?shù). 除2之外, 只有奇數(shù)5枚舉中三個(gè)關(guān)鍵問題問題一給出解空間, 建立簡潔的數(shù)學(xué)模型可能的情況是什么à模型中變量數(shù)盡可能少, 它們之間相互 “求小于N的最大素?cái)?shù)” 中的條件是 “n不能被2,n)中

3、任意一個(gè)素?cái)?shù)整除” 而不是 “n不能被2,n)中任意一個(gè)整數(shù)整除”6枚舉中三個(gè)關(guān)鍵問題問題二減少搜索的空間利用知識縮小模型中各變量的取值范圍, 避免不必要的計(jì)算à減少代碼中循環(huán)體執(zhí)行次數(shù) 除2之外, 只有奇數(shù)才可能是素?cái)?shù), 2,2*i+1|1<=i, 2*i+1<n7枚舉中三個(gè)關(guān)鍵問題問題三采用合適的搜索順序搜索空間的遍歷順序要與模型中條件表達(dá)式一致 對2,2*i+1|1<=i, 2*i+1<n按照從小到大的順序8中國古代的枚舉問題百錢百雞問題 雞值錢五, 雞值, 雞雛三值錢一.百錢買百雞, 問雞翁, 雞母, 雞雛各幾何建算經(jīng) 求解方法: 先構(gòu)造可能的解的集合 S=(X,Y,Z)|0<=X,Y,Z<=100X, Y, Z分別代表買公雞, 母雞和小雞的只數(shù) 然后驗(yàn)證條件X+Y+Z