Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Bài toán Tháp Hà Nội là một bài toán kinh điển có thể giải bằng đệ quy. Giả sử câu đố có ba cọc và có 2 đĩa có kích thước như hình bên

A

B

C

Hãy tìm cách chuyển các đĩa từ cọc A sang cọc C theo thứ tự tăng dần kích thước đĩa.

LƯU Ý

Cần phải chuyển chồng đĩa từ cọc A sang cọc C theo quy tắc:

(1) Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.

(2) Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn. Trong quá trình di chuyển cọc B làm cọc trung gian.

BÀI 4. THỰC HÀNH TỔNG HỢP THIẾT KẾ THUẬT TOÁN ĐỆ QUY

BÀI TOÁN THÁP HÀ NỘI

1

Bài toán Tháp Hà Nội được trình bày dưới dạng trò chơi như sau: Có ba cọc A, B, C. Trên cọc A có một chồng đĩa gồm n cái đĩa, đường kính giảm dần từ dưới lên trên. Cần phải chuyển chồng đĩa từ cọc A sang cọc C theo quy tắc:

• Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.
• Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn. Trong quá trình chuyển được phép dùng cọc B làm cọc trung gian.

Bài toán Tháp Hà Nội

Câu a

• Xác định đầu vào và đầu ra tương ứng của ba bước 1, 2, 3.
• Xác định đầu vào và đầu ra tương ứng của ba bước 5, 6, 7.
• Mô tả quá trình giải bài toán Tháp Hà Nội với trường hợp n = 3.
• Khi giải bài toán Tháp Hà Nội cho trường hợp n = 3, cần phải giải bao nhiêu lần bài toán này với n = 2?

Quan sát Hình 3, trang 21 trả lời các câu hỏi sau:

Ba bước 1, 2, 3 có đầu vào là hình bên trái của bước 1, đầu ra là hình bên phải của bước 3.

Cọc A là cọc xuất phát, cọc B là cọc đích.

Ba bước 5, 6, 7 có đầu vào là hình bên trái của bước 5, đầu ra là hình bên phải của bước 7.

Cọc B là cọc xuất phát, cọc C là cọc đích.

Quá trình giải Bài toán Tháp Hà Nội cho trường hợp n = 3

Giai đoạn 1 gồm bước 1, 2, 3: Chuyển 2 đĩa trên cùng từ cọc A sang cọc B, cọc C làm trung gian để thỏa mãn quy tắc di chuyển đã nêu trong bài toán.

Giai đoạn 2 gồm bước 4: Chuyển đĩa có đường kính lớn nhất từ cọc A sang cọc C.

Giai đoạn 1 gồm bước 1, 2, 3: Chuyển 2 đĩa trên cùng từ cọc A sang cọc B, cọc C làm trung gian để thỏa mãn quy tắc di chuyển đã nêu trong bài toán.

Khi giải bài toán Tháp Hà Nội cho trường hợp n = 3, cần phải giải hai lần bài toán này với n = 2

Câu b

Với n = 4, giả sử đã chuyển được ba đĩa trên cùng của cọc A sang cọc B. em hãy thực hiện tiếp các bước để cả 4 đĩa đều ở cọc C và cho biết khi giải bài toán Tháp Hà Nội với n = 4 ta cần giải bao nhiều lần bài toán này với n = 3.

Đọc thông tin và trả lời câu hỏi:

Quá trình thực hiện bài toán Tháp Hà Nội với n = 4

GIAI ĐOẠN 1

Trạng thái ban đầu: 4 đĩa đang ở cọc A

Trạng thái thứ hai: chuyển 3 đĩa trên cùng của cọc A sang cọc B.

Ta phải giải bài toán Tháp Hà Nội với n = 3 để chuyển từ trạng thái ban đầu sang trạng thái thứ hai.

Giai đoạn 2: Chuyển đĩa có đường kính lớn nhất từ cọc A sang cọc C. Giai đoạn này chỉ cần 1 bước.

Giai đoạn 3: Tất cả các bước mà HS vừa liệt kê (loại trừ bước đầu đã tương ứng với giai đoạn 2) thực hiện công việc chuyển ba đĩa ở cọc B sang cọc C

Giai đoạn này phải giải bài toán với n = 3.

Câu c

Dựa vào những phân tích đã nêu ở câu a) và b) kết hợp với sơ đồ chung đã học ở Bài 2 viết hàm đệ quy: HanoiTower(n, ten_coc_xuat_phat, ten_coc_dich, ten_coc_trung_gian)

Đọc thông tin và trả lời câu hỏi:

• Hàm HanoiTower(n, A, C, B)
• Giai đoạn 1 được thực hiện bằng câu lệnh:
• Giai đoạn 2 được thực hiện bằng câu lệnh:
• Giai đoạn 3 được thực hiện bằng câu lệnh:
• Trường hợp cơ sở của bài toán được xác định khi không còn đĩa nào, tương ứng với n = 0.

Câu d

Viết chương trình yêu cầu người dung nhập vào số lượng đĩa n và gọi hàm đệ quy đã xây dựng được, để hướng dẫn người chơi các bước di chuyển đĩa. Sau đó, em hãy chạy thử chương trình với các giá trị n lần lượt là 3, 4, 5 kiểm thử chương trình.

Đọc thông tin và trả lời câu hỏi:

def HanoiTower(n, ten_coc_xuat_phat, ten_coc_dich, ten_coc_trung_gian):

if (n ==0): #Trường hợp cơ sở

return #Không làm gì

else: #Gọi đệ quy

HanoiTower(n–1, ten_coc_xuat_phat, ten_coc_ trung_gian, ten_coc_dich)

print("Chuyển đĩa "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ ten_coc_dich)

