算法與程序設(shè)計（VB）

【教學目標】

1.???????? 掌握算法的基本概念及面向?qū)ο缶幊趟枷?/p>

2.???????? 熟練掌握并運用VB基礎(chǔ)編程知識和基本算法知識

*請下載課程需要的軟件，對照知識點和練習題進行上機操作練習。

【知識歸納】

1.???????? 算法基本概念

(1)?????? 特征:有窮性、確定性、可行性、有輸出

(2)?????? 形式:自然語言、流程圖、計算機語言

(3)?????? 結(jié)構(gòu):順序、分支(選擇)、循環(huán)

2.???????? 常用算法：枚舉、解析、排序(冒泡排序、選擇排序)、查找(順序查找、對分查找)

3.???????? 面向?qū)ο缶幊?/p>

(1)?????? 對象：擁有狀態(tài)和方法，是對客觀事物的抽象

(2)?????? 類：對相同性質(zhì)的對象的抽象，一個對象是類的一個示例

(3)?????? 事件：發(fā)生在一個對象上的事情，通常指用戶在對象上激發(fā)的動作

*VB工具箱中每種控件都是一個類。對象是窗體和控件生成的工具。每個對象都有自己的屬性、方法，并且可以響應(yīng)外部事件。

4.???????? VB可視化編程(窗體文件名后綴是．frm)：

(1)?????? 常用控件：Label(標簽)、TextBox(文本框)、CommandButton、(按鈕控件)、Image(圖像框)、ListBox(列表框)、Timer(時鐘)

(2)?????? 常用屬性：Name(名稱)、Font(字體)、Text(文本)、Caption(標題)、BackColor(背景色)、Width(寬度)、Height(高度)、Left(左邊距)、Top(頂邊距)、Visible(可視)

(3)?????? 改變控件屬性的方法：對象名.屬性名

5.???????? VB程序設(shè)計(工程文件名后綴是．vbp)：

(1)?????? 常用數(shù)據(jù)類型：Integer(整型)、Long(長整型)、Single(實數(shù))、Double(實數(shù))、String(字符串，帶"")、Boolean(邏輯型)、Date(日期型，帶# #)

(2)?????? 常量：Const 常量名=數(shù)值

(3)?????? 變量：Dim 變量名 As 數(shù)據(jù)類型

(4)?????? 變量命名：①字母、數(shù)字、下劃線組成②只能字母開頭③不能使用關(guān)鍵字、保留字

(5)?????? 基本運算

(6)?????? 語法規(guī)則：

注釋語句：以單引號(')開頭的一串文字，對附近的程序段進行簡要的說明

賦值語句：變量名=表達式? 或???? 對象名.屬性名=表達式

選擇語句：行If、塊If

循環(huán)語句：For循環(huán)、While循環(huán)、Do While循環(huán)

(7)?????? 函數(shù)

①???? 常用函數(shù)：絕對值A(chǔ)bs(x)、取整(取不大于x的最大整數(shù)) Int(x)、

截取x的整數(shù)部分Fix(x)、算術(shù)平方根Sqr(x)、字符轉(zhuǎn)ASCII碼Asc(x)、

ASCII碼轉(zhuǎn)字符Chr(x)、取值Val(x)、轉(zhuǎn)字符串Str(x)、字符串長度Len(x)、

截取字符串Mid(x,n,k)、求隨機數(shù)Rnd()

②???? 自定義函數(shù)：

Function函數(shù)名(參數(shù)表) As　類型名

　語句塊

End Function

?

【知識梳理】

1.???????? 算法：對解題方法的精確而完整的描述，即解決問題的方法和步驟。

(1)?????? 特征:

①?? 有窮性：一個算法必須保證它的執(zhí)行步驟是有限的，即它是能終止的。一般來說，“有窮性” 也指在有限的或者合理的時間范圍內(nèi)完成全部操作。

②?? 確定性：算法中的每個步驟必須有確切的含義，不能有兩義性。

③?? 可行性：算法中的每一個步驟都要是足夠簡單、能實際操作的，而且能在有限的時間內(nèi)完成。

④?? 有0個或多個輸入。算法常需要對數(shù)據(jù)進行處理，因此算法常常需要數(shù)據(jù)輸入。如果初始數(shù)據(jù)已經(jīng)存在，則不再需要從外部輸入數(shù)據(jù)。

⑤?? 有一個或多個輸出：算法的目的是用來解決問題的，它必須向人們提供最終的結(jié)果。

(2)?????? 表示方法:

①???? 自然語言：用自然語言描述算法通俗易懂，但其缺點是敘述比較繁瑣冗長，容易出現(xiàn)“歧義性”。

②???? 流程圖：一種直觀易用，圖形描述算法的方法，也是目前使用最廣泛的一種方法。

③???? 計算機語言：計算機語言表示算法必須嚴格遵守所使用的程序設(shè)計語言語法規(guī)則。

(3)?????? 結(jié)構(gòu):

①???? 順序結(jié)構(gòu)：在算法流程中，執(zhí)行完一個處理步驟Step1后，順序執(zhí)行緊跟著的下一個步驟Step2， 一直這樣下去直至完成任務(wù)。

順序結(jié)構(gòu)流程圖

②???? 選擇結(jié)構(gòu)也叫分支結(jié)構(gòu)，就是判斷條件是否成立，并選擇某一條路徑中的指令執(zhí)行。

選擇結(jié)構(gòu)流程圖

?

③???? 循環(huán)結(jié)構(gòu)就是首先判斷條件是否成立，如果不成立則跳出循環(huán)體，如果條件成立則執(zhí)行循環(huán)體內(nèi)的指令，然后再次判斷條件是否成立，如果條件成立則再次執(zhí)行循環(huán)體內(nèi)的指令，直至條件不成立跳出循環(huán)體為止。

??

當型循環(huán)(While循環(huán))結(jié)構(gòu)流程圖

直到型循環(huán)(Do While循環(huán))結(jié)構(gòu)流程圖

??

【典型例題】

1.某算法部分流程圖如圖所示。執(zhí)行這部分流程,依次輸入12、-5、29、18、7,則輸出值是

A．12

B．-5

C．29

D．7

2.某算法的流程圖如下圖所示，它主要表示的是算法中的（? ）。

A、選擇結(jié)構(gòu)

B、順序結(jié)構(gòu)

C、循環(huán)結(jié)構(gòu)

D、流程結(jié)構(gòu)

?
?

?

2.???????? 面向?qū)ο缶幊?Object Oriented Programming,簡稱OOP)

(1)?????? 對象：擁有狀態(tài)和方法，是對客觀事物的抽象

(2)?????? 類：對相同性質(zhì)的對象的抽象，一個對象是類的一個示例

(3)?????? 事件：發(fā)生在一個對象上的事情，通常指用戶在對象上激發(fā)的動作

*VB工具箱中每種控件都是一個類。對象是窗體和控件生成的工具。每個對象都有自己的屬性、方法，并且可以響應(yīng)外部事件。

?

3.???????? VB可視化編程(窗體文件名后綴是．frm)：

(1)?????? 常用控件

(2)?????? 常用屬性

*改變控件屬性的方法：對象名.屬性名

?

4.???????? VB程序設(shè)計(工程文件名后綴是．vbp)：

(1)?????? 常用數(shù)據(jù)類型：Integer(整型)、Long(長整型)、Single(實數(shù))、Double(實數(shù))、String(字符串，帶"")、Boolean(邏輯型)、Date(日期型，帶# #)

(2)?????? 常量：Const 常量名=數(shù)值

(3)?????? 變量：Dim 變量名 As 數(shù)據(jù)類型

(4)?????? 變量命名：①字母、數(shù)字、下劃線組成②只能字母開頭③不能使用關(guān)鍵字、保留字

(5)?????? 基本運算

(6)?????? 語法規(guī)則：

注釋語句：以單引號(')開頭的一串文字，對附近的程序段進行簡要的說明

賦值語句：變量名=表達式??????? 或???? 對象名.屬性名=表達式

選擇語句：

行If：

? If 條件表達式 Then 語句1? Else 語句2 ?或 If 條件表達式 Then 語句

塊If：

If 條件表達式1 ?Then

????????語句1

ElseIf 條件表達式2? Then

????????語句2

????????……

ElseIf 條件表達式n? Then

????????語句n

Else

????????語句0

End If

循環(huán)語句：

For循環(huán)：

For 循環(huán)變量 = 初值 To 終值 Step 步長

????????語句塊

Next 循環(huán)變量

While循環(huán)：

While 條件表達式 ?

????????語句塊

Wend

Do While循環(huán)：

Do While 條件表達式 ?

????????語句塊

Loop

(7)?????? 函數(shù)

Function ? 函數(shù)名(參數(shù)表) ?As　類型名

????????語句塊

End? Function

【典型例題】

1.有如下VB程序段：

a(1) = 1: a(2) = 1

b(1) = 1: b(2) = 2

For i = 3 To 5

??? a(i) = a(i - 1) + a(i - 2)

??? b(i) = b(i - 1) + a(i)

Next i

執(zhí)行該程序段后，數(shù)組元素b(5)的值為

??

A．12

B．8

C．5

D．5

??

?

?2.有如下程序段：

?????????????????? For i=1 To 2

??????????????????????????? For j=1 To 7-i

???????????????????????????????????? If a(j)>a(j+1) Then

?????????????????????????????????????????????? t=a(j):a(j)=a(j+1):a(j+1)=t

???????????????????????????????????? End If

??????????????????????????? Next j

?????????????????? Next i

???????? 數(shù)組元素a(1)到a(7)的值依次為"44,24,33,67,77,58,12"，經(jīng)過該程序段“加工”后，數(shù)組元素a(1)到a(5)的值依次為

??

A．12,24,44,33,58

B．12,24,33,67,77

C．24,44,44,58,12

D．44,24,33,58,12

??

?

5.???????? 常用算法

(1)?????? 枚舉算法：例舉出問題可能的解，并在例舉過程中檢驗是不是問題真正解的算法。

(2)?????? 解析算法：利用解析方法找到表示問題的前提條件和結(jié)果之間關(guān)系的數(shù)學表達式，并通過表達式計算實現(xiàn)問題求解的算法。

(3)?????? 排序算法

①???? 冒泡排序：重復(fù)的順序訪問數(shù)組，依次比較相鄰兩個數(shù)據(jù)，如果他們順序錯誤就把他們交換過來，直到?jīng)]有數(shù)據(jù)需要交換為止。

升序排序n個數(shù)據(jù)的數(shù)組d：

For i=1 To n-1 'n個數(shù)排序共需進行n－1趟

???????? For j=n To i+1 Step-1 '每一趟從后往前，相鄰兩數(shù)兩兩比較

?????????????????? If d(j)＜d(j-1) Then '若滿足條件則進行互換

??????????????????????????? Temp=d(j):d(j)=d(j-1):d(j-1)=temp

?????????????????? End If

???????? Next j

Next i

*若要降序排列，只需將語句"If d(j)＜d(j－1) Then"改為"If d(j)＞d(j－1) Then"即可。

?

②???? 選擇排序：從數(shù)組中找到最小(或最大)的一個數(shù)，使他與第一個數(shù)交換位置，然后從剩下的數(shù)中找到最小(或最大)的一個數(shù)與數(shù)組中的第二個數(shù)交換位置，以此類推，直到所有數(shù)排成一個有序數(shù)組為止。示例代碼如下：

升序排序n個數(shù)據(jù)的數(shù)組d：

For i=1 To n-1 'n個排序共進行n－1趟排序

???????? k=i '第i趟排序時，首先用k記錄i

