BÀI 26. PHƯƠNG PHÁP LÀM MỊN DẦN TRONG THIẾT KẾ CHƯƠNG TRÌNH
Trang bìa
Trang bìa
Ảnh
TIN HỌC 11
BÀI 26. PHƯƠNG PHÁP LÀM MỊN DẦN TRONG THIẾT KẾ CHƯƠNG TRÌNH
Ảnh
Mục tiêu bài học
Mục tiêu
Ảnh
Mục tiêu:
Biết và giải thích được phương pháp làm mịn dần trong lập trình. Vận dụng được phương pháp làm mịn dần để thiết kế chương trình.
Khởi động
Khởi động
Ảnh
- 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.
Hình thành kiến thức
1. Phương pháp thiết kế làm mịn dần
1. Phương pháp thiết kế làm mịn dần
Ảnh
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à trả lời các câu 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?
- HĐ1: Tìm hiểu các bước thiết kế làm mịn dần
Bài toán gốc
Cho trước dãy số A: A[0], A[ 1], ..., A[n-1]. Cần tiến hành sắp xếp dãy phải nhận được là trên theo thứ tự tăng dần. Kết quả phải nhận được: A[0] latex(<=) A[1] latex(<=) ... latex(<=) A[n-1].
- Bài toán gốc:
Ví dụ:
Với bộ dữ liệu đầu vào là dãy [2, 1, 7, 10, 4] thì kết quả thu được dãy [1, 2, 4, 7, 10].
Ảnh
a. Tìm hiểu bài toán
Ảnh
a. Tìm hiểu bài toán
Bài toán gốc là cho trước dãy A, cần sắp xếp lại dãy này theo thứ tự tăng dần.
b. Thiết kế chương trình giải bài toán
Ảnh
b. Thiết kế chương trình giải bài toán
Việc thiết kế chương trình giải bài toán chia thành nhiều bước:
B1: Thiết lập ý tưởng thiết kế ban đầu.
B2: Thực hiện việc "Chèn A[i] vào đúng vị trí."
Ảnh
Ảnh
+ Bước 3, 4, 5 (b. Thiết kế chương trình giải bài toán)
Ảnh
B3: Nhấc A[i] lên bằng cách tạo biến value để lưu giá trị A[i]. B4: Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.
Bước 5: Chèn A[i] vào đúng vị trí trống.
Ảnh
Ảnh
c. Chương trình hoàn chỉnh
Ảnh
Ảnh
c. Chương trình hoàn chỉnh
Chương trình giải bài toán đặt ra được thiết kế hoàn chỉnh dưới dạng hàm InsertionSort(A). Tổng hợp các bước trên chúng ta có chương trình hoàn chỉnh như sau:
- Ghi nhớ
- Ghi nhớ:
Ảnh
Phương pháp làm mịn dần trong thiết kế chương trình là quá trình chi tiết hoá từ ý tưởng của các bước trước thành những hành động cụ thể hơn ở các bước sau. Ở bước cuối cùng, các hành động tương ứng với các câu lệnh của ngôn ngữ lập trình để viết chương trình hoàn chỉnh.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
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? 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 đó?
2. Thiết kế chương trình bằng phương pháp làm mịn dần
2. Thiết kế chương trình bằng phương pháp làm mịn dần
Ảnh
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.
- HĐ2: Thiết kế chương trình bằng PP làm mịn dần
Bài toán
- Bài toán:
Ảnh
Cho trước dãy số A: A[0], A[ 1], ..., A[n-1]. Cặp phần tử A[i], A[j] được gọi là nghịch đảo nếu i < j nhưng A[i] > A[j]. Cần viết chương trình đếm số các cặp nghịch đảo của dãy A. Ví dụ:
Dãy 3, 4, 2, 1 sẽ có 5 cặp nghịch đảo: (3,2), (3, 1), (4,2), (4,1), (2,1).
a. Tìm hiểu bài toán
a. Tìm hiểu bài toán
Ảnh
Bài toán gốc là cho trước dãy số A có n phần tử, cần đếm số các cặp phần tử nghịch đảo của A.
b. Thiết kế chương trình giải bài toán
b. Thiết kế chương trình giải bài toán
* Bước 1: Thiết lập ý tưởng thiết kế ban đầu.
Ảnh
* Bước 2: Tìm tất cả các cặp chỉ số (ij).
Ảnh
Ảnh
+ Bước 3: Kiểm tra tính nghịch đảo của cặp (i)) (b. Thiết kế chương trình giải bài toán)
* Bước 3: Kiểm tra tính nghịch đảo của cặp (i)).
Ảnh
Ảnh
c. Chương trình hoàn chỉnh
Ảnh
c. Chương trình hoàn chỉnh
Trên cơ sở các phân tích trên chúng ta có thể thiết lập hàm Nghichdao(A) để đếm số các cặp nghịch đảo của dãy A cụ thể:
Ảnh
- Ghi nhớ
Ảnh
- Ghi nhớ:
Phương pháp làm mịn dần trong thiết kế chương trình phải tuân thủ các quy trình và nguyên tắc sau:
Chia việc thiết kế thành từng bước và thực hiện lần lượt các bước. Mỗi bước lớn có thể được chia thành nhiều bước nhỏ để giải quyết độc lập. Tiếp cận bài toán từ tổng quan đến chi tiết, mỗi bước tiếp theo sẽ phải là thiết kế chi tiết hơn bước trước đó. Quá trình như vậy sẽ tiếp tục cho đến khi viết xong toàn bộ các câu lệnh của chương trình giải bài toán đã cho.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Ảnh
Câu 1: Với Bài toán ở Hoạt động 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 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
Ảnh
- Luyện tập
Câu 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. Câu 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
- Câu 1
Ảnh
- Vận dụng:
Câu 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".
- Câu 2 (- Luyện tập )
Ảnh
Câu 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[0], A[l], ..., A[i - 1]> bằng các lệnh sau thì chương trình vẫn đúng:
Ảnh
Dặn dò
Dặn dò
Ảnh
Dặn dò:
Ôn lại kiến thức vừa học. Làm bài tập trong SBT. Chuẩn bị bài sau: "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".
Cảm ơn
Ảnh