Lý thuyết Tin học 11 Kết nối tri thức 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

Chúng tôi xin giới thiệu bài Lý thuyết Tin học lớp 11 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 hay, chi tiết sách Kết nối tri thức sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt Tin học 11.

Bài: Thực hành thiết kế chương trình theo phương pháp làm mịn dần

1. Nhiệm vụ 1: Kiểm tra hoán vị
2. Nhiệm vụ 2: Đếm số lần lặp

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

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.

Hướng dẫn: Phân tích thiết kế

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ắp xếp A theo thứ tự tăng dần. Sau đó chỉ cần so sánh A có trùng khít với dãy [1, 2, ... n] hay không. Như vậy sơ đồ khung ban đầu của lời giải sẽ như sau:

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

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

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:

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.

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

Tổng hợp các bước làm mịn trên chúng ta thu được chương trình hoàn chỉnh cho bài toán. Chương trình hoàn chỉnh sẽ có hai chương trình con là hàm sapxep() và kt_hoanvi().

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

Thiết kế và viết chương 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 tinh đượ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. Vi du nếu A = [2, 1, 1, 3, 5, 10, 2, 5] thi B = [2, 2, 2, 1, 2, 1, 2, 2].

Hướng dẫn: Phân tích thiết kế

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.

Theo yêu cầu chúng ta cần xây dựng dãy B có cùng kích thước với dãy A và các phần tử của B liên hệ với dãy A như sau: B[k] = số lần lặp của phần tử A[k] trong dãy A. Do vậy thiết kế lời giải sơ lược ban đầu của bài toán như sau:

- Bước 2. Thiết kế dãy B rỗng.

Việc này được thực hiện đơn giản bằng lệnh B = [].

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

Công việc này có thể được thực hiện thông qua lời gọi hàm lap(x,A) tinh 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:

- 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, chúng ta thu được đoạn chương trình hoàn chỉnh đã nếu ở bước 1 như sau:

- 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 chúng ta sẽ 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: