Giáo trình Bài tập lập trình hướng sự kiện

guyªn tè !” If KetQua = False Then MsgBox n & “ kh«ng ph¶i lµ sè nguyªn tè !” End Sub c. Ghi chú: • Để thoát vô điều kiện khỏi vòng lặp Do While…, Do…Loop While hay Do … Loop Until thì cần gọi lệnh Exit Do • Hàm Sqr(n) trong VB dùng để tính n (không phải là tính bình phương như trong một số ngôn ngữ lập trình khác – như Pascal). • Nếu công việc gì chỉ làm một lần (ví dụ thông báo kết quả như trên) thì “KHÔNG BAO GIỜ” được đặt trong vòng lặp mà phải đặt ở ngoài vòng lặp. Vì đặc điểm của vòng lặp là “lặp đi lặp lại” nhiều lần một công việc ! Bài tập 12 a. Hướng dẫn: Giai thừa của số N được tính theo công thức N!=1.2.3…N-1.N. Để tính toán ta thực hiện nhân dồn các số i ( i = 1 ÷ N) vào kết quả. b. Chương trình mẫu: Private Sub Form_Load() Dim n As Integer, i As Integer, KetQua As Long BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 12 '/// NhËp sè n, ®¶m b¶o 0<n<10 Do n = InputBox("CÇn tÝnh giai thõa cña mÊy : ") Loop Until (0 < n And n < 10) '/// Sö dông vßng lÆp For KetQua = 1 For i = 1 To n KetQua = KetQua * i Next Debug.Print "KÕt qu¶ cña " & n & "! = " & KetQua '/// Sö dông vßng lÆp Do While KetQua = 1 i = 1 Do While i <= n KetQua = KetQua * i i = i + 1 Loop Debug.Print "KÕt qu¶ cña " & n & "! = " & KetQua '/// Sö dông vßng lÆp Do Until KetQua = 1 i = 1 Do Until i > n KetQua = KetQua * i i = i + 1 Loop Debug.Print "KÕt qu¶ cña " & n & "! = " & KetQua '/// Sö dông vßng lÆp Do ... Loop While i = 1 KetQua = 1 Do KetQua = KetQua * i i = i + 1 Loop While i <= n Debug.Print "KÕt qu¶ cña " & n & "! = " & KetQua '/// Sö dông vßng lÆp Do ... Loop Until i = 1 KetQua = 1 Do KetQua = KetQua * i i = i + 1 Loop Until i > n Debug.Print "KÕt qu¶ cña " & n & "! = " & KetQua End Sub c. Ghi chú: • Có thể tính N! bằng phương pháp đệ qui : GiaiThua = GiaiThua (n-1) * N. • Người ta đã chứng minh được rằng tất các cấu trúc lặp đều có thể viết tương đương theo các cấu trúc khác. • Trong VB có rất nhiều cấu trúc lặp, tuy nhiên chỉ cần thuộc 3 cấu trúc sau là đủ: o For … BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 13 o Do ……… Loop Until o Do While …….. Loop • Cấu trúc Do While … Loop và Do Until …. Loop cùng có điểm giống nhau là kiểm tra điều kiện trước khi lặp (giống như cấu trúc While …do trong Pascal hay While trong C/C++) nhưng cấu trúc Do While … Loop chỉ lặp khi điều kiện vẫn đúng, còn cấu trúc Do Until …. Loop chỉ lặp khi điều kiện vẫn sai (Hay thoát nếu là đúng). • Cấu trúc Do … Loop While và cấu trúc Do … Loop Until cùng giống nhau là thực hiện lặp sau đó mới kiểm tra điều kiện (Giống cấu trúc Repeat … Until trong pascal hay do … While trong C/C++), nhưng cấu trúc Do … Loop While chỉ lặp nếu điều kiện vẫn còn đúng, trong khi đó cấu trúc Do … Loop Until chỉ lặp nếu biểu thức điều kiện vẫn còn sai (Hay nói cách khác là kết thúc lặp nếu điều kiện lặp là đúng) • Khi thực hành, không nhất thiết phải nhớ cả 4 kiểu lặp đã nêu ở trên mà bạn nên vận dụng thành thạo 3 cấu trúc lặp được khuyến cáo dùng là For, Do While và Do … Loop Until, vì 3 cấu trúc này tương tự như các cấu trúc lặp trong một số ngôn ngữ lập trình phổ biến khác (For,While…do,Repeat ..Until). Bài tập 13 a. Hướng dẫn: Ta có thổng S = S1 + S2 + S3, với S1, S2, S3 tương ứng với 3 tổng trên. Sử dụng vòng lặp để tính tổng của mỗi Si, sau đó cộng lại để được kết quả. b. Chương trình mẫu: Private Sub form_load() Dim i As Integer Dim Tong As Long Dim S1 As Long, S2 As Long, S3 As Long Tong = 0 ' §Çu tiªn do ch−a tÝnh nªn Tong b»ng 0 S1 = 0 S2 = 0 S3 = 0 '/// TÝnh tæng S1 For i = 1 To 8 S1 = S1 + i ^ 2 Next '/// TÝnh tæng S2 For i = 100 To 200 S2 = S2 + i ^ 2 Next '/// TÝnh tæng S3 For i = 300 To 310 S3 = S3 + i ^ 2 Next S = S1 + S2 + S3 MsgBox "Tæng lµ : " & Tong, vbInformation, "Th«ng b¸o ..." End Sub BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 14 Bài tập 14: a. Hướng dẫn: Công thức tính giai thừa của số N là: N! = 1.2.3…N-1.N, như vậy ở đây ta cần nhân liên tiếp các số i (i chạy từ 1 đến n) vào kết quả. Trong đó, giá trị khởi tạo cho kết quả là 1. Bài này có thể giải theo cách đệ qui hoặc không đệ qui. b. Chương trình mẫu Cách 1: Dùng vòng lặp (Không dùng đệ qui) Private Sub Form_Load() Dim i As Integer, n As Integer Dim KetQua As Long '/// NhËp sè n (0<n<20) Do n = InputBox("NhËp sè N : ", "TÝnh giai thõa") Loop Until (0 < n And n < 20) KetQua = 1 For i = 1 To n KetQua = KetQua * i Next MsgBox n & " ! bằng " & KetQua End Sub Cách 2: Dùng đệ qui '/// Hµm ®Ö qui tÝnh N ! Function GiaiThua(ByVal N As Integer) As Long If N = 1 Then GiaiThua = 1 Else GiaiThua = GiaiThua(N - 1) * N End If End Function Private Sub Form_Load() Dim i As Integer, N As Integer Dim KetQua As Long '/// NhËp sè n (0<n<20) Do N = InputBox("NhËp sè N : ", "TÝnh giai thõa") Loop Until (0 < N And N < 20) MsgBox N & " ! bằng " & GiaiThua(N) End Sub BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 15 Bài tập 15: a. Hướng dẫn: Với bài toán dạng tính tổng của một chuỗi số khi biết số hạng tổng quát Si, nói chung là đơn giản. Có thể thực hiện theo giải thuậ như sau: S = 0 For i = i0 TO in S = S + Si Next Với mỗi dãy khác nhau thì giá trị i0, N, Si có thể khác nhau và cần phải xác định. - Giá trị i0 và N thường xác định bởi giải phương trình Si = S0 và Si = Sn - Số hạng tổng quát Si thường có thể nhìn thấy ngay trong đề bài. Trong bài này: - )1(* ++= iniSi - Xác định i0: Cho S0 = Si ⇔ 2*1 +n = )1(* ++ ini ⇒ i0=1 - Xác định in: Cho Sn = Si ⇔ )1(* ++ nnn = )1(* ++ ini ⇒ in=n b. Chương trình mẫu: Private Sub Form_Load() Dim S As Single, i As Integer, N As Integer N = InputBox("NhËp sè N : ") S = 0 For i = 1 To N S = S + i * Sqr(N + (i + 1)) Next MsgBox "Tæng cña d·y ®· cho lµ : " & S End Sub Bài tập 16 a. Hướng dẫn: Với các bài toán được định nghĩa theo kiểu đệ qui thì cách giải phù hợp và dễ nhất là theo giải thuật qui. Tuy nhiên, tốc độ bị chậm đáng kể khi số N lớn, ngoài ra còn có thể bị tràn Stack. b. Chương trình mẫu: '/// TÝnh d·y Fibonasi dïng §Ö qui Function Fib_Dequi(ByVal N As Integer) As Long If N = 0 Or N = 1 Then Fib_Dequi = 1 If N > 1 Then Fib_Dequi = Fib_Dequi(N - 2) + Fib_Dequi(N - 1) End Function '/// TÝnh d·y Fibonasi KH¤NG dïng §Ö qui Function Fib_KhongDequi(ByVal N As Integer) As Long Dim i As Integer Dim F1 As Long, F2 As Long, KetQua As Long F1 = 1 F2 = 1 KetQua = 1 BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 16 i = 2 Do While i <= N KetQua = F1 + F2 F1 = F2 F2 = KetQua i = i + 1 Loop Fib_KhongDequi = KetQua End Function '--------------------------------------------------------------------------------------------------------------------------- '/// Ch−¬ng tr×nh chÝnh Private Sub Form_Load() MsgBox "Fib (30) = " & Fib_Deq ui(30) MsgBox "Fib (30) = " & Fib_KhongDequi(30) End Sub Chú ý: Riêng với bài toán này, người ta còn có thể giải bằng phương pháp qui hoạch động (Dynamic Programming) rất đơn giản như sau: Function Fib_DynamicPrgramming(ByVal N As Integer) As Long Dim i As Integer Dim F(1000) As Long '/// B¶ng chøa gi¸ trÞ ®· tÝnh to¸n ®−îc ë b−íc trung gian '/// §iÓm xuÊt ph¸t F(0) = 1 F(1) = 1 For i = 2 To N F(i) = F(i - 2) + F(i - 1) Next Fib_DynamicPrgramming = F(N) End Function Bài tập 17: a. Hướng dẫn: Để tìm ước số chung lớn nhất của 2 số nguyên a và b, người ta có thể dựa vào công thức Ơ-Le và cài đặt bằng vòng lặp hoặc đệ qui. Việc tìm ước số chung được ứng dụng vào tối giản phân số. b. Chương trình mẫu: '/// T×m USCLN kh«ng dïng ®Ö qui Function USCLN(a As Integer, b As Integer) As Integer Dim Du As Integer Du = a Mod b Do While Du 0 a = b b = Du Du = a Mod b Loop USCLN = b End Function BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 17 '/// T×m USCLN b»ng §Ö qui Function USCLN_Dequi(a As Integer, b As Integer) As Integer If a Mod b = 0 Then USCLN_Dequi = b Else USCLN_Dequi = USCLN_Dequi(b, a Mod b) End If End Function '----------------------------------------------------------------------------------------------------------------------------- '/// Ch−¬ng tr×nh chÝnh Private Sub Form_Load() MsgBox "−íc sè chung lín nhÊt cña 20 vµ 30 lµ : " & USCLN(20, 30) MsgBox "−íc sè chung lín nhÊt cña 20 vµ 30 lµ : " & USCLN_Dequi(20, 30) End Sub Bài tập 18: a. Hướng dẫn: Phân số dạng a/b được gọi là tối giản nếu Ước số chung lớn nhất của a và b là 1. Ví dụ: phân số 5/7 và 9/7 là tối giản; 4/6 và 6/4 là chưa tối giản. b. Chương trình mẫu: '/// T×m −íc sè chung lín nhÊt cña 2 sè a vµ b Function USCLN(a As Integer, b As Integer) As Integer If a Mod b = 0 Then USCLN = b Else USCLN = USCLN(b, a Mod b) End If End Function '----------------------------------------------------------------------------------------------------------------------------- '/// Ch−¬ng tr×nh chÝnh Private Sub Form_Load() Dim a As Integer, b As Integer, TuMoi As Integer, MauMoi As Integer a = InputBox("NhËp tö sè : ") b = InputBox("NhËp mÉu sè : ") If USCLN(a, b) = 1 Then MsgBox "Ph©n sè " & a & "/" & b & " ®· tèi gi¶n", vbInformation Else TuMoi = a / USCLN(a, b) ‘/// TÝnh l¹i tö sè míi MauMoi = b / USCLN(a, b) ‘/// TÝnh l¹i mÉu sè míi MsgBox "Ph©n sè sau khi tèi gi¶n lµ : " & TuMoi & "/" & MauMoi End If End Sub Bài tập 19: a. Hướng dẫn: Trước hết cần xây dựng hàm kiểm tra xem số N có phải là nguyên tố hay không ? Sau đó sử dụng kết quả này vào giải quyết yêu cầu bài toán. b. Chương trình mẫu: BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 18 '/// Hµm kiÓm tra xem sè N cã ph¶i lµ sè nguyªn tè hay kh«ng ? Function LaSoNguyenTo(ByVal n As Integer) As Boolean Dim i As Integer LaSoNguyenTo = True For i = 2 To Round(Sqr(n)) If n Mod i = 0 Then LaSoNguyenTo = False Exit Function End If Next End Function '----------------------------------------------------------------------------------------------------------------------------- '/// Ch−¬ng tr×nh chÝnh Private Sub Form_Load() Dim i As Integer, n As Integer, DaySo(100) As Integer n = InputBox("Sè phÇn tö cÇn nhËp : ", , 10) For i = 1 To n DaySo(i) = InputBox("NhËp sè thø " & i) Next For i = 1 To n If LaSoNguyenTo(DaySo(i)) Then Debug.Print DaySo(i) Next End Sub Bài tập 20 a. Hướng dẫn: Để đếm số ký tự a và A trong một xâu S, chúng ta cần duyệt và kiểm tra lần lượt từng ký tự nằm trong xâu S và so sánh với ký tự a và A. Để duyệt (lấy từng ký tự trong xâu S) chúng ta có thể sử dụng một trong 3 loại vòng lặp. Hàm Mid(S,i,1) cho ta ký tự tại vị trí thứ i trong xâu S. b. Chương trình mẫu (Sử dụng vòng lặp Do While): Form_load() Dim S As String Dim TongAa As Integer Dim i As Integer S = InputBox("B¹n h·y nhËp mét x©u : ") i = 1 'B¾t ®Çu tõ ký tù thø nhÊt TongAa = 0 'Khëi t¹o sè ký tù A hoa vµ a th−êng ban ®Çu b»ng 0. Do While i <= Len(S) If Mid(S, i, 1) = "A" Or Mid(S, i, 1) = "a" Then TongAa = TongAa + 1 End If i = i + 1 ‘/// Chuyển đến vị trí của ký tự tiếp theo Loop MsgBox "Tæng sè ký tù a vµ A trong x©u lµ " & TongAa & " ký tù" End Sub BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 19 C. Ghi chú: Trong vòng lặp For thì biến chạy sẽ được tự động tăng lên 1 đơn vị, còn trong vòng lặp Do While ... Loop và Do...Loop biến chạy không tự động tăng lên 1, do vậy ta phải tự thực hiện tăng biến chạy lên 1 đơn vị bằng câu lệnh i = i + 1 như bài tập ở trên. Bài tập 21: a. Hướng dẫn: Tổng S chính là tổng của các số hạng thứ i, với Si = ni xi + (Đây là số hạng tổng quát) và i chạy từ 0 đến N. Do vậy để tính tổng chúng ta cần sử dụng một trong 3 loại vòng lặp đã học. b. Chương trình mẫu: (Sử dụng vòng lặp For, bạn hãy thực hiện với vòng lặp do...While và do...Loop) Private Sub Form_Load() Dim i As Integer, N As Integer, x As Single Dim S As Single '///////// NhËp x vµ n //////////////////////// x = InputBox("NhËp vµo sè x : ") N = InputBox("NhËp vµo sè n : ") S = 0 '// Khëi t¹o tæng S = 0 For i = 0 To N S = S + x ^ i / (i + 1) ‘/// Nói chung là : S = S + Next MsgBox "Tæng S = " & S, vbInformation, "TÝnh tæng chuçi" End Sub Chú ý: Khi tính tổng của một dãy số bất kỳ, việc khó khăn nhất là phải xác định được số hạng tổng quát Si, sau đó là cận dưới và cận trên của vòng lặp. Còn tổng thì thường tính theo công thức : S = S + Si Bài tập 22 a. Hướng dẫn: Trước hết cần khai báo một mảng nguyên, sau đó hỏi người dùng xem muốn nhập bao nhiêu số và sử dụng vòng lặp để tiến hành nhập dữ liệu cho mảng. Để tìm số lớn nhất, thông thường ta giả định là phần tử đầu tiên. Sau đó dùng vòng lặp để duyệt qua các phần tử còn lại và so sánh, nếu số đang xét lớn hơn số giả định thì ta lại thay đổi giá trị của số giả định bằng phần tử đang xét. b. Chương trình mẫu: Private Sub Form_Load() Dim i As Integer, N As Integer Dim MAX As Integer Dim A(100) As Integer 'Khai b¸o m¶ng A cã 101 phÇn tö '///////// NhËp sè phÇn tö n N = InputBox("B¹n cÇn nhËp bao nhiªu sè: ") BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 20 For i = 1 To N A(i) = InputBox("NhËp vµo sè thø " & i) Next '/////// T×m sè lín nhÊt trong N sè võa nhËp /////////////////////// MAX = A(1) '///Gi¶ ®Þnh phÇn tö lín nhÊt lµ phÇn tö A(1) For i = 1 To N If A(i) > MAX Then MAX = A(i) Next MsgBox "PhÇn tö lín nhÊt lµ : " & MAX End Sub C. Ghi chú: ở trên chúng ta đã khai báo mảng A(100) và như vậy phần tử đầu tiên là A(0), nhưng khi nhập ta lại cho i chạy từ 1, tức là không sử dụng phần tử A(0). Đây là thói quen sử dụng của mỗi người. Bạn có thể sử dụng A(0) hay không là tuỳ, còn nếu sử dụng A(0) thì vòng lặp trên sẽ có dạng : For i= 0 to N - 1 .... Bài tập 23 a. Hướng dẫn: Cần phải tìm ra số lớn nhất, kí hiệu là MAX, sau đó hiển thị những phần tử có giá trị bằng với MAX vừa tìm được. b. Chương trình mẫu: Private Sub Form_Load() Dim i As Integer, MAX As Integer Dim DS(100) As Integer, N As Integer '/// NhËp c¸c sè N = InputBox("NhËp sè phÇn tö : ") For i = 1 To N DS(i) = InputBox("NhËp sè thø " & i) Next '/// T×m sè lín nhÊt c¸c sè võa nhËp MAX = DS(1) For i = 1 To N If MAX < DS(i) Then MAX = DS(i) Next '/// HiÓn thÞ nh÷ng phÇn tö b»ng víi MAX (chÝnh lµ nh÷ng ptö lín nhÊt) For i = 1 To N If DS(i) = MAX Then Debug.Print DS(i) Next End Sub C. Ghi chú: • Có thể áp dụng để giải bài toán tìm số nhỏ nhất, in ra các số nhỏ nhất v.v… • Trong danh sách không phải chỉ có duy nhất một phần tử lớn nhất (nhỏ nhất) Bài tập 24 a. Hướng dẫn: Để sắp xếp một dãy số A có N phần tử ta tiến hành như sau: • Bắt đầu từ phần tử đầu tiên BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 21 • Tại vị trí (phần tử) thứ i trong mảng A, Ta xét tất cả các số từ thứ i+1 đến N xem có số nào nhỏ hơn phần tử thứ i đang xét hay không. Nếu có phần tử A(j) nào đó nhỏ hơn A(i) thì hoán đổi giá trị của A(i) Cho A(j). Để hoán đổi A(i) với A(j) ta thực hiện như sau: o TrungGian = A(i) o A(i) = A(j) o A(j) = TrungGian • Lặp lại đối với các phần tử A(i) cho đến khi nào i >= N thì dừng. b. Chương trình mẫu: Private Sub Form_Load() Dim i As Integer, N As Integer, TrungGian As Integer Dim A(100) As Integer 'Khai b¸o m¶ng A cã 101 phÇn tö '///////// NhËp sè phÇn tö N vµ nhËp d÷ liÖu cho m¶ng A N = InputBox("B¹n cÇn nhËp bao nhiªu sè: ") For i = 1 To N A(i) = InputBox("NhËp vµo sè thø " & i) Next '/////// S¾p xÕp m¶ng A theo chiÒu t¨ng dÇn /////////////////////// For i = 1 To N - 1 '///DuyÖt tõng phÇn tö tõ 1 ®Õn N-1 For j = i + 1 To N '///KiÓm tra c¸c phÇn tö cßn l¹i ®øng sau phÇn tö thø i If A(j) < A(i) Then '///Nếu nhỏ hơn số i thi` Ho¸n ®æi A(i) víi A(j) TrungGian = A(i) A(i) = A(j) A(j) = TrungGian End If Next Next Debug.Print "D·y sau khi s¾p xÕp " For i = 1 To N Debug.Print A(i) Next End Sub Chú ý: • Thuật toán sắp xếp ở trên thường xuyên được sử dụng trong các bài toán không đòi hỏi nhiều về tốc độ và nó có thể áp dụng để sắp xếp một danh sách tổng quát (cả số và xâu), do vậy chúng ta cần nắm vững thuật toán này. • Nếu muốn sắp xếp danh sách theo chiều giảm dần thì chỉ việc thay câu lệnh If A(j) A(i) Then …. Bài tập 25 a. Hướng dẫn: Về bản chất, giải thuật Quick_Sort sử dụng phương pháp “Chia để trị” (Deive and Conquer). Có thể mô tả thô thuật toán này như sau: - Chọn một vị trí K ở giữa (Không nhất thiết là chính giữa) của danh sách L. - Duyệt từng phần tử và xét: Nếu phần tử L[i] < L[k] thì cho vào danh sách con L1, còn nếu L[i] >= L[k] thì cho vào danh sách L2. Kết quả ta được: L = L1 ∪ L[k] ∪ L2, Trong đó L[k] ở vị trí đúng. Tiếp tục thực hiện đệ qui với L1 và L2… Do L hữu hạn nên thuật toán sẽ dừng. Độ phức tạp của thuật toán này trung bình vào cỡ O(n) = n.Log2n. BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 22 b. Chương trình mẫu: '/// Thñ tôc t¸ch danh s¸ch thµnh 2 danh s¸ch con vµ 1 vÞ trÝ ®óng (Chèt-K) Sub TachDanhSach(DS() As Integer, ByVal L As Integer, ByVal R As Integer, K As Integer) Dim i As Integer, j As Integer, Tam As Integer i = L j = R Do While i < j Do While DS(j) > DS(i) j = j - 1 Loop Do While (DS(i) <= DS(L)) And (i < j) i = i + 1 Loop If (j > i) Then Tam = DS(i) DS(i) = DS(j) DS(j) = Tam End If Loop K = j Tam = DS(L) DS(L) = DS(j) DS(j) = Tam End Sub '----------------------------------------------------------------------------------------------------------------------------- '/// Thùc hiÖn s¾p xÕp Quick_Sort Private Sub Quick_Sort(ByRef DS() As Integer, ByVal L As Integer, ByVal R As Integer) Dim K As Integer If R > L Then TachDanhSach DS, L, R, K Quick_Sort DS, L, K - 1 Quick_Sort DS, K + 1, R End If End Sub '----------------------------------------------------------------------------------------------------------------------------- '/// Ch−¬ng tr×nh chÝnh Private Sub Form_Load() Dim i As Integer, n As Integer, DaySo(100) As Integer n = InputBox("Sè phÇn tö cÇn nhËp : ", , 10) For i = 1 To n DaySo(i) = InputBox("NhËp sè thø " & i) Next Debug.Print "D·y sè sau khi s¾p xÕp lµ : " & vbCrLf Quick_Sort DaySo, 1, n For i = 1 To n Debug.Print DaySo(i) Next End Sub BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 23 c. Ghi chú: • Trong phần khai báo hàm và thủ tục, nếu trước tham số hình thức không có từ khoá byref đứng trước thì VB hiểu đó là tham biến (tham chiếu). • Tham số hình thức trong phần khai báo chương trình con là một mảng thì phải viết dưới dạng như sau: () As , Cách viết: A (10) As integer hay A (1 to 10) As String v.v… là sai !. • Giải thuật Quick_Sort thực hiện tương đối nhanh khi n lớn. Người ta gọi giải thuật sắp xếp Quick_Sort và một số giải thuật sắp xếp nhanh khác (như Merge sort, Heap sort…) thuộc phương pháp sắp “Công nghiệp”, do vậy cần phải nhớ và vận dụng thành thạo giải thuật này. Bài tập 26 a. Hướng dẫn: Ý tưởng của giải thuật này là dùng mảng một chiều để biểu diễn cây nhị phân. Sau đó tinh chỉnh dần các cây con đã được sắp xếp để cho kết quả cuối cùng. b. Chương trình mẫu '/// Thñ tôc ho¸n ®æi gi¸ trÞ cña 2 biÕn a vµ b cho nhau (sÏ sử dông trong ch−¬ng tr×nh) Sub Swap(a As Integer, b As Integer) Dim Tam As Integer Tam = a a = b b = Tam End Sub '----------------------------------------------------------------------------------------------------------------------------- '/// Thñ tôc ®iÒu chØnh l¹i c©y con b¾t ®Çu tõ nót i ®Ó nã trë thµnh mét ®èng (Heap) '/// §iÒu chØnh t¹i nót i cña c©y DS, cã N phÇn tö Sub DieuChinhNut(i As Integer, N As Integer, DS() As Integer) Dim R As Integer If i > (N \ 2) Then Exit Sub '/// So s¸nh con tr¸i vµ con ph¶i cña nót i, nÕu con nµo lín h¬n th× '/// R sÏ l−u vÞ trÝ cña con ®ã R = 2 * i '/// Gi¶ sö con tr¸i lín h¬n If (R + 1 <= N) And (DS(R) < DS(R + 1)) Then R = R + 1 If DS(i) < DS(R) Then '//NÕu nót cha i nhá h¬n th× tr¸o ®æi l¹i gi¸ trÞ ®Ó tho¶ m·n lµ Heap Call Swap(DS(i), DS(R)) Call DieuChinhNut(R, N, DS) '/// cÇn ph¶i ®iÒu chØnh l¹i nót R sau khi ho¸n ®æi End If End Sub '----------------------------------------------------------------------------------------------------------------------------- '/// ®iÒu chØnh toµn bé N nót cña c©y (Danh s¸ch) ®Ó toµn bé c©y tho¶ m·n lµ Khèi Heap Sub DieuChinhToanBo(N As Integer, DS() As Integer) Dim i As Integer For i = N \ 2 To 1 Step -1 Call DieuChinhNut(i, N, DS) Next End Sub BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 24 '/// Thùc hiÖn HeapSort Sub Heap_Sort(N As Integer, DS() As Integer) Dim i As Integer DieuChinhToanBo N, DS For i = N To 2 Step -1 Swap DS(1), DS(i) DieuChinhNut 1, i - 1, DS Next End Sub '----------------------------------------------------------------------------------------------------------------------------- '/// Ch−¬ng tr×nh chÝnh Private Sub Form_Load() Dim i As Integer, N As Integer, DaySo(100) As Integer N = InputBox("Sè phÇn tö cÇn nhËp : ", , 10) For i = 1 To N DaySo(i) = InputBox("NhËp sè thø " & i) Next Debug.Print "D·y sè sau khi s¾p xÕp lµ : " & vbCrLf Heap_Sort N, DaySo For i = 1 To N Debug.Print DaySo(i) Next End Sub c. Ghi chú: • Toán tử “\” để thực hiện phép chia lấy phần nguyên. • Khi gọi hàm hay thủ tục có thể thêm từ khoá Call hoặc không, nhưng khi có từ khoá Call thì các tham số phải được đặt trong ngoặc đơn như trên. • Một cây nhị phân có thể biểu diễn bằng mảng một chiều, trong đó nút con trái của nút i có chỉ số là i*2 và nút con phải là i*2 + 1. Nút cha của nút i có chỉ số là i \ 2. Bài tập 27 a. Hướng dẫn: Việc sắp xếp có thể thực hiện thông qua giải thuật sắp xếp đơn giản có độ phức tạp tính toán n2. (Áp dụng thuật toán đã sử dụng trong bài tập 12) b. Chương trình mẫu: Private Sub Form_Load() Dim DanhSach(100) As String ‘// Mảng lưu danh sách tên của lớp Dim SoSV As Integer '//Số Sinh viên nhập vào Dim i As Integer SoPT = InputBox("Bạn cần nhập tên của bao nhiêu người : ") For i = 1 To SoSV DanhSach(i) = InputBox("Nhập tên của người thứ " & i) Next Dim j As Integer, TrungGian As String '/// Sắp xếp tăng dần bằng 1 thuật toán đơn giản (dùng với số pt ít) BÀI TẬP LẬP TRÌNH HƯỚNG SỰ KIỆN Biên soạn: Bộ môn CNPM–ĐHSPKT HY 2005 Trang 25 For i = 1 To SoSV- 1 For j = i + 1 To SoSV If DanhSach(j) < DanhSach(i) Then TrungGian = DanhSach(i) DanhSach(i) = DanhSach(j) DanhSach(j) = TrungGian End If Next Next '/// Hiển thị danh sách vừa sắp xếp ra cửa sổ Immediate '/// Nhấn Ctrl-G để hiển thị cửa sổ này For i = 1 To SoSV Debug.Print DanhSach(i) Next End Sub c. Ghi chú: Có thể áp dụng giải thuật Quic_Sort và Heap_Sort ở các bài tập trước để thực hiện sắp xếp trên danh sách ở dạng xâu ký tự. Bài tập 28: a. Hướng dẫn: Sử dụng các hàm thao tác xâu ký tự. • Hàm Trim(S) trả về xâu S nhưng không có dấu trắng ở 2 đầu (Lưu ý: Bản thân xâu S không bị thay đổi). • Hàm Replace(S, Sc, Sm) : Hàm thay thế tất cả các xâu con Sc nằm trong xâu cha S bằng xâu Sm. b. Chương trình mẫu: '----------------------------------------------------------------------------------------------------------------------------- '/// Hµm chuÈn ho¸ x©u ký tù S. Gi¸ trÞ tr¶ vÒ cho hµm lµ x©u ®−îc chuÈn ho¸ '/// X©u vµo ®−îc truyÒn ë d¹ng tham trÞ. Hµm kh«ng lµm thay ®æi x©u vµo S '----------------------------------------------------------------------------------------------------------------------------- Function ChuanHoa(ByVal S As String) As String '/// Thªm dÊu tr¾ng vµo sau dÊu chÊm "." -> hay dấu “.” = “.” + dấu trắng S = Replace(S, ".", "." & Chr(32)) '//Thªm dÊu tr¾ng vµo sau dÊu ph¶y "," -> hay thay dấu “,” bằng dấu “,” + dấu trắng S = Replace(S, ",", "," & Chr(32)) '/// Thay 2 dÊu tr¾ng b»ng 1 dÊu tr¾ng cho ®Õn khi nµo kh«ng cßn 2 dÊu tr¾ng liÒn nhau Do While InStr(1, S, Chr(32) & Chr(32)) > 0 S = Rep