第05章編程思維與方法訓(xùn)練

1、第5章 編程思維與方法訓(xùn)練本章內(nèi)容提示：本章以程序設(shè)計(jì)中常見典型問題為例，講解程序設(shè)計(jì)中問題分析，編程基本思路，基本算法設(shè)計(jì)描述，代碼編程實(shí)現(xiàn)和程序算法的優(yōu)化，說明程序設(shè)計(jì)的一般思想和方法。本章內(nèi)容是對(duì)前面所學(xué)程序設(shè)計(jì)基礎(chǔ)知識(shí)的提升，分類介紹常見幾類典型問題程序設(shè)計(jì)的思想、方法和規(guī)律，并對(duì)同類問題程序設(shè)計(jì)方法進(jìn)行總結(jié)。教學(xué)基本要求：學(xué)會(huì)典型問題的分析，理解問題抽象出的本質(zhì)（模型），掌握問題的求解思路、算法設(shè)計(jì)和編程方法，通過編程練習(xí)、上機(jī)調(diào)試程序，掌握程序設(shè)計(jì)的一般思維和實(shí)現(xiàn)方法，培養(yǎng)用計(jì)算機(jī)解決問題的能力。5.1 程序設(shè)計(jì)的一般方法利用計(jì)算機(jī)處理問題的一般過程是：首先對(duì)各類具體問題進(jìn)行仔細(xì)研

2、究和分析，確定解決問題的具體方法和步驟（算法），然后依據(jù)方法和步驟，選擇某種計(jì)算機(jī)語言，依據(jù)算法編寫程序，提交計(jì)算機(jī)執(zhí)行，讓計(jì)算機(jī)按照人們指定的步驟有效的工作。例如編程求解猴子吃桃問題：猴子第一天摘下若干個(gè)桃子，當(dāng)即吃掉一半，還不過癮，又多吃了一個(gè)，第二天早上又將剩下的桃子吃掉一半，又多吃一個(gè)，以后每天早上都吃掉前一天剩下的一半又多一個(gè)。直到第10天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問猴子第一天共摘了多少個(gè)桃子？（1）問題分析：設(shè)第一天的桃子數(shù)為peach1，第二天桃子數(shù)為peach2，第十天的桃子數(shù)為peach10。已知peach10=1，而peach10=peach9/2-1，則peach9=

3、2(peach10+1),同理可得peach8=2(peach9+1),依次類推，可得peach1=2(peach2+1)。由此可見，peach1,peach2,peach10之間存在關(guān)系：peachi=2(peachi+1+1),i=9,8,2,1,即每項(xiàng)可由它的前一項(xiàng)計(jì)算得出。用計(jì)算機(jī)計(jì)算時(shí)可用式子 peach=2*(peach+1)求解，賦初值peach=1，運(yùn)算一次可計(jì)算得到peach=4即第9天的桃子數(shù)，再次運(yùn)算，代入式子右邊的peach為第9天的桃子數(shù)，可求得第8天的桃子數(shù)，依次計(jì)算9次，可得第一天的桃子數(shù)。（2）經(jīng)過分析，可得算法：S1:使peach=1；S2:使i=9;S3:計(jì)

4、算peach=2*(peach+1)S4:i=i-1S5:如果i=1,返回重新執(zhí)行步驟S3；否則，執(zhí)行S6。S6:打印peach這樣的算法已經(jīng)可以很方便的轉(zhuǎn)化成相應(yīng)的程序語句了。（3）基于算法編寫的程序如下： Dim peach%, i% peach = 1 i = 9 Do peach = 2 * (peach + 1) i = i - 1 Loop While i = 1Print peach（4）進(jìn)行文檔說明，對(duì)較小的程序，需要養(yǎng)成對(duì)所設(shè)計(jì)的程序或系統(tǒng)進(jìn)行注釋習(xí)慣，以便于自己和其他人以后進(jìn)行閱讀和修改。例如程序可注釋如下：Rem 本程序設(shè)計(jì)于2013.4.28，由張三設(shè)計(jì)。Rem 本程序

5、實(shí)現(xiàn)的問題是：猴子吃桃問題：猴子第一天摘下若干個(gè)桃子，當(dāng)即吃掉一半，還不過癮，又多吃了一個(gè)，第二天早上又將剩下的桃子吃掉一半，又多吃一個(gè)，以后每天早上都吃掉前一天剩下的一半又多一個(gè)。直到第10天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問猴子第一天共摘了多少個(gè)桃子？Dim peach%, i%peach = 1 賦初值，第10天的桃子數(shù)為1i = 9 循環(huán)變量賦初值，從第9天開始計(jì)算。Do 控制循環(huán)9次，依次計(jì)算第9,8,7,1天數(shù)的桃子數(shù) peach = 2 * (peach + 1) 遞推公式 i = i - 1Loop While i = 1Print peach 打印第一天的桃子數(shù)程序設(shè)計(jì)一般步驟

