Giáo án điện tử Khoa học máy tính 11 kết nối Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

CHÀO MỪNG CÁC EM QUAY TRỞ LẠI VỚI MÔN HỌC!

KHỞI ĐỘNG

Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp nổi bọt.

Thảo luận nhóm 3 - 4 HS

• Tất cả các thiết kế chương trình đó có điểm nào chung?
• Theo em, để thiết kế một thuật toán đúng giải một bài toán cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.

Các thuật toán và chương trình như tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp nổi bọt trên đều là các thuật toán cơ bản trong lập trình và giải quyết các vấn đề thông thường. Điểm chung của các bài toán đó là có tính đơn giản và độ phức tạp thấp.

Để thiết kế một thuật toán đúng giải một bài toán cho trước cần trải qua các bước:

BÀI 26: PHƯƠNG PHÁP LÀM MỊN DẦN TRONG THIẾT KẾ CHƯƠNG TRÌNH

NỘI DUNG BÀI HỌC

1. PHƯƠNG PHÁP THIẾT KẾ LÀM MỊN DẦN

Thảo luận nhóm 3 - 5 HS

Hoạt động 1:

Cùng trao đổi, thảo luận các bước thiết kế chương trình theo thuật toán sắp xếp chèn, từ đó đưa ra phương pháp chính khi thiết kế chương trình. Sau mỗi bước thiết kế cần trao đổi và trả lời các câu hỏi sau:

1. Bước này đã thực hiện công việc gì?
2. Kết quả vừa thực hiện với kết quả của bước trước đó khác nhau như thế nào?

Bài toán gốc. Cho trước dãy số A: A[0], A[1],..., A[n–1]. Cần tiến hành sắp xếp dãy trên theo thứ tự tăng dần. Kết quả phải nhận được:

A[0] ≤ A[1] ≤  … ≤  A[n-1]

Ví dụ với bộ dữ liệu vào là dãy [2, 1, 7, 10, 4] thì kết quả thu được dãy [1, 2, 4, 7, 10].

1. a) Tìm hiểu bài toán

Bài toán gốc là cho trước dãy A, cần sắp xếp lại dãy này theo thứ tự tăng dần.

1. b) Thiết kế chương trình giải bài toán

Bước 1:

Thiết lập ý tưởng thiết kế ban đầu

Thuật toán ban đầu có thể được mô tả như sau:

  for i in range (1,n):

      <Đặt A[i] vào đúng vị trí của dãy A[0],A[1], …, A[i-1]>

Tại dòng 2 của sơ đồ trên, bài toán được đặt ra là: "Chèn phần tử A[i] vào đúng vị trí của dãy A[0], A[1], …, A[i-1]".

Bước 2:

Làm chi tiết hơn, thực hiện việc "Chèn A[i] vào đúng vị trí"

• Việc "Chèn A[i] vào đúng vị trí" có thể thực hiện như sau:

Chèn A[i] vào đúng vị trí

1  Nhấc phần tử A[i] lên.

2  Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.

3  Chèn A[i] vào vị trí trống.

Bước 3:

Nhấc A[i] lên.

Thao tác này được thực hiện đơn giản bằng việc tạo ra một biến mới value để lưu trữ giá trị A[i].

value = A[i]

Bước 4:

Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.

 j = i – 1

 while j >= 0 and A[j] > value:

     A[j+1] = A[j]

     j = j – 1

Bước 5:

Chèn A[i] vào đúng vị trí trống

Thao tác chèn A[i] vào đúng vị trí có thể được thực hiện bằng các câu lệnh chương trình như sau:

 value A[i]

 j = i – 1

 while j >= 0 and A[j] > value:

        A[j+1] = A[j]

        j = j – 1

 A[j+1] = value

1. c) Chương trình hoàn chỉnh

• Chương trình giải bài toán đặt ra được thiết kế hoàn chỉnh dưới dạng hàm InsertionSort(A).

 def InsertionSort(A):

     n = len(A)

     for i in range(1,n):

         value = A[i]

         j = i-1

         while j >= 0 and A[j] > value:

            A[j+1] = A[j]

            j = j - 1

         A[j+1] = value

MỞ RỘNG

Phương pháp thiết kế làm mịn dần (stepwise refinement) trong khoa học máy tính còn có tên gọi là phương pháp thiết kế từ trên xuống (top-down design) là một trong những phương pháp thiết kế lâu đời nhất và được coi là phương pháp tổng quát nhất, chung nhất cho cách lập trình cấu trúc.

Phương pháp thiết kế top-down có thể mô tả bằng sơ đồ ý tưởng sau:

GHI NHỚ

Phương pháp làm mịn dần trong thiết kế chương trình là quá trình chi tiết hóa từ ý tưởng của các bước trước thành những hành động cụ thể hơn ở các bước sau. Ở bước cuối cùng, các hành động tương ứng với các câu lệnh của ngôn ngữ lập trình để viết chương trình hoàn chỉnh.

Câu hỏi củng cố kiến thức

Câu 1 (SGK - tr.120). Trong các bước đã thực hiện của bài toán sắp xếp chèn ở trên, bước nào là đơn giản nhất theo nghĩa có thể thực hiện ngay bằng các lệnh lập trình?

Các bước đơn giản nhất của cách thiết kế trên là bước 3 và 5.

• Bước 3 được thực hiện bằng một lệnh: value = A[i].
• Bước 5 được thực hiện bằng 1 lệnh: A[j+1] = value.

Câu 2 (SGK - tr.120). Nếu bài toán đặt ra là sắp xếp dãy A theo thứ tự giảm dần thì các bước thiết kế như trên có cần thay đổi không? Thay đổi như thế nào?

Chỉ thay đổi một từ trong cách mô tả tại bước 4 như sau: Chuyển các phần tử bên trái A[i] và nhỏ hơn A[i] sang phải.

2. THIẾT KẾ CHƯƠNG TRÌNH BẰNG PHƯƠNG PHÁP LÀM MỊN DẦN