Câu hỏi mở đầu trang 118

Đề bài: 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?

Lời giải:

Điểm chung của các thiết kế thuật toán/chương trình đã học:

• Đều bắt đầu từ ý tưởng tổng quát, sau đó cụ thể hóa dần thành các câu lệnh chi tiết.
• Đều sử dụng các cấu trúc cơ bản: vòng lặp, câu lệnh điều kiện.
• Đều được mô tả bằng ngôn ngữ tự nhiên trước, rồi mới chuyển thành ngôn ngữ lập trình.

Các bước thiết kế một thuật toán đúng:

1. Tìm hiểu bài toán: xác định đầu vào và đầu ra.
2. Đưa ra ý tưởng ban đầu dưới dạng tổng quát.
3. Chi tiết hoá (làm mịn) dần các thao tác lớn thành các thao tác nhỏ hơn.
4. Viết thành câu lệnh cụ thể bằng ngôn ngữ lập trình.

1. Phương pháp thiết kế làm mịn dần

Hoạt động 1 trang 118

Đề bài: 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?

Lời giải:

Bài toán gốc: Sắp xếp dãy A tăng dần.

Quá trình thiết kế được thực hiện qua 5 bước làm mịn dần:

→ Kết luận: Mỗi bước tiếp theo là sự chi tiết hoá (làm mịn) của bước trước, chuyển dần từ mô tả bằng ngôn ngữ tự nhiên sang câu lệnh cụ thể của ngôn ngữ lập trình.

Câu hỏi củng cố mục 1 trang 120

Đề bà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?

Lời giải:

Các bước đơn giản nhất là Bước 3 và Bước 5, vì có thể thực hiện ngay bằng một câu lệnh:

• Bước 3: “Nhấc A[i] lên” → value = A[i].
• Bước 5: “Chèn A[i] vào vị trí trống” → A[j+1] = value.

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?

Lời giải:

Các bước thiết kế giữ nguyên, chỉ cần thay đổi điều kiện so sánh ở Bước 4:

• Với dãy tăng dần: chuyển các phần tử lớn hơn value sang phải → điều kiện A[j] > value.
• Với dãy giảm dần: chuyển các phần tử nhỏ hơn value sang phải → điều kiện A[j] < value.

Đoạn lệnh chỉ cần đổi dấu so sánh:

value = A[i]
j = i - 1
while j >= 0 and A[j] < value:    # đổi > thành <
    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 trang 120

Đề bài: 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 bài toán sau.

Bài toán: 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 là (3,2), (3,1), (4,2), (4,1), (2,1).

Lời giải:

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

• Đầu vào: dãy A gồm n phần tử.
• Đầu ra: số các cặp phần tử nghịch đảo của A.

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

Bước 1 – Ý tưởng ban đầu: Đếm tất cả các cặp (A[i], A[j]) là nghịch đảo.

count = 0
Tìm tất cả các cặp chỉ số (i, j) có thể tạo ra cặp phần tử nghịch đảo
Kiểm tra nếu cặp A[i], A[j] là nghịch đảo thì tăng count lên 1 đơn vị
return count

Bước 2 – Tìm tất cả các cặp chỉ số (i, j):

Vì cặp (i, j) cần thoả mãn i < j, ta dùng 2 vòng lặp lồng nhau:

for i in range(n-1):
    for j in range(i+1, n):

Sau bước 2, thuật toán trở thành:

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        if <cặp (i, j) là nghịch đảo>:
            tăng count lên 1 đơn vị
return count

Bước 3 – Kiểm tra tính nghịch đảo của cặp (i, j):

Vòng lặp ở Bước 2 đã đảm bảo i < j, vậy chỉ cần kiểm tra thêm điều kiện A[i] > A[j].

if A[i] > A[j]:
    count = count + 1

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

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 củng cố mục 2 trang 122

Đề bài:

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?

Lời giải:

Có thể. Ta tách phần chèn A[i] vào đúng vị trí thành một hàm con:

def ChenPhanTu(A, i):
    value = A[i]
    j = i - 1
    while j >= 0 and A[j] > value:
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = value

def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        ChenPhanTu(A, i)

→ Chương trình trở nên rõ ràng, dễ đọc và có thể tái sử dụng hàm ChenPhanTu ở nơi khác.

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 đó?

Lời giải:

• Bước 1 → Bước 2: Cụ thể hoá thao tác “Tìm tất cả các cặp chỉ số (i, j)” thành hai vòng lặp lồng nhau với range(n-1) và range(i+1, n).
• Bước 2 → Bước 3: Cụ thể hoá điều kiện “cặp (i, j) là nghịch đảo” thành câu lệnh if A[i] > A[j] (vì điều kiện i < j đã được đảm bảo bởi vòng lặp).