6、如下：（1）分析問題對(duì)求解問題進(jìn)行認(rèn)真的理解，研究所給定的條件，分析最后應(yīng)達(dá)到的目標(biāo)，找出解決問題的規(guī)律，選擇解題的方法，達(dá)到實(shí)際問題求解的要求。在分析求解問題的基礎(chǔ)上，將所研究問題的數(shù)據(jù)與數(shù)據(jù)間關(guān)系抽象出來，形成程序中數(shù)據(jù)的類型和數(shù)據(jù)組織存儲(chǔ)形式。（2）設(shè)計(jì)算法算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。設(shè)計(jì)算法即設(shè)計(jì)出解題的方法和具體步驟?？捎昧鞒虉D等方法描述算法，為編寫程序代碼做好準(zhǔn)備工作。（3）編寫程序依據(jù)算法和流程圖，用程序設(shè)計(jì)語言將整個(gè)數(shù)據(jù)、數(shù)據(jù)之間的關(guān)系和算法表述出來，形成程序代碼。（4）調(diào)試運(yùn)行將程序輸入計(jì)算機(jī)，進(jìn)行編輯、調(diào)試和運(yùn)行

7、。（5）分析結(jié)果對(duì)程序執(zhí)行結(jié)果進(jìn)行驗(yàn)證和分析，發(fā)現(xiàn)程序中存在問題并修改完善。（6）寫出程序的文檔程序是提供給用戶使用的，如同正式的產(chǎn)品應(yīng)當(dāng)提供產(chǎn)品說明書一樣，正式提供給用戶使用的程序，必須向用戶提供程序說明書。內(nèi)容應(yīng)包括：程序名稱、程序功能、運(yùn)行環(huán)境、程序的裝入和啟動(dòng)、需要輸入的數(shù)據(jù)，以及使用注意事項(xiàng)等，為程序的使用、修改做好基礎(chǔ)工作。5.2 一般計(jì)算問題在進(jìn)行程序設(shè)計(jì)時(shí)，通常會(huì)遇到需要通過簡(jiǎn)單累加、累積、計(jì)數(shù)或統(tǒng)計(jì)等進(jìn)行求解的問題，這類問題關(guān)鍵是確定每次累加（乘）、統(tǒng)計(jì)的操作是什么，通過循環(huán)方式實(shí)現(xiàn)多次重復(fù)操作，從而得到運(yùn)算結(jié)果，這是程序設(shè)計(jì)中的最基本問題之一。5.2.1累加、累積若求解問題

8、通過分析后，其本質(zhì)是累加、累積問題，程序設(shè)計(jì)的基本思路是：首先，確定每次累加（乘）的對(duì)象（數(shù)據(jù)）是什么；其次，這些對(duì)象具有何種規(guī)律，將其表示成有規(guī)律的形式，構(gòu)造出運(yùn)算數(shù)據(jù)對(duì)象的表達(dá)式（如x=x+1）；再次，每次運(yùn)算有何種規(guī)律，將其表示成有規(guī)律的運(yùn)算形式，構(gòu)造出累加（乘）的運(yùn)算表達(dá)式（s=s+x），構(gòu)成重復(fù)操作的內(nèi)容；最后，確定實(shí)現(xiàn)重復(fù)運(yùn)算的控制方法（循環(huán)控制）。在上述思路的基礎(chǔ)，設(shè)計(jì)求解問題算法，依據(jù)算法編寫程序。圖5-1 求階乘N流程圖輸入n的值是x=x+1f=f*x計(jì)數(shù)器x=0、累乘器f初始化為1xn輸出階乘f例5-1 求任意數(shù)n的階乘?；谏鲜龅幕舅悸?，階乘問題分析和求解基本方法是：

9、（1）n!=1*2*3*n，每次相乘的數(shù)分別為1,2,3,n,每一項(xiàng)相乘的數(shù)據(jù)有一個(gè)變化規(guī)律：是一個(gè)自然數(shù)，如果i的初值為0，可以用式子x=x+1構(gòu)造所有要累乘每一項(xiàng)數(shù)據(jù)，一次產(chǎn)生一個(gè)自然數(shù)x；（2）每次累乘的數(shù)是x，可以用f=f*x構(gòu)造累乘運(yùn)算表達(dá)式，每次實(shí)現(xiàn)一個(gè)數(shù)據(jù)的累乘；（3）計(jì)算n個(gè)x累乘，則需要循環(huán)操作n次，構(gòu)造執(zhí)行n次的循環(huán)控制。本例可參照第3章例3-11問題“1+2+3+10”的算法分析，若將問題看做是1*2*3*n，只需要將f初始值設(shè)為1，將s=s=+x改為f=f*x。流程圖如圖5-1所示，程序代碼如下。Private Sub Command1_Click() Dim n As

10、 Integer, x As Integer, f As Integer n = Val(InputBox(請(qǐng)輸入n的值) x = 0 累乘數(shù)據(jù)變量的初始為值0 f = 1 累乘結(jié)果變量初始值為1 Do While x n 循環(huán)控制，執(zhí)行n次循環(huán) x = x + 1 構(gòu)造累乘的數(shù)據(jù) f = f * x 累乘運(yùn)算 Loop Print f=; fEnd Sub注意：這里的n不能太大，否則會(huì)出現(xiàn)“溢出”錯(cuò)誤。因?yàn)槔鄯e器f的數(shù)據(jù)類型為整型，能存放的最大整數(shù)為32767，如果要計(jì)算的n較大時(shí)，可將f的數(shù)據(jù)類型改為長整型、單精度型或雙精度型。以下同類題目與上例算法相同，對(duì)累加的數(shù)x進(jìn)行適當(dāng)變換，注意數(shù)據(jù)