???????? For j=i+1 To n 'k位置上的數(shù)依次與j位置上的數(shù)進行比較

?????????????????? If d(k)>d(j) Then k=j '若找到比k位置上更小的數(shù)，則更新k的值

???????? Next j

???????? If k<>i Then '若i位置上的數(shù)不是最小數(shù)，則和k位置上的數(shù)進行互換

?????????????????? temp=d(i):d(i)=d(k):d(k)=temp

???????? End If

Next i

*若要降序排列，只需將語句" If d(k)>d(j) Then k=j "改為" If d(k)>d(j) Then k=j "即可。

?

(4)?????? 查找算法

①???? 順序查找：從第一個數(shù)開始，順序逐個與給定值進行比較，若某個數(shù)和給定值相等，則查找成功，否則查找失敗。

在數(shù)組d中查找值key：

For循環(huán)：

For i=1 to n

???????? If d(i)=key Then '找到，做相應(yīng)處理

Next i '若i>n表示未找到

?Do - While循環(huán)：

　i=1

　Do While i<=n

????????????? If d(i)=key Then '找到，做相應(yīng)處理

????????????? i=i+1

　Loop'若i>n表示未找到

②???? 對分查找：在有序數(shù)據(jù)序列中，首先把要查找的數(shù)據(jù)與數(shù)組中間的元素進行比較，如果相等，則查找成功并退出查找；否則，根據(jù)數(shù)組元素的有序性，確定在數(shù)組前半部分還是后半部分查找，確定了查找范圍后重復(fù)進行以上比較，直到找到或未找到為止。

*注意：

???????????????????????? i.????????????? 數(shù)據(jù)序列必須有序。

?????????????????????? ii.????????????? "未找到"是指在指定范圍內(nèi)起點大于終點時仍未找到該數(shù)據(jù)。

【典型例題】

???????? 有一組正整數(shù)，要求供對其中的素數(shù)進行升序排序。排序后素數(shù)在前，非素數(shù)在后。排序示例如下。

Const n = 8

Dim a(1 To n) As Integer

Private Sub Command1_Click()

???????? Dim i As Integer, j As Integer, k As Integer, t As Integer

???????? Dim flag As Boolean

???????? '讀取一組正整數(shù)，存儲在數(shù)組a中，代碼略

???????? For i = 1 To n - 1

???????? ???????? k = 1

???????? ???????? If IsPrime(a(k)) Then flag = True Else flag = False

???????? ?????????????????? For j = i + 1 To n

?????????????????? ?????????????????? If IsPime(a(j)) Then

??????????????????????????? ?????????????????? If a(j) < a(k) Then

?????????????????? ???????? ???????? ???????? k = j

?????????????????? ???????? ???????? ???????? flag = True

?????????????????? ?????????????????? End If

??????????????????????????? End If

?????????????????? Next j

?????????????????? If k <> i Then

??????????????????????????? t = a(k): a(k) = a(i): a(i) = t

?????????????????? End If

?????????????????? If Not flag Then Exit For 'Exit For表示退出循環(huán)

???????? Next i

???????? '依次輸出排序后的數(shù)據(jù)。代碼略

End Sub

Function IsPrime(m As Integer) As Boolean

???????? '本函數(shù)判斷m是否是素數(shù)：是素數(shù)返回值為True，不是素數(shù)返回值為False

???????? '代碼略

End Function

?

?

【課堂練習】

?

1. ?? Dim i As Integer, j As Integer, k As String, n As Integer

???????? n=3

???????? List1.Clear

???????? For i=1 To n

???????? k=""

???????? For j=1 To i

?????????????????? k=k＋"*"

?????????????????? Next j

?????????????????? List1.AddItem k

???????? Next i

該程序運行中，在列表框List1中顯示的是(　　)

??

2.某數(shù)組的6個元素依次為“27，32，57，78，80，90”。若對該函數(shù)組進行順序查找，其平均查找次數(shù)為(1+2+3+4+5+6)/6=7/2；若對該數(shù)組進行對分查找，其平均查找次數(shù)為（　?。?/p>