HanoiTower(n–1, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

n = int(input("Nhập số lượng đĩa n = "))

HanoiTower(n, "A", "C", "B")

Kết luận: Các bước thực hiện khi giải bài toán Tháp Hà Nội trong trường hợp n đĩa được chia làm 3 giai đoạn:

CÁC GIAI ĐOẠN THỰC HIỆN

• Giai đoạn 1 có thể gồm nhiều bước: Thực hiện giải bài toán Tháp Hà Nội cho trường hợp n – 1 để chuyển n – 1 đĩa trên cùng (gồm các đĩa 1, 2… n – 1) từ cọc A sang cọc B. Trong quá trình di chuyển sẽ dùng cọc C làm trung gian để thỏa mãn các quy tắc di chuyển đã nêu.
• Giai đoạn 2 gồm một bước: Chuyển đĩa có đường kính lớn nhất (đĩa n) từ cọc A sang cọc C.
• Giai đoạn 3 có thể gồm nhiều bước: Thực hiện giải bài toán Tháp Hà Nội cho trường hợp n – 1 để chuyển toàn bộ n – 1 đĩa đang ở cọc B (gồm các đĩa 1, 2… n – 1) sang cọc C. Trong quá trình di chuyển sẽ dùng cọc A làm trung gian để thỏa mãn các quy tắc di chuyển đã nêu.

LUYỆN TẬP

Câu 1: Giai đoạn 2 trong bài toán Tháp Hà Nội với số lượng đĩa n gồm một bước: Chuyển đĩa có đường kính lớn nhất (đĩa n) từ cọc A sang cọc C được thực hiện thông qua câu lệnh:

A. print("Chuyển đĩa", n, "từ cọc A sang cọc C")

B. n = int(input("Nhập kích thước n = "))

C. HanoiTower(n-1, B, C, A)

D. HanoiTower(n–1, ten_coc_xuat_phat, ten_coc_ trung_gian, ten_coc_dich)

A. print("Chuyển đĩa", n, "từ cọc A sang cọc C")

Câu 2: Với n = 1 có bao nhiêu giai đoạn chuyển đĩa từ cọc A sang cọc C?

A. 1

B. 2

C. 3

D. 4

A. 1

Câu 3: Khi giải bài toán Tháp Hà Nội với n = 4, ta cần giải bao nhiêu lần bài toán với n = 3?

A. 1

B. 2

C. 3

D. 4

B. 2

Câu 4: Chọn đáp án đúng khi nói về quy tắc chuyển chồng đĩa từ cọc A sang cọc C:

A. Mỗi lần được chuyển một đĩa ở vị trí bất kì của một cọc.

B. Mỗi lần được chuyển hai đĩa ở trên cùng của một cọc.

C. Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.

D. Mỗi lần được chuyển lớn nhất trên một cọc.

C. Mỗi lần chỉ chuyển một đĩa ở trên cùng của một cọc.

Câu 5: Cho chương trình:

def HanoiTower(n, ten_coc_xuat_phat, ten_coc_dich, ten_coc_trung_gian):

if (n ==0): #Trường hợp cơ sở

return #Không làm gì

else: #Gọi đệ quy

HanoiTower(n–1, ten_coc_xuat_phat, ten_coc_ trung_gian, ten_coc_dich)

print("Chuyển đĩa "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ ten_coc_dich)

HanoiTower(n, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

n = int(input("Nhập số lượng đĩa n = "))

HanoiTower(n, "A", "C", "B")

Câu lệnh nào bị viết sai?

A. print("Chuyển đĩa "+str(n)+" từ cọc "+ ten_coc_xuat phat+ " sang cọc "+ ten_coc_dich)

B. n = int(input("Nhập số lượng đĩa n = "))

C. HanoiTower(n, "A", "C", "B")

D. HanoiTower(n, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

D. HanoiTower(n, ten_coc_trung_gian, ten_coc_dich, ten_coc_xuat_phat)

VẬN DỤNG

Xét bài toán Tháp Hà Nội trong các trường hợp cọc A có một chồng đĩa gồm 2n cái đĩa với n kích thước khác nhau (mỗi kích thước có 2 cái đĩa), đường kính giảm dần từ dưới lên trên. Em hãy thực hiện các yêu cầu sau:

• Hình 4 và 5 minh họa cách di chuyển đĩa với n = 1 và n = 2 tương ứng. Bài toán n = 2 có 6 bước di chuyển đĩa, em hãy cho biết trong đó có bao nhiêu lần giải bài toán với n = 1, nêu tên cọc xuất phát và cọc đích ở từng lần giải đó.
• Khi giải bài toán với n = 3 thì phải giải bài toán với n nhỏ hơn nào, nêu tên cọc xuất phát và cọc đích ở từng lần giải đó.
• Viết hàm đệ quy giải quyết bài toán. Kết quả là hiển thị các bước di chuyển đĩa. Sau đó, chạy hàm này với n lần lượt là 3, 4, 5 và kiểm tra kết quả thu được.

a

Đánh thứ tự các đĩa trên cọc A như ở hình bên dưới, các bước di chuyển đĩa trong bài toán với kích thước n = 2 được chia làm 3 giai đoạn:

Giai đoạn 1 gồm bước 1 + bước 2: Chuyển lần lượt 2 đĩa trên cùng (gồm 2 đĩa size 1) từ cọc A sang cọc B. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là A, cọc đích là B.

Giai đoạn 2 gồm bước 3 + bước 4: Chuyển toàn bộ lần lượt 2 đĩa đang ở cọc A (gồm 2 đĩa size 2) sang cọc C. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là A, cọc đích là C.

Giai đoạn 3 gồm bước 5 + bước 6: Chuyển toàn bộ lần lượt 2 đĩa đang ở cọc B (gồm 2 đĩa size 1)sang cọc C. Giai đoạn này tương ứng với giải bài toán kích thước n = 1, cọc xuất phát là B, cọc đích là C.

--------------- Còn tiếp ---------------