11、類型：1. (累加為：f=f+1/x) 或（將x變換為：i=i+1：x= 1/i）2. 1！+2！+3！+.+n! （增加累加運(yùn)算的語句s=s+f）3. （累加為：f=f+1/( x*（x+1）4.用公式求的近似值，直到最后一項(xiàng)的絕對(duì)值小于10-6為止。對(duì)累加和累乘的題目，總結(jié)如下：（1）用一個(gè)或若干個(gè)語句（x=x+1）運(yùn)算產(chǎn)生要累乘或累加的每一項(xiàng)；（2）用一個(gè)語句，如f=f*x（f=f+x），將產(chǎn)生的項(xiàng)累加或累乘起來。（3）依據(jù)題目命題，結(jié)合前面兩項(xiàng)，構(gòu)造合適的循環(huán)語句和條件。通過本節(jié)分析舉例，對(duì)同類問題可以達(dá)到舉一反三的效果。5.2.2 計(jì)數(shù)與統(tǒng)計(jì)若求解問題的結(jié)果是計(jì)數(shù)或統(tǒng)計(jì)，通過分析后，

12、其本質(zhì)是計(jì)數(shù)（簡(jiǎn)單累加：n=n+1）、統(tǒng)計(jì)（分類計(jì)數(shù)、累加s=s+x或求均值p=s/n等）。程序設(shè)計(jì)的基本思路是：首先，確定每次計(jì)數(shù)或統(tǒng)計(jì)的處理對(duì)象是什么；其次，這些對(duì)象進(jìn)行處理（統(tǒng)計(jì)或計(jì)數(shù)）依據(jù)是什么，有哪些處理?xiàng)l件；再次，將其處理過程表示成有規(guī)律的形式，構(gòu)造統(tǒng)計(jì)或計(jì)數(shù)運(yùn)算的表達(dá)式，形成每次重復(fù)操作的內(nèi)容（循環(huán)體）；最后，確定實(shí)現(xiàn)重復(fù)運(yùn)算的控制方法（循環(huán)控制）。例5-2 從鍵盤上輸入若干個(gè)數(shù)，求其平均值。分析：求若干個(gè)數(shù)的平均值，需要對(duì)數(shù)據(jù)累加求和，并對(duì)累加數(shù)據(jù)進(jìn)行計(jì)數(shù)，然后計(jì)算得到平均值，問題的本質(zhì)是累加（s=s+x），計(jì)數(shù)（n=n+1）?；舅悸泛颓蠼饣痉椒ǎ海?）設(shè)統(tǒng)計(jì)的數(shù)為x，通過

13、鍵盤輸入；（2）處理要求是對(duì)每個(gè)數(shù)據(jù)x需要進(jìn)行累加，同時(shí)進(jìn)行計(jì)數(shù)；（3）處理過程可以表示為（s=s+x：n=n+1）；（4）確定控制循環(huán)執(zhí)行的條件。由于要進(jìn)行累加與統(tǒng)計(jì)數(shù)據(jù)個(gè)數(shù)，需要設(shè)置兩個(gè)變量sum、n，可以分別稱它們?yōu)槔奂悠髯兞縮um和計(jì)數(shù)器變量n，與上題不同的是累加器變量中累加的是從鍵盤輸入的數(shù)據(jù)。它們的初值一般為0。對(duì)于不固定個(gè)數(shù)的數(shù)求和，其累加、計(jì)數(shù)的次數(shù)也不固定，應(yīng)采用Do循環(huán)。為了使循環(huán)能夠結(jié)束，需設(shè)定一個(gè)結(jié)束標(biāo)志，本題可設(shè)置-9999（結(jié)束標(biāo)志應(yīng)選擇遠(yuǎn)離有效數(shù)據(jù)為宜）做結(jié)束標(biāo)志。代碼如下： Private Sub Command1_Click() Dim sum!, n%, x

