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

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

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 chọn, sắp xếp nổi bọt. 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.

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

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à Đáp án chuẩn các CH hỏi sau:

1. Bước này đã thực hiện được 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?

Câu hỏi 1: 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âu hỏi 2: 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?

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

Hoạt động 2: Thực hiện thiết kế thuật toán và chương trình bằng phương pháp làm mịn dần theo các bài toán sau. Trao đổi, thảo luận với bạn bè để thiết lập được lời giải tốt hơn.

Câu hỏi 1: Với Bài toán 1 có thể tách các dòng lệnh từ 4 đến 9 thành một hàm con độc lập được không?

Câu hỏi 2: Trong thiết kế bài toán tìm các cặp phần tử nghịch đảo, các bước sau đã thực hiện những thay đổi quan trọng nào so với bước trước đó?

LUYỆN TẬP

Luyện tập 1: Phát biểu sau đúng hay sai?

Khi thiết kế chương trình thì việc đầu tiên là tìm hiểu yêu cầu chung của bài toán, xác định đầu vào, đầu ra của bài toán, sau đó mới đi cụ thể vào chi tiết.

Luyện tập 2: Sử dụng thiết kế của Bài toán 2, tìm tất cả các cặp nghịch đảo của dãy: 3, 2, 1, 5, 4.

VẬN DỤNG

Vận dụng 1: Sử dụng phương pháp làm mịn dần để giải bài toán sau: Cho trước số tự nhiên không âm n, viết chương trình kiểm tra xem số n có phải là số nguyên tố hay không? Chương trình cần thông báo "CÓ" nếu n là số nguyên tế, ngược lại thông báo "KHÔNG".

Vận dụng 2: Với thuật toán sắp xếp chèn, chứng minh rằng nếu thay toàn bộ phần Chèn A[i] vào vị trị đúng của dãy con A[@), A[l], ..., A[i - 1]> bằng các lệnh sau thì chương trình vẫn đứng:

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD:

Xác định bài toán ® Tìm cấu trúc dữ liệu biểu diễn thuật toán ® Tìm Thuật toán ® Lập trình ® Kiểm thử chương trình ® Tối ưu chương trình.

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

Đáp án HD1: 

1. Bước này đã định nghĩa cách thức sắp xếp chèn.
2. Kết quả của bước này khác với kết quả của bước trước đó về cách thức sắp xếp chèn được định nghĩa và thực hiện..

Đáp án CH1: 

Bước đơn giản nhất là quá trình di chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.

Đáp án CH2: 

Các bước thiết kế như trên cần thay đổi như sau:

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

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

Đáp án HD2: 

def nghichdao(A):

 n = len(A)

 count = 0

 for i in range(n-1):

  for j in range(i+1, n):

   if A[i] > A[j]:

    count = count + 1

 return count

Đáp án CH1: 

Có thể tách các dòng lệnh từ 4 đến 9 thành một hàm con độc lập

Đáp án CH2: 

Bước thực hiện để tìm các cặp phần tử nghịch đảo trong Python có thể được thực hiện theo nhiều cách khác nhau và tùy vào cách tiếp cận của người lập trình. 

LUYỆN TẬP

Đáp án LT1: 

Đúng

Đáp án LT2: 

Có 5 cặp nghịch đảo là: (3,2), (3,1), (3,5), (3,4), và (2,1)

VẬN DỤNG

Đáp án VD1:

def is_prime(n):

 if n <= 1:

  return "KHÔNG"# Trường hợp n <= 1 không phải số nguyên tố

 elif n <= 3:

  return "CÓ"# Trường hợp n = 2 hoặc n = 3 là số nguyên tố

 elif n % 2 == 0:

  return "KHÔNG"# Trường hợp n chẵn lớn hơn

Đáp án VD2:

• Ta cần chứng minh hai điều kiện sau đây:
• Điều kiện ban đầu: Sau khi thực hiện lệnh j = 1, dãy con A[0] chỉ gồm một phần tử là A[0]. Do đó, dãy con này đã được sắp xếp đúng.
• Điều kiện duy trì: Trong mỗi vòng lặp của while, nếu A[j] < A[j-1], ta hoán đổi giá trị của A[j] và A[j-1] bằng lệnh Đổi chỗ A[j] và A[j-1]. Sau đó, ta giảm giá trị của j đi 1 đơn vị bằng lệnh j = j - 1. Lúc này, giá trị của A[j] là giá trị của A[j-1] trước khi hoán đổi, và giá trị của A[j-1] là giá trị của A[j] trước khi hoán đổi. Đồng nghĩa với việc dãy con A[0], A[1], ..., A[j-1] đã được sắp xếp đúng.