→ Mỗi bước sau đều chuyển đổi mô tả bằng chữ thành câu lệnh cụ thể của ngôn ngữ lập trình.

Luyện tập

Luyện tập trang 122

Đề bà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.”

Lời giải:

Phát biểu đúng.

Giải thích: Đây chính là nguyên tắc đầu tiên của phương pháp làm mịn dần – tiếp cận bài toán từ tổng quan (tìm hiểu yêu cầu, đầu vào, đầu ra) trước, sau đó mới cụ thể hoá dần thành các bước chi tiết. Nếu chưa hiểu rõ bài toán mà đã lập trình ngay thì rất dễ sai.

2. Sử dụng thiết kế của Bài toán ở Hoạt động 2, tìm tất cả các cặp nghịch đảo của dãy: 3, 2, 1, 5, 4.

Lời giải:

Dãy A = [3, 2, 1, 5, 4], có 5 phần tử (chỉ số 0 đến 4). Duyệt tất cả các cặp (i, j) với i < j:

→ Dãy có 4 cặp nghịch đảo: (3, 2), (3, 1), (2, 1), (5, 4).

Vận dụng

Vận dụng trang 122

Đề bà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”.

Lời giải:

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

• Đầu vào: số tự nhiên không âm n.
• Đầu ra: thông báo “CÓ” nếu n là số nguyên tố, “KHÔNG” nếu ngược lại.

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

Bước 1 – Ý tưởng ban đầu:

Nhập n
Kiểm tra n có phải số nguyên tố hay không
Nếu là số nguyên tố → in "CÓ", ngược lại → in "KHÔNG"

Bước 2 – Chi tiết hoá “Kiểm tra n có phải số nguyên tố”:

Số nguyên tố là số lớn hơn 1 và chỉ có 2 ước là 1 và chính nó. Vậy:

• Nếu n < 2 → không phải số nguyên tố.
• Nếu n ≥ 2 → duyệt các số k từ 2 đến n – 1, nếu tìm được số k mà n chia hết cho k → không phải số nguyên tố; ngược lại → là số nguyên tố.

la_snt = True
if n < 2:
    la_snt = False
else:
    Duyệt k từ 2 đến n-1, nếu n chia hết cho k thì la_snt = False

Bước 3 – Cụ thể hoá phần duyệt:

for k in range(2, n):
    if n % k == 0:
        la_snt = False

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

n = int(input("Nhập số tự nhiên n: "))
la_snt = True

if n < 2:
    la_snt = False
else:
    for k in range(2, n):
        if n % k == 0:
            la_snt = False

if la_snt:
    print("CÓ")
else:
    print("KHÔNG")

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[1], ..., A[i - 1]> bằng các lệnh sau thì chương trình vẫn đúng:

j = i
while j > 0 and A[j] < A[j-1]:
    Đổi chỗ A[j] và A[j-1]
    j = j - 1

Lời giải:

Ý tưởng chứng minh:

Đoạn lệnh mới sử dụng cách đổi chỗ trực tiếp hai phần tử liền kề, thay vì cách “nhấc A[i] – dịch phải – đặt vào chỗ trống” ban đầu. Ta chứng minh cả hai cách đều đưa A[i] về đúng vị trí trong dãy A[0], A[1], …, A[i].

Diễn biến của đoạn lệnh mới:

• Đầu vòng lặp: j = i. Xét phần tử A[j] = A[i].
• Nếu A[j] < A[j-1]: giá trị A[j] nhỏ hơn phần tử liền trước → đổi chỗ để A[j] “trượt sang trái”, sau đó giảm j = j – 1 để tiếp tục so sánh.
• Vòng lặp dừng khi:
  • j == 0: đã tới đầu dãy, không còn phần tử nào bên trái để so sánh.
  • Hoặc A[j] >= A[j-1]: A[j] đã lớn hơn hoặc bằng phần tử liền trước → nằm đúng vị trí trong dãy đã sắp xếp.

Kết luận:

• Sau vòng lặp, phần tử A[i] ban đầu đã được đưa về đúng vị trí trong dãy A[0], A[1], …, A[i] sao cho dãy này sắp xếp tăng dần.
• Các phần tử bên trái A[i] cũng vẫn giữ nguyên thứ tự tăng dần (vì chỉ đổi chỗ khi thực sự cần).
• Do đó, cách viết mới cho cùng kết quả với cách viết cũ.

→ Chương trình sắp xếp chèn theo đoạn lệnh mới vẫn đúng.

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa