第2節(jié) 枚舉、解析算法及其程序?qū)崿F(xiàn)(A)

1、第四單元算法的程序?qū)崿F(xiàn)第四單元算法的程序?qū)崿F(xiàn) A枚舉算法及其程序?qū)崿F(xiàn)枚舉算法及其程序?qū)崿F(xiàn) 1枚舉算法枚舉算法又稱為窮舉法，其基本思想是根據(jù)問題的本身性質(zhì)，一一列出該問題所有可能的情況，并根據(jù)條件逐個(gè)做出判斷，從中挑選出符合條件的解。枚舉就是將問題的可能解一個(gè)一個(gè)地列舉，逐一判斷，即使中途找到符合解也要繼續(xù)找下去，將所有可能都找完才結(jié)束。2枚舉算法的特點(diǎn)(1)不能遺漏任何一個(gè)真正解，這是問題本身所要求的；(2)設(shè)計(jì)算法時(shí)要盡可能小的范圍內(nèi)羅列出所有可能的情況，不能遺漏，也不能重復(fù)。(3)在使用VB程序解決枚舉算法問題時(shí)，主要是由循環(huán)語句(如用For語句，通過循環(huán)語句在一定的范圍內(nèi)，以一定的方式羅

2、列所有的可能解)和選擇語句(如用If語句對(duì)一個(gè)可能解是否是問題的真正解進(jìn)行判斷和選擇)的適當(dāng)組合來完成的。 3枚舉算法的程序?qū)崿F(xiàn)高中階段，對(duì)于較為復(fù)雜的枚舉算法問題，一般通過雙重循環(huán)來實(shí)現(xiàn)。雙重循環(huán)在使用時(shí)，每個(gè)循環(huán)必須有一個(gè)唯一的變量名作為循環(huán)變量；在Next語句結(jié)束循環(huán)時(shí)，必須是內(nèi)層的循環(huán)語句先結(jié)束，不得出現(xiàn)互相交叉，如下循環(huán)結(jié)構(gòu)中，語句“Next j”與語句“Next i”順序不能調(diào)換。 該程序段運(yùn)行時(shí)，外循環(huán)中變量i每取一個(gè)值，都要執(zhí)行一次完整的內(nèi)循環(huán)(即內(nèi)循環(huán)都要循環(huán)一次)。 【例1】一張單據(jù)上有一個(gè)5位數(shù)的編號(hào)，其百位數(shù)和十位數(shù)處模糊不清(如圖a所示)，但已知該5位數(shù)是37或67的

3、倍數(shù)。設(shè)計(jì)算法，找出所有滿足這些條件的5位數(shù)，并統(tǒng)計(jì)這些5位數(shù)的個(gè)數(shù)。算法分析：(1)設(shè)計(jì)過程：在這個(gè)5位數(shù)的百位和十位上分別填上兩個(gè)十進(jìn)制數(shù)字，它就生成了一個(gè)可能解n，然后判斷n是否是一個(gè)真正解，即n能否被37或67整除。若n是真正解，則輸出n的值，并在計(jì)數(shù)器c中加1，表示找到一個(gè)真正解。圖a (2)枚舉過程：在5位數(shù)的百位和十位上依次填入00、01、02、97、98、99，這100個(gè)不同的數(shù)，從而產(chǎn)生出全部可能解：25006、25016、25026、25986、25996。在計(jì)算過程中使用循環(huán)處理模式，讓變量i依次取0到99這100個(gè)不同的值，同時(shí)對(duì)于i的每個(gè)確定的值乘以10并加上2500

4、6，形成一個(gè)可能解n。對(duì)于每個(gè)可能解n，只要判斷它是否能被37或67整除，就能確定它是否是一個(gè)真正解了。 算法對(duì)應(yīng)流程圖如圖b所示，其中各變量含義為：i：循環(huán)變量，用來控制循環(huán)是否繼續(xù)進(jìn)行，并在循環(huán)處理過程中用來記錄已經(jīng)進(jìn)行的循環(huán)的次數(shù)；依次產(chǎn)生應(yīng)填在百位和十位上的數(shù)值。c：計(jì)數(shù)器，用于記錄算法執(zhí)行過程中已經(jīng)找到的真正解的個(gè)數(shù)。n：存儲(chǔ)一個(gè)可能解。 圖b 根據(jù)上述分析，并結(jié)合流程圖，請(qǐng)?jiān)趧澗€處填入合適代碼。Private Sub Command1_Click()Dim i As IntegerDim c As Integer, n As Integerc 0For i _n 25006 _If

5、 n Mod 37 0 _ n Mod 67 0 Thenc c 1List1.AddItem _End IfNext iText1.Text Str(c)End Sub 【例1解題】根據(jù)流程圖，i取值范圍為099，故處答案為0 To 99；產(chǎn)生可能數(shù)據(jù)為25006、25016、25026、25986、25996，故處答案為i*10；根據(jù)篩選條件“n是37或是67的倍數(shù)”可知處答案為Or；列表框List1中輸出符合要求的n的值，因此處答案為Str(n)?！敬鸢?】_ 0 To 99 i*10 Or Str(n) 【例2】包裝1200個(gè)玩具，要求是：(1)包裝的規(guī)格分別是：小盒(每盒5個(gè))和大盒

