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

NHIỆT LIỆT CHÀO ĐÓN CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ cây để mô tả phương pháp này không?

BÀI 27: THỰC HÀNH THIẾT KẾ CHƯƠNG TRÌNH THEO PHƯƠNG PHÁP LÀM MỊN DẦN

NHIỆM VỤ THỰC HÀNH

NHIỆM VỤ 1: KIỂM TRA HOÁN VỊ

Hoạt động nhóm từ 2 - 4 HS

Bài toán. Cho trước một dãy n số, các số được kí hiệu A[0], A[1],..., A[n-1]. Cần thiết kế chương trình kiểm tra xem dãy trên có phải là một hoán vị của dãy số 1, 2,…, n hay không. Chương trình cần thông báo kết quả là CÓ hoặc KHÔNG.

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

Cho trước dãy số A gồm n phần tử, cần kiểm tra xem A có phải là một hoán vị của dãy số 1, 2,..., n hay không.

1. b) Thiết kế theo phương pháp làm mịn dần

Bước 1. Thiết lập ý tưởng thiết kế ban đầu

Bước 2. Sắp xếp dãy A

Bước 3. Với dãy A đã được sắp xếp, kiểm tra A có phải là dãy [1, 2, …, n]?

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

 def sapxep(A):

     for i in range(len(A)):

         j = i

         while j > 0 and A[j] < A[j-1]:

            A[j],A[j-1] = A[j-1],A[j]

            j = j – 1

 def kt_hoanvi(A):

     sapxep(A)

    kq = True

    for i in range(len(A)):

        if A[i] != i+1:

           kq = False

           break

    return kq

 #Chương trình chính

 A = [2,1,9,10,8,6,5,2,3,1]

 if kt_hoanvi(A):

    print("CÓ")

 else:

    print("KHÔNG")

NHIỆM VỤ 2: ĐẾM SỐ LẦN LẶP

Thiết kế và việc chương trình trình theo phương pháp làm mịn dần cho bài toán sau:

Cho trước dãy số A[0], A[1], ...A[n-1]. Cần tính được mỗi giá trị của các phần tử của dãy trên được lặp lại bao nhiêu lần trong dãy đó. Kết quả cần được đưa ra dãy B. Như vậy dãy B sẽ có ý nghĩa như sau B[k] = số lần lặp của phần tử A[k] trong dãy A. Ví dụ nếu A = [2, 1, 1, 3, 5, 10, 2, 5] thì B = [2, 2, 2, 1, 2, 1, 2, 2].

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

Cho trước dãy số A có n phần tử. Cần tạo ra một dãy mới là số các lần lặp của các phần tử tương ứng trong A.

1. b) Thiết kế theo phương pháp làm mịn dần

Bước 1. Thiết lập ý tưởng thiết kế ban đầu

 Thiết lập dãy B rỗng

 for i in range(len(A)):

     Tính số lần lặp của A[i] trong dãy A

     Bổ sung giá trị này vào dãy B

 Trả về dãy B

Bước 2. Thiết lập dãy B rỗng

Thực hiện bằng lệnh B = [].

Bước 3. Tính số lần lặp của A[i] trong dãy A.

Thực hiện thông qua lời gọi hàm lap(x,A) tính số lần lặp của một giá trị bất kì trong dãy A:

 def lap(x,A):

     S = 0

     for a in A:

         if a == x:

            S = S + 1

     return S

Bước 4. Bổ sung số lần lặp vào dãy B

Tổng hợp kết quả của các bước trên, đoạn chương trình hoàn chỉnh đã nêu ở bước 1 như sau:

     B = []

     for i in range(len(A)):

         B.append(lap(A[i],A))

     return B

Bước 5. Trả về dãy B cần tìm của bài toán

Thiết lập hàm tinh_lap(A) mô tả đoạn chương trình đã nêu trong Bước 4.

 def tinh_lap(A):

     B = []

     for a in A:

         B.append(lap(a,A))

     return B

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