Giáo án 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

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chia lớp thành các nhóm từ 2 – 4 HS.

- GV chiếu nhiệm vụ học tập:

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.

- GV mô tả nhiệm vụ và phác thảo các bước thiết kế chính theo phương pháp làm mịn dần:

+ Tìm hiểu bài toán

+ Thiết kế theo phương pháp làm mịn dần

+ Chương trình hoàn chỉnh

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS lắng nghe GV hướng dẫn, đọc theo SGK và thực hiện việc cài đặt thành chương trình hoàn chỉnh, tạo bộ test theo hướng dẫn và kiểm tra xem chương trình đã viết có đúng không.

- GV quan sát và trợ giúp HS.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS báo cáo các bộ test theo hướng dẫn.

- HS khác nhận xét, bổ sung cho bạn.

Bước 4: Đánh giá kết quả thực hiện:

- Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 1.

- GV chuyển sang hoạt động tiếp theo.

Nhiệm vụ 1. Kiểm tra hoán vị

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

Bài toán gốc: 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.

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

Sơ đồ khung ban đầu của lời giải như sau:

1 Sắp xếp dãy A theo thứ tự tăng dần

2 Kiểm tra A có phải là dãy 1, 2, …, n hay không

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

- Việc sắp xếp dãy A theo thứ tự tăng dần được mô tả bằng hàm sapxep(A) theo một trong các thuật toán sắp xếp mà chúng ta đã biết.

- Ví dụ bằng thuật toán sau:

1 def sapxep(A):

2     for i in range(len(A)):

3       j = i

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

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

6           j = j – 1

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]?

- Việc kiểm tra này có thể được thực hiện đơn giản như sau:

Kiểm tra lần lượt các phần tử của A với các phần tử tương ứng của dãy 1, 2, …, n. Nếu tất cả các so sánh đều bằng nhau thì trả về kết quả True, ngược lại trả về False.

- Sử dụng biến kq để trả lại kết quả của việc so sánh A và dãy các số 1, 2, …, n, ta có thể viết đoạn chương trình chi tiết thực hiện công việc được mô tả trên như sau:

1      sapxep(A)

2      kq = True

3      for i in range(len(A)):

4           if A[i] != i+1:

5              kq = False

6              break

7      return kq

- Kết quả của toàn bộ bước này có thể viết dưới dạng hàm kt_hoanvi(A), trong đó A là dãy số ban đầu. Hàm sẽ trả về True nếu A là hoán vị của [1, 2, …, n] ngược lại trả về False.

1 def kt_hoanvi(A):

2     sapxep(A)

3     kq = True

4     for i in range(len(A)):

5         if A[i] != i+1:

6            kq = False

7            break

8      return kq

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

1 def sapxep(A):

2     for i in range(len(A)):

3       j = i

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

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

6            j = j – 1

7

8 def kt_hoanvi(A):

9     sapxep(A)

10    kq = True

11    for i in range(len(A)):

12        if A[i] != i+1:

13           kq = False

14           break

15     return kq

16

17 #Chương trình chính

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

19 if kt_hoanvi(A):

20    print("CÓ")

21 else:

22    print("KHÔNG")

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chiếu nhiệm vụ học tậ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]

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS lắng nghe GV hướng dẫn, đọc theo SGK và thực hiện việc cài đặt thành chương trình hoàn chỉnh, tạo bộ test theo hướng dẫn và kiểm tra xem chương trình đã viết có đúng không.

- GV quan sát và trợ giúp HS.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS báo cáo các bộ test theo hướng dẫn.

- HS khác nhận xét, bổ sung cho bạn.

Bước 4: Đánh giá kết quả thực hiện:

- Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 2.

- GV chuyển sang hoạt động luyện tập.

Nhiệm vụ 2. Đếm số lần lặp

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

Bài toán gốc: 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.

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

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

2 for i in range(len(A)):

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

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

5 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. Hàm lap(x,A) có thể được viết như sau:

1 def lap(x,A):

2     S = 0

3     for a in A:

4         if a == x:

5            S = S + 1

6     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:

1     B = []

2     for i in range(len(A)):

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

4     return B

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

Để hoàn thiện toàn bộ chương trình cần thiết lập hàm tinh_lap(A) mô tả đoạn chương trình đã nêu trong bước 4. Hàm tinh_lap(A) trả về dãy B cần tìm:

1 def tinh_lap(A):

2     B = []

3     for a in A:

4         B.append(lap(a,A))

5     return B

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

1 def lap(x,A):

2     S = 0

3     for a in A:

4         if a == x:

5            S = S + 1

6     return S

7

8 def tinh_lap(A):

9     B = []

10    for a in A:

11        B.append(lap(a,A))

12    return B

13 # Chương trình chính

14 A = [2, 1, 1, 3, 5, 10, 2, 5, 2]

15 B = tinh_lap(A)

16 print(B)