14、!, aver! sum = 0 累加器初值置0 n = 0 計(jì)數(shù)器初值置0 x = Val(InputBox(請(qǐng)輸入：) 輸入第1個(gè)數(shù) Do While x -9999 sum = sum + x n = n + 1 x = Val(InputBox(請(qǐng)輸入：) 輸入下1個(gè)數(shù) Loop aver = sum / n MsgBox 共輸入 & n & 個(gè)數(shù)，平均值為： & averEnd Sub從分析可以看出循環(huán)體外的InputBox()，用來輸入求和的第1個(gè)數(shù)，目的是為進(jìn)入循環(huán)；循環(huán)體內(nèi)InputBox()函數(shù)用來輸入除第1個(gè)數(shù)以外的其他數(shù)及結(jié)束標(biāo)志-9999，目的是維持循環(huán)并最后能夠結(jié)束循

15、環(huán)。如果在本題中第1次輸入數(shù)據(jù)時(shí)就輸入-9999，會(huì)出現(xiàn)錯(cuò)誤，請(qǐng)讀者思考出錯(cuò)的原因？如果將程序修改成：Dim sum!, n%, x!, aver!sum = 0n = 0Do While x -9999 x = Val(InputBox(請(qǐng)輸入：) sum = sum + x n = n + 1Loopaver = sum / nMsgBox 這些數(shù)的平均值為： & aver程序又會(huì)出現(xiàn)什么問題呢？請(qǐng)大家試一試。本例學(xué)習(xí)的重點(diǎn)：在循環(huán)次數(shù)未知的情況下使用輸入循環(huán)標(biāo)志結(jié)束循環(huán)的方法。例5-3 輸入多名學(xué)生的一門課程的考試成績（假設(shè)為整數(shù)），統(tǒng)計(jì)各分?jǐn)?shù)段學(xué)生人數(shù)。在計(jì)算機(jī)數(shù)據(jù)處理中，如果需要多個(gè)

16、計(jì)數(shù)器，可以考慮使用一維數(shù)組，利用數(shù)組元素充當(dāng)計(jì)數(shù)器進(jìn)行多項(xiàng)計(jì)數(shù).問題分析：學(xué)生人數(shù)無法預(yù)先知道，因此應(yīng)采用動(dòng)態(tài)數(shù)組存儲(chǔ)學(xué)生成績，輸入數(shù)據(jù)時(shí)采用文本框輸入，便于數(shù)據(jù)的編輯。本例是要統(tǒng)計(jì)各分?jǐn)?shù)段（11段）的人數(shù)，所以要使用的計(jì)數(shù)器變量不止一個(gè)（11個(gè)），可以考慮用一維數(shù)組的數(shù)組元素作為計(jì)數(shù)器，通過巧妙的使用進(jìn)行計(jì)數(shù)和批量處理?！敖y(tǒng)計(jì)”按鈕用于將錄入的數(shù)據(jù)保存在一維數(shù)組中，并完成統(tǒng)計(jì)處理和結(jié)果輸出。程序運(yùn)行界面如圖5-2。圖5-2 例5-3運(yùn)行結(jié)果Private Sub Command1_Click() Dim a$() Dim x(0 To 10) As Integer 數(shù)組元素充當(dāng)計(jì)數(shù)器，保存

17、統(tǒng)計(jì)結(jié)果 a = Split(Text1, ,) For i = 0 To UBound(a) If (a(i) 0) Then k = a(i) 10 x(k) = x(k) + 1 End If Next i Print 統(tǒng)計(jì)結(jié)果如下：Print 100分的有： & x(10) & 人For i = 9 To 0 Step -1 Print i * 10 & 分 - ; i * 10 + 9 & 分有： & x(i) & 人Next iEnd SubPrivate Sub Command2_Click()EndEnd Sub請(qǐng)反復(fù)錄入數(shù)據(jù)試運(yùn)行程序，體會(huì)成績分段統(tǒng)計(jì)技巧。讀者可以思考，如果

18、用多分支選擇結(jié)構(gòu)對(duì)各分?jǐn)?shù)段的成績進(jìn)行統(tǒng)計(jì)，程序代碼又該如何編寫呢？例5-4 輸入一串字符，統(tǒng)計(jì)各字母出現(xiàn)的次數(shù)（不區(qū)分大小寫），并輸出統(tǒng)計(jì)結(jié)果，如圖5-3。分析：統(tǒng)計(jì)26個(gè)字母出現(xiàn)的次數(shù)，需要26個(gè)計(jì)數(shù)器，可以聲明一個(gè)具有26個(gè)元素的一維數(shù)組。算法如下：（1）用取子串函數(shù)Mid(Text1, i, 1)從Text1中取出每一個(gè)字符，并轉(zhuǎn)換成大寫字母；（2）將AZ之間的大寫字母用Asc()函數(shù)轉(zhuǎn)換成ASCII碼值，再根據(jù)ASCII碼值為相圖5-3 例5-4運(yùn)行結(jié)果應(yīng)的數(shù)組元素計(jì)數(shù)。代碼如下：Private Sub Command1_Click() Dim a%(65 To 90), c As S

