Giải bài 26: Phương pháp làm mịn dần trong thiết kế chương trình | Tin học 11 Kết nối tri thức

Tin học 11 Kết nối tri thức bài 26 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. Bài làm
Thực hiện chi tiết hóa các bước lập trình Các bước 1. Xác định bài toán
2. Tìm cấu trúc dữ liệu biểu diễn thuật toán. 3. Tìm Thuật Toán. 4. Lập Trình (Programming)
5. Kiểm thử chương trình (Testing program)
6. Tối ưu chương trình (optimization program)
1. Phương pháp thiết kế làm mịn dần
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? Bài làm
Xác định cách thức sắp xếp chèn: Sắp xếp chèn là một thuật toán đơn giản, trong đó
từng phần tử của dãy đang xét được chèn vào vị trí đúng của dãy con đã được sắp
xếp trước đó. Bước này định nghĩa cách thức sắp xếp chèn, bao gồm quá trình so
sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng.
1. Bước này đã định nghĩa cách thức sắp xếp chèn, bao gồm cách thức so sánh và di
chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.
2. Kết quả của bước này khác với kết quả của bước trước đó về cách thức sắp xếp
chèn được định nghĩa và thực hiện. Bước này tập trung vào việc định nghĩa và triển
khai thuật toán sắp xếp chèn cụ thể, trong khi bước trước đó có thể là các bước
chuẩn bị dữ liệu, định nghĩa bài toán, hoặc thiết kế các thuật toán phụ trợ khác.
Câu hỏi 1. Trong các bước đã thực hiện của bài toán sắp xếp chèn ở trên, bước nào
là đơn giản nhất theo nghĩa có thể thực hiện ngay bảng các lệnh lập trình. Bài làm
Bước đơn giản nhất của bài toán sắp xếp chèn mà có thể thực hiện ngay bằng các
lệnh lập trình là quá trình di chuyển các phần tử để đưa phần tử mới vào vị trí đúng
của dãy con đã được sắp xếp trước đó.
Câu hỏi 2. Nếu bài toán đặt ra là sắp xếp dãy A theo thứ tự giảm dần thì các bước
thiết kế như trên có cần thay đổi không? Thay đổi như thế nào? Bài làm
Các bước thiết kế như trên cần thay đổi như sau: def Insertionsort(A): n=len(A) for i in range(1,n): value=A[i] j=i-1
while j>=0 and A[j] A[j+1]=A[j] j=j-1 A[j+1]=value
2. Thiết kế chương trình bằng phương pháp làm mịn dần
Hoạt động 2: Thiết kế chương trình bằng phương pháp làm mịn dần
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. Bài làm def nghichdao(A): n = len(A) count = 0 for i in range(n-1): for j in range(i+1, n): if A[i] > A[j]: count = count + 1 return count
Câu hỏi 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? Bài làm
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âu hỏi 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 đó? Bài làm
Bước thực hiện để tìm các cặp phần tử nghịch đảo trong Python có thể được thực
hiện theo nhiều cách khác nhau và tùy thuộc vào cách tiếp cận của người lập trình.
Giả sử chúng ta đang thực hiện các bước sau để giải quyết bài toán tìm các cặp phần
tử nghịch đảo trong Python:
- Tạo một danh sách các số nguyên cần tìm các cặp phần tử nghịch đảo.
- Tạo một danh sách trống để lưu các cặp phần tử nghịch đảo tìm được.
- Duyệt qua từng phần tử trong danh sách các số nguyên, và cho vào một vòng lặp
trong đó duyệt qua các phần tử còn lại của danh sách.
- Tại mỗi cặp phần tử được duyệt qua, kiểm tra xem tích của chúng có bằng 1
không. Nếu có, thêm cặp phần tử này vào danh sách chứa các cặp phần tử nghịch đảo.
Một vài thay đổi quan trọng có thể được thực hiện so với cách tiếp cận mặc định
này ví dụ như sử dụng thuật toán tìm kiếm nhị phân để tìm các cặp phần tử nghịch
đảo thay vì duyệt qua từng phần tử hoặc sử dụng một thư viện bên ngoài như
NumPy để thực hiện tính toán và tìm kiếm các cặp phần tử nghịch đảo. Tuy nhiên
các bước cơ bản được giới thiệu ở trên vẫn được sử dụng rộng rãi và cung cấp một
cách tiếp cận đơn giản và hiệu quả để giải quyết bài toán tìm các cặp phần tử nghịch đảo trong Python. 3. Luyện tập
Câu hỏi 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. Bài làm
Phát biểu trên là đúng. Khi thiết kế chương trình, việc đầu tiên là hiểu rõ yêu cầu
chung của bài toán, xác định đầu vào và đầu ra của bài toán. Việc này giúp định
hướng rõ ràng cho quá trình thiết kế, đảm bảo rằng chương trình được xây dựng
đúng theo yêu cầu của bài toán và đáp ứng được các yêu cầu của người dùng. Sau
đó, mới đi vào chi tiết thiết kế chương trình, bao gồm việc lựa chọn thuật toán, cấu
trúc dữ liệu, giao diện người dùng, kiểm tra lỗi, v.v. Việc đúng đắn từ đầu sẽ giúp
tiết kiệm thời gian và nguồn lực trong quá trình phát triển chương trình.
Câu hỏi 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. Bài làm
Có 5 cặp nghịch đảo là: (3,2), (3,1), (3,5), (3,4), và (2,1) 4. Vận dụng
Câu hỏi 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". Bài làm def is_prime(n): if n <= 1:
return "KHÔNG"# Trường hợp n <= 1 không phải số nguyên tố elif n <= 3:
return "CÓ"# Trường hợp n = 2 hoặc n = 3 là số nguyên tố elif n % 2 == 0:
return "KHÔNG"# Trường hợp n chẵn lớn hơn
Câu hỏi 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[@), A[l], ..., A[i - 1]> bằng các lệnh sau thì chương trình vẫn đứng: Bài làm
Để chứng minh tính đúng đắn của thuật toán sắp xếp chèn với các lệnh thay đổi
trên, ta cần chứng minh hai điều kiện sau đây:
Điều kiện ban đầu (trước khi bắt đầu vòng lặp): Sau khi thực hiện lệnh j = 1, giá trị
của j đang là 1, và dãy con A[0] chỉ gồm một phần tử là A[0] (vì j-1 là 0). Do đó,
dãy con này đã được sắp xếp đúng.
Điều kiện duy trì (trong quá trình vòng lặp): Trong mỗi vòng lặp của while, nếu A[j]
< A[j-1], ta hoán đổi giá trị của A[j] và A[j-1] bằng lệnh Đổi chỗ A[j] và A[j-1]. Sau
đó, ta giảm giá trị của j đi 1 đơn vị bằng lệnh j = j - 1. Lúc này, giá trị của A[j] là giá
trị của A[j-1] trước khi hoán đổi, và giá trị của A[j-1] là giá trị của A[j] trước khi
hoán đổi. Điều này đồng nghĩa với việc dãy con A[0], A[1], ..., A[j-1] đã được sắp
xếp đúng sau mỗi vòng lặp.
Vậy nên, dãy con A[0], A[1], ..., A[j-1] luôn được sắp xếp đúng sau mỗi vòng lặp
của while, và dãy con này sẽ không bị thay đổi giá trị trong quá trình hoán đổi. Do
đó, tính đúng đắn của thuật toán sắp xếp chèn vẫn được duy trì sau khi thay toàn bộ
phần chèn A[i] vào vị trí đúng của dãy con A[0], A[1], ..., A[i-1] bằng các lệnh trên.
Document Outline

• Khởi động
• 1. Phương pháp thiết kế 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
• 3. Luyện tập
• 4. Vận dụng