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

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ế

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ướ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.

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().

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 neu 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ế

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ướ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 ki 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: 

Tới đây việc thiết kế theo phương pháp làm mịn dẫn kết thúc. Chương trình hoàn chỉnh được viết như sau:

Qua bài học này, các em sẽ: Thực hành thiết kế chương trình theo phương pháp làm mịn dần.

2.1. Trắc nghiệm Bài 27 SGK Tin học 11 Kết nối tri thức  

Như vậy là các em đã xem qua bài giảng Bài 27 Chủ đề 6 Tin học lớp 11 Kết nối tri thức. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Kết nối tri thức Bài 27.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Kết nối tri thức Bài 27 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 123 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 1 trang 126 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 2 trang 126 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 1 trang 126 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 2 trang 126 SGK Tin học 11 Kết nối tri thức - KNTT

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!