19、tring * 1 le = Len(Text1) For i = 1 To le c = UCase(Mid(Text1, i, 1) 分離出的字母轉(zhuǎn)換成大寫字母，方便統(tǒng)計(jì) If c = A And c 0 Then Picture1.Print ; Chr(j); =; a(j); ; Next jEnd Sub本例說明VB中數(shù)組定義中下標(biāo)可以從任意整數(shù)開始。5.2.3 計(jì)算定積分例5-5 求xy0abhhhf(a)xf(x)圖5-4 定積分求解幾何示意圖求一個(gè)函數(shù)f(x)在a,b上的定積分，其幾何意義是求f(x)曲線和直線x=a, y=0, x=b所圍成的曲邊圖形的面積，如圖5-4所示。

20、問題分析：為了近似求出此面積，可將a,b區(qū)間分成若干個(gè)小區(qū)間，可用矩形法或梯形法等近似求出每個(gè)小的曲邊圖形的面積，每個(gè)區(qū)間的寬度為h=(b-a)/n（n為區(qū)間個(gè)數(shù)）。然后將n個(gè)小面積加起來，就近似求得總面積，即定積分的近似值。n愈大，計(jì)算的結(jié)果越接近實(shí)際值。近似求出小曲邊圖形面積的方法，常用的有以下三種： 用小矩形代替小曲邊圖形，求出各小矩形的面積，然后累加。 用小梯形代替小曲邊圖形，求出各小梯形的面積，然后累加。 在小區(qū)間范圍內(nèi)，用一條直線代替該區(qū)間內(nèi)的拋物線，然后求出該直線與x=a+(i-1)h，y=0，x=a+ih形成的小曲邊圖形面積（1）矩形法求面積矩形法求積分值是將積分區(qū)間a,b n

21、 等分，小區(qū)間的寬度為，第i塊小矩形的面積是：。程序設(shè)計(jì)的基本思路： 設(shè)置區(qū)間a,b,確定區(qū)間等分n的值，計(jì)算區(qū)間寬度h， 第1個(gè)區(qū)間矩形坐標(biāo)為x，則x=a，其對(duì)應(yīng)的函數(shù)值f(x)為矩形的一邊長度；圖5-5 矩形法求定積分值流程圖否是iN，則交換M、N的值否是x=1循環(huán)控制變量x=Nx整除M、N輸出最大公約數(shù)x退出循環(huán)x=x+1是若兩個(gè)整數(shù)為m和n，假設(shè)mn，設(shè)x為最小公倍數(shù)，則可能為最小公倍數(shù)x的取值范圍為m，m*n，可用窮舉法的辦法求解?；舅悸罚海?）列舉出可能是m、n最小公倍數(shù)x的情況，則x的取值情況為m，m*n；（2）依據(jù)公倍數(shù)的定義，判斷x的每個(gè)取值是否滿足條件：x能同時(shí)被m和n整

22、除；（3）若能整除，x取值為最小公倍數(shù)，求解結(jié)束；（4）通過循環(huán)操作實(shí)現(xiàn)窮舉每個(gè)x取值情況；基本算法：（1）對(duì)x從m開始的每一個(gè)可能的取值，判斷能否同時(shí)被m、n整除（即是否是公倍數(shù)）；（2）若是，x必定是m和n的最小公倍數(shù)，程序運(yùn)行結(jié)束；（3）如果不是，則判斷下一個(gè)x；（4）依次類推，直到x的取值為m*n為止。最大公約數(shù)算法與最小公倍數(shù)類似，設(shè)y為最大公約數(shù)，y的范圍是1，n，程序?qū)崿F(xiàn)時(shí)，y的取值從n開始，判斷過程與求最小公倍數(shù)類似，流程圖如圖5-6所示，代碼如下：Private Sub Command1_Click() Dim m%, n% m = Val(InputBox(請(qǐng)輸入第1個(gè)數(shù)m

23、：) n = Val(InputBox(請(qǐng)輸入第2個(gè)數(shù)n：) If m n For x = m To m * n 最小公倍數(shù)，xm,m*n If x Mod m = 0 And x Mod n = 0 Then Print 最小公倍數(shù)為：; x Exit For 結(jié)束循環(huán) End If Next x For y = n To 1 Step -1 y取值范圍為n1 If m Mod y = 0 And n Mod y = 0 Then Print 最大公約數(shù)為：; y Exit For 結(jié)束循環(huán) End If Next yEnd Sub這種方法效率較低，求最大公約數(shù)可采用經(jīng)典的“輾轉(zhuǎn)相除法”，并

24、在求出最大公約數(shù)后，最小公倍數(shù)就等于兩個(gè)原數(shù)的乘積除以最大公約數(shù)。算法描述如下：（1）將m除以n得余數(shù)r；（2）若r=0，則n為求得的最大公約數(shù)，循環(huán)結(jié)束；若r0，則執(zhí)行（3）；（3）將n賦給m，將r賦給n，再重執(zhí)行（1）、（2）步。代碼如下：Private Sub Command1_Click() Dim m%, n%, r% m = Val(InputBox(請(qǐng)輸入第1個(gè)數(shù)m：) n = Val(InputBox(請(qǐng)輸入第2個(gè)數(shù)n：) mn = m * n r = m Mod n Do While r 0 m = n n = r r = m Mod n Loop MsgBox 兩個(gè)數(shù)的最大

25、公約數(shù)為 & n & ，最小公倍數(shù)為 & mn / nEnd Sub本例因?yàn)樵谘h(huán)過程中由于改變了m、n的值，所以先將m*n的值放入變量mn中。讀者可以比較一下兩種算法的循環(huán)次數(shù)。窮舉法是基于計(jì)算機(jī)特點(diǎn)而進(jìn)行解題的思維方法，一般是根據(jù)問題中的部分條件（約束條件）將所有可能解的情況列舉出來，然后通過一一驗(yàn)證是否符合整個(gè)問題的求解要求，從而得到問題的解。窮舉法一般解題模式為：（1）問題解的可能搜索的范圍：用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實(shí)現(xiàn)；此問題用計(jì)算機(jī)進(jìn)行求解時(shí)一般使用窮舉驗(yàn)證的方法進(jìn)行。（2）寫出符合問題解的條件； （3）能使程序優(yōu)化的語句，以便縮小搜索范圍，減少程序運(yùn)行時(shí)間。 5.3.2 質(zhì)數(shù)質(zhì)數(shù)也叫

26、素?cái)?shù)，是指只能被1和它本身整除的自然數(shù)。最小的質(zhì)數(shù)是2。例5-7 從鍵盤輸入一個(gè)數(shù)m，判斷是否為質(zhì)數(shù)。問題分析：判斷一個(gè)數(shù)m是否為質(zhì)數(shù)的方法很多，最基本的是從質(zhì)數(shù)的定義來求解，設(shè)x為可能整除m的數(shù)，則x取值范圍為2，m-1，可用窮舉法求解?；舅悸罚海?）列舉出可能整除m的數(shù)x的情況，則x取值情況為2，m-1；（2）判斷x的每個(gè)取值情況：x是否能整除m；（3）若能整除，則m不是質(zhì)數(shù)，不再進(jìn)行判斷；（4）若不能整除，則需要進(jìn)行下一個(gè)x判斷；（5）通過循環(huán)操作實(shí)現(xiàn)窮舉每個(gè)x取值情況。（6）結(jié)果判讀，在循環(huán)處理過程中，若都不能整除m，則m為素?cái)?shù)，只要其中有一個(gè)數(shù)能整除m，則m就不是質(zhì)數(shù)。否是輸入M的

27、值Flag=Ture（假設(shè)M為質(zhì)數(shù)）否是x=M-1循環(huán)控制變量x=2M整除xFlag=false退出循環(huán)x=x+1是圖5-7 求質(zhì)數(shù)流程圖是end否flag=TureM是質(zhì)數(shù)M不是質(zhì)數(shù)基本算法：（1）輸入m，設(shè)置標(biāo)志flag=True，默認(rèn)m為質(zhì)數(shù)；（2）x從2開始取值，判斷x能否整除m；（3）若整除，則m不是質(zhì)數(shù)，設(shè)置標(biāo)志位false，結(jié)束判斷；（4）若不整除，則判斷下一個(gè)x，即x=x+1；（5）依次類推，直到x的取值為m-1為止。（6）依據(jù)flag標(biāo)志，若flag為True，則m為質(zhì)數(shù)，否則m不是質(zhì)數(shù)。流程圖如圖5-7所示，程序代碼如下：Private Sub Command1_Click

28、() Dim m%, i%, flag As Boolean m = Val(InputBox(請(qǐng)輸入要判斷的整數(shù)m) flag = True 先假設(shè)m是質(zhì)數(shù) For x = 2 To m - 1 If m / x = m x Then flag = False x整除m，則m為非質(zhì)數(shù) Exit For m不是質(zhì)數(shù)，結(jié)束循環(huán)判斷 End If Next x If flag = True Then MsgBox m & 是質(zhì)數(shù) Else MsgBox m & 不是質(zhì)數(shù) End IfEnd Sub實(shí)際上，依據(jù)質(zhì)數(shù)定義判斷一個(gè)數(shù)m是否為質(zhì)數(shù)，x的取值范圍 2,m-1, 通過數(shù)學(xué)知識(shí)推導(dǎo)可知，x的取值

29、范圍2,m/2,這樣，循環(huán)次數(shù)可以減少為原來一半。數(shù)學(xué)已經(jīng)證明，判斷的取值范圍可以是2, ，這樣可進(jìn)一步減少循環(huán)次數(shù)，通過優(yōu)化算法，以便縮小窮舉的搜索范圍，減少程序運(yùn)行時(shí)間。5.3.3 不定方程求解例5-8 我國古代數(shù)學(xué)家張丘建在算經(jīng)中提出一個(gè)不定方程問題，即“百雞問題”：公雞每只值5元，母雞每只值3元，小雞3只值1元，100元錢買100只雞，三種雞都要有。問：公雞、母雞、小雞各可買多少只？問題分析：（1）設(shè)可買公雞x只，母雞y只，小雞z只，根據(jù)數(shù)學(xué)知識(shí)可有下面的方程式：圖5-8 百雞問題求解流程圖否是X=20定義循環(huán)控制變量Z=Z+1是Y=33是Z=100否是輸出x，y，zN=100且M=1

30、00N=x+y+zM=5x+3y+z/3否否Y=Y+1X=X+1End（2）這是一個(gè)由3個(gè)未知數(shù)、兩個(gè)方程組成的不定方程組，存在多組可能的解，可用窮舉法求解。通過窮舉x、y、z的各種可能取值情況，將其帶入方程組進(jìn)行驗(yàn)證，若滿足方程組，則x、y、z的取值為方程組的一組解。（3）考慮到100元最多買20只公雞，33只母雞，所以x取值范圍應(yīng)該在120之間，y取值范圍是133，而z的范圍是1100?；舅惴ǎ海?）列舉出x、y、z的取值情況；（2）將x、y、z帶入方程組進(jìn)行驗(yàn)證；（3）若方程組成立，則輸出一組解；（4）若方程組不成立，則繼續(xù)判斷下一個(gè)情況；（5）通過循環(huán)操作實(shí)現(xiàn)窮舉所有x、y、z的取值

31、情況。流程圖如圖5-8所示，代碼如下。Private Sub Command1_Click() Dim x%, y%, z% For x = 1 To 20 For y = 1 To 33 For z = 1 To 100 N= x + y + z 總頭數(shù)M=5*x+3*y+z/3 總錢數(shù)If N=100 And M=100 Then Print x, y, z End If Next z Next y Next xEnd Sub該程序中的判斷語句共運(yùn)行了20*33*100次，實(shí)際上，在確定公雞和母雞的只數(shù)后，小雞只數(shù)可以直接推算出來，即z100-x-y，不需要再用循環(huán)列舉z的值。因此，程序可

32、以優(yōu)化為：Private Sub Command1_Click() Dim x%, y%, z%For x = 1 To 20 確定買公雞只數(shù)For y = 1 To 33 確定買母雞只數(shù)z=100-x-y 計(jì)算小雞只數(shù)s=5*x+3*y+z/3If s=100 Then 符合條件的解，即買公雞、買母雞和小雞只數(shù)Print x,y,zEnd IfNext yNext xEnd Sub這樣循環(huán)次數(shù)減少到20*33次，若在確定公雞只數(shù)x的基礎(chǔ)上，再確定母雞的只數(shù)y，讀者可以在此基礎(chǔ)上考慮進(jìn)一步優(yōu)化程序。5.4 遞推和迭代法求解問題遞推（recurence）：從前面的結(jié)果計(jì)算推出后面的結(jié)果。解決遞推

33、問題必須具備兩個(gè)條件：（1）初始條件；（2）遞推關(guān)系（或遞推公式）。迭代（iterate）：不斷以計(jì)算的新值取代原值的過程。在進(jìn)行程序設(shè)計(jì)時(shí)，遞推的問題一般可以用迭代方法來處理，但若使用數(shù)組進(jìn)行遞推問題求解，則可以不用迭代法處理。遞推和迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值，新值（替代原值）又推出下一組新值等，進(jìn)而實(shí)現(xiàn)對(duì)復(fù)雜問題的求解。迭代法又分為精確迭代和近似迭代。如例5-9求斐波那契數(shù)列為精確迭代，“牛頓迭代法”屬于近似迭代法。

34、5.4.1數(shù)列求數(shù)列通常是給出數(shù)列初始幾項(xiàng)（或最后幾項(xiàng)）和遞推公式（或規(guī)律），求解出數(shù)列中其他項(xiàng)。例5-9 求斐波那契（Fibonaccii）數(shù)列。已知數(shù)列的前兩項(xiàng)均為1，從第三項(xiàng)開始，每一項(xiàng)為其前兩項(xiàng)之和，求該數(shù)列的前20項(xiàng)。問題分析：設(shè)a、b分別為數(shù)列中的前一項(xiàng)和前二項(xiàng)，c為后一項(xiàng)，則有c=a+b，第3到20個(gè)數(shù)用循環(huán)中的語句求出。已知第1項(xiàng)和第2項(xiàng)，在求出第3項(xiàng)后，使a和b分別代表數(shù)列中的第2、3項(xiàng)，以便求出第4項(xiàng)，如以下過程示意，以后依次類推，求出其他項(xiàng)。11235第一次計(jì)算abc第二次計(jì)算abc第三次計(jì)算abc圖5-9 求斐波那契數(shù)列流程圖否是i0.000001假設(shè)近似根x0=0迭代

35、次數(shù)N=0x1 = x0f =x13-2*x12+4*x1+1f1 = 3*x12-4*x1+4x0 = x1-f / f1Print n, x0n = n+1輸出c輸出數(shù)組元素的值Print x0根據(jù)以上算法，流程圖如圖5-11所示，程序如下：Private Sub Command1_Click() Dim x1!, x0!, n% x0 = 0 n = 0 Do While n = 0 Or Abs(x0 - x1) 0.000001 x1 = x0 f = x1 3 - 2 * x1 2 + 4 * x1 + 1 f1 = 3 * x1 2 - 4 * x1 + 4 x0 = x1 -

36、f / f1 Print n, x0 n = n + 1 Loop Print String(20, *) Print x0 Print String(20, *)End Sub在此程序中，每次循環(huán)x1和x0代表不同的數(shù)，x1存儲(chǔ)原x值，用來計(jì)算新的x值，x0存儲(chǔ)的是計(jì)算出的新值?？偨Y(jié)：利用迭代算法解決問題，需做好以下三個(gè)方面的工作：（1）確定迭代變量在可以用迭代算法解決的問題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。（2）建立迭代關(guān)系式所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢皂樛苹?/p>

37、倒推的方法來完成。（3）對(duì)迭代過程進(jìn)行控制在何時(shí)結(jié)束迭代過程，這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件。5.5 排序問題排序是指將一組數(shù)按遞增或遞減的次序排列。在日常生活中，排序問題和應(yīng)用無處不在，如學(xué)生名單按學(xué)號(hào)，成績按高低排序或排名，某個(gè)會(huì)議代表名單的排序等，這些都是對(duì)數(shù)據(jù)排序的具體應(yīng)用。排序的基本思想：對(duì)一組原始數(shù)據(jù)，按照按遞增或

38、遞減的方式，對(duì)數(shù)據(jù)進(jìn)行比較，調(diào)整其所在整個(gè)數(shù)據(jù)集合中位置（次序），通過將多次比較和調(diào)整，使所有的數(shù)據(jù)在整個(gè)集合中保持合適的位置，數(shù)據(jù)所在的位置表明數(shù)據(jù)的排列次序。實(shí)現(xiàn)基本方法：（1）首先，將數(shù)據(jù)存放在一維數(shù)組中，每個(gè)數(shù)據(jù)對(duì)應(yīng)一個(gè)數(shù)組元素，數(shù)組元素的下標(biāo)代表數(shù)據(jù)在一組數(shù)中的排列位置；（2）將數(shù)組元素值進(jìn)行比較，交換數(shù)組元素值，通過多次比較操作，實(shí)現(xiàn)數(shù)組元素值按照遞增或遞減方式按次序存放在數(shù)組元素中，達(dá)到數(shù)據(jù)在數(shù)組中有序排列；（3）按次序輸出數(shù)據(jù)元素的值，得到排序結(jié)果。常用排序的方法有比較交換法、選擇法、冒泡法、插入法等。這里介紹比較交換法、選擇法。例5-11將一組數(shù)據(jù)15、8、4、13、6、10

39、、17、1按照由小到大的順序遞增排列。方法1：比較交換法排序。比較交換排序法算法：（1）首先，將數(shù)組的第1個(gè)元素a(1)與其后的每一個(gè)元素進(jìn)行比較，若a(1)大于其后元素值，則將a(1)與之交換值，通過此輪的多次比較，將最小數(shù)交換到a(1)中；（2）再次，將a(2)與其后的每一個(gè)元素比較，若a(2)大于其后元素值，則將a(2)與之交換，通過此輪比較，將此數(shù)交換到a(2)中；（3）依次類推到a(n-1) ，完成排序，共計(jì)需要n-1輪比較；（4）按次序輸出數(shù)組元素值。比較交換的過程如下：（1）先將第1個(gè)數(shù)與第2個(gè)數(shù)比較，若第1個(gè)數(shù)大于第2個(gè)數(shù)，則互換，再將第1個(gè)數(shù)和第3個(gè)數(shù)比較，若第1個(gè)數(shù)大于第3

40、個(gè)數(shù)，互換，依次將第1個(gè)數(shù)與第4到第n個(gè)數(shù)依次比較并互換。這樣就將n個(gè)數(shù)中的最小數(shù)通過比較互換安排到數(shù)組中的第一個(gè)位置上。（2）按步驟（1）對(duì)其余n-1個(gè)數(shù)進(jìn)行比較互換，將最小數(shù)換到第2個(gè)位置。重復(fù)步驟（1）共n-1次，最后數(shù)組中的元素就是按遞增順序排列的。若以上數(shù)字存放在數(shù)組a中，a15841361017112345678依照以上步驟，相互比較互換數(shù)字的數(shù)組元素的下標(biāo)關(guān)系如下：第一輪第二輪第三輪第七輪a(1)a(2)a(2)a(3)a(3)a(4)a(7)a(8)a(3)a(4)a(5)a(4)a(5)a(6)a(5)a(6)a(7)a(6)a(7)a(8)a(7)a(8)a(8)比較過程中

41、數(shù)組下標(biāo)的變化規(guī)律：（1）第一輪將8個(gè)數(shù)中的最小數(shù)安排在下標(biāo)是1的數(shù)組元素中；（2）第二輪將剩下的7個(gè)數(shù)中的最小數(shù)安排在下標(biāo)為2的數(shù)組元素中；圖5-12 比較排序法流程圖否是i=n-1定義數(shù)組循環(huán)控制變量i=1數(shù)組賦值j=j+1輸出排序前的數(shù)組是ja(j)a(i)與a(j)交換值i=i+1輸出排序后的數(shù)組否否（3）下標(biāo)的變化為1,2,3，,7；（4）將8個(gè)數(shù)據(jù)排好序，需進(jìn)行7輪比較（對(duì)n個(gè)數(shù)排序，則進(jìn)行n-1輪）；用循環(huán)for i=1 to n-1控制比較的輪數(shù)，循環(huán)變量i用于表示比較的元素a(i)。對(duì)每一輪比較過程中,a(i)需要和其后的元素比較，則其后元素下標(biāo)從i+1到8（對(duì)n個(gè)數(shù)，則從i

42、+1到n），用循環(huán)for j=i+1 to 8可控制一輪的比較過程，循環(huán)變量j表示與a(i)比較元素的下標(biāo)；兩個(gè)循環(huán)嵌套，可實(shí)現(xiàn)以上過程。流程圖如圖5-12所示，代碼如下：Option Base 1Private Sub Command1_Click() Dim a(), i%, n%, j% a = Array(15, 8, 4, 13, 6, 10, 17, 1) n = UBound(a) Print 排序前：; For i = 1 To n Print a(i); Next i Print For i = 1 To n - 1 For j = i + 1 To n If a(i) a(j) Then