6、(每盒12個(gè))。(2)每種規(guī)格的盒數(shù)可任意，但每盒都必須裝滿。設(shè)計(jì)一個(gè)算法，輸出所有“總的盒數(shù)不超過n(包含n)”的包裝方案，并輸出包裝方案的個(gè)數(shù)。算法分析：(1)設(shè)1200個(gè)玩具分別裝入x個(gè)小盒和y個(gè)大盒，它們必須滿足等式5x12y1200。(2)考慮x、y值可能的變化范圍：x為0240，y為0100。(3)采用了雙重循環(huán)來枚舉，外層的For循環(huán)當(dāng)x取值為0時(shí)，內(nèi)層的For循環(huán)完整執(zhí)行一次，即y取值為0100之間的整數(shù)，然后判斷這些y與x的組合是否滿足兩個(gè)條件5x12y1200且xyn，若滿足，則在列表框List1中輸出x、y的值，并使方案個(gè)數(shù)1，一次內(nèi)循環(huán)結(jié)束后，外循環(huán)變量x增加1，再次執(zhí)

7、行一次完整的內(nèi)層For循環(huán)，y取值仍為0100之間的整數(shù)，如此反復(fù)，將x在0240之間取值和y在0100之間取值的所有可能組合都判斷是否滿足條件5x12y1200且xyn，若條件成立，則在在列表框List1中輸出一組x、y的值并使方案個(gè)數(shù)1。請(qǐng)?jiān)趧澗€處填入合適代碼。Private Sub Command1_Click()Dim x As Integer, y As Integer, c As Integer, n As Integer, z As IntegerList1.AddItem ”總盒數(shù)不超過” Text1.Text ”的方案” n _c 0真正解個(gè)數(shù)的計(jì)數(shù)器預(yù)置初值0For x 0

8、 To 240For y 0 To 100If 5 * x 12 * y 1200 And _ Then檢驗(yàn)x、y是否是真正解List1.AddItem Str(x) ” Str(y)c c 1Exit ForEnd IfNext yNext xText2.Text _End Sub【例2解題】n的值來自文本框Text1的數(shù)值，因此處答案為Val(Text1.Text)；對(duì)于枚舉的x、y的值要同時(shí)滿足5x 12y 1200和x y n，變量c用來統(tǒng)計(jì)方案數(shù)，文本框Text2中輸出的是方案數(shù)，故Text2.Text Str(c)?！敬鸢?】_ x y 0If _ Then m1 m1 1 Els

9、e m2 m2 1n n 2LoopIf _ Then ss1Next iText1.Text _End Sub 【例4解題】本題屬于稍難題，主要考查學(xué)生對(duì)程序的綜合應(yīng)用能力。該程序段為雙重循環(huán)結(jié)構(gòu)，外循環(huán)實(shí)現(xiàn)枚舉前1000個(gè)自然數(shù)，十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)采用除二取余法，內(nèi)循環(huán)用來判斷每次除2后的余數(shù)是否為0，如果是就在變量m1中累加1，否則在變量m2中累加1，故處答案為n Mod 2 0；變量s用來統(tǒng)計(jì)A類數(shù)的個(gè)數(shù)，當(dāng)滿足數(shù)字“1”的個(gè)數(shù)多于數(shù)字“0” 的個(gè)數(shù)時(shí)為A類數(shù)，即滿足條件m1 m2；最后將統(tǒng)計(jì)的結(jié)果s賦值給文本框，故處答案為Str(s)?！敬鸢?】_ n Mod 2 0 m1 m2

10、 Str(s) 【例5】某木材加工廠需要把購入的木料切割成長度為3米和7米兩種規(guī)格的線材?，F(xiàn)要求編寫VB程序(運(yùn)行界面如圖所示)，實(shí)現(xiàn)如下功能：在文本框Text1中輸入木材長度，單擊“計(jì)算”按鈕Command1，計(jì)算出一種廢料長度最小的切割方案，在文本框Text2和文本框Text3中分別輸出該切割方案所得3米和7米兩種規(guī)格線材的數(shù)量。按此要求編寫的程序如下。但加框處代碼有錯(cuò)，請(qǐng)改正。 Private Sub Command1_Click()Dim length As Single木料長度Dim min As Single 最小廢料長度Dim x As Integer 3米規(guī)格線材數(shù)量Dim y As Integer 7米規(guī)格線材數(shù)量Dim f As Single 廢料長度Dim a As Integer 廢料最少的切割方案所得3米規(guī)格線材數(shù)量Dim b As Integer 廢料最少的切割方案所得7米規(guī)格絨材數(shù)量length Val(Text1.Text)min lengthFor x0 To length3y(length3*x)7 (1)If fmin Thenminfax (2)End IfNext xText2.TextStr(a)Text3.TextStr(b)End Sub 【例5解題】根據(jù)題意可知，要得到廢料長度最小的切割