??

A.7/2

B.7/3

C.5/2

D.2

?

3.用VB編寫一個字符串分行程序，功能如下：單擊“分行”按鈕Command1，將文本框Text1中的英文文本在列表框List1中分行顯示(分行時單詞不得跨行，每行字符盡可能多但不超過40個)，并在標簽Label1中輸出總行數(shù)，運行效果如圖所示。分行算法如下：

(1)將文本框中的字符串保存到變量s中；

(2)當s中字符個數(shù)超過40時，循環(huán)執(zhí)行下列①②③步，否則跳轉(zhuǎn)到(3)：

①如果第41個字符不是英文字母，則分行位置p＝40；否則，向左逐個查找，直至找到第一個非英文字母，將其位置作為分行位置p；

②截取s的前p個字符，作為新增行顯示在列表框List1中，同時總行數(shù)加1；

③將s中未分行部分重新賦值給變量s。

(3)將s作為新增行顯示在列表框List1中，同時總行數(shù)加1。

實現(xiàn)上述功能的VB程序如下，請在畫線處填入合適代碼。

Private Sub Command1_Click( )

???????? Dim s As String,c As String

???????? Dim r As Integer,total As Integer,p As Integer

???????? total=0

???????? s=__(1)__

???????? Do While Len(s)>40

?????????????????? r=41

?????????????????? c=Mid(s,r,1)

?????????????????? If Not((c>="a" And c<="z")Or(c>="A" And c<="Z")) Then

　?????????????????????? p=40

?????????????????? Else

　?????????????????????? '從第41個字符開始向左找到第1個非英文字母，并將其位置值賦給p

　?????????????????????? Do While(c>="a" And c<="z")Or(c>="A"And c<="Z")

???????????????????????????????????? r=__(2)__

???????????????????????????????????? c=Mid(s,r,1)

　?????????????????????? Loop

　?????????????????????? p=r

?????????????????? End If

?????????????????? List1.AddItem Mid(s,1,p)

?????????????????? total=total+1

?????????????????? s=__(3)__

　???? Loop

　???? List1.AddItem s

　???? total=total + 1

　???? Label1.Caption＝"共"+Str(total)+"行"

End Sub

?

4. 某種編碼以4位二進制碼為一組，每組前兩位表示方向，后兩位表示距離。編寫一個程序,將編碼翻譯成方向和距離，距離值為每組編碼后兩位二進制碼轉(zhuǎn)換為十進制數(shù)的值。具體功能如下：在文本框Text1中輸入連續(xù)多組編碼，單擊“翻譯”按鈕Command1，結(jié)果顯示在列表框List1中。程序運行界面如圖所示。

(1)要使程序運行時，文本框Text1的Width屬性值為2018，可在Form_Load事件過程中添加語句??????? （單選，填字母：A. Width=2018 / B.Text1. Width = 2018 / C. Width. Text1=2018）。

(2)實現(xiàn)上述功能的VB程序如下，請在劃線處填入合適的代碼。

Private Sub Command1_Click()

Dim s As String, c As String, d As String

Dim n As Integer, bl As Integer, b2 As Integer, v As Integer, i As Integer

s = Text1.Text: n = Len(s): i = 1

Do While i <= n

??? c = Mid(s, i, 2)

??? If c = "00" Then

?????????????????? d = "東"

??? ElseIf c = "01" Then

?????????????????? d = "南"

??? ElseIf c = "10" Then

?????????????????? d = "西"

??? Else

?????????????????? d = "北"

??? End If

??? b1 = Val(Mid(s, i + 2, 1))

??? b2 = Val(Mid(s, i + 3, 1))

??? v=____①____?????????????

??? List1.AddItem d + " " + Str(v)

____②____

Loop

End Sub

（3）若文本框Text1中輸入的內(nèi)容為“1111”，單擊“翻譯”按鈕，列表框List1中顯示的內(nèi)容是________。

?