khoahoc.vietjack.com
Kích hoạt VIP
khoahoc.vietjack.com
Kích hoạt VIP Đăng nhập
Tạo VIP
  1. Lớp 11
  2. Tin học
  3. Giải chuyên đề Tin 11 Cánh diều Bài 4. Thực hành tổng hợp thiết kế thuật toán đệ quy có đáp án

Giải chuyên đề Tin 11 Cánh diều Bài 4. Thực hành tổng hợp thiết kế thuật toán đệ quy có đáp án

28 người thi tuần này 4.6 487 lượt thi 2 câu hỏi

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

🔥 Học sinh cũng đã học

11 người thi tuần này

Đề thi cuối kì 2 Tin học 11 năm 2024-2025 Sở Nam Định có đáp án

50 lượt thi 30 câu hỏi
17 người thi tuần này

Đề thi cuối kì 2 Tin học 11 năm 2025-2026 THPT Xuyên Mộc (TP.HCM) có đáp án

56 lượt thi 31 câu hỏi
11 người thi tuần này

Đề thi cuối kì 2 Tin học 11 năm 2024-2025 THPT Gio Linh (Quảng Trị) có đáp án

50 lượt thi 23 câu hỏi
12 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2025-2026 THPT Xuyên Mộc (TP.HCM) có đáp án

59 lượt thi 28 câu hỏi
9 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2024-2025 THPT Hồ Nghinh (Quảng Nam) có đáp án

56 lượt thi 20 câu hỏi
17 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2025-2026 THPT Hùng Vương (Đà Nẵng) có đáp án

64 lượt thi 20 câu hỏi
9 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2024-2025 THPT (Bắc Giang) có đáp án

56 lượt thi 23 câu hỏi
9 người thi tuần này

Đề thi cuối kì 1 Tin học 11 năm 2024-2025 THPT Gio Linh (Quảng Trị) có đáp án

46 lượt thi 29 câu hỏi

Danh sách câu hỏi:

Câu 1/2

Bài toán tháp Hà Nội.

Bài toán Tháp Hà Nội được đượ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 tuân thủ 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 chuyển được phép dùng cột B làm cọc trung gian.

Bài toán đặt ra là: Tìm cách chơi và đưa ra từng bước di chuyển đĩa thoả mãn yêu cầu.

Lời giải

Các Hình 1,2,3 lần lượt minh hoạ các bước di chuyển đĩa cần thực hiện khi số đĩa n = 1,2,3.

Với n = 1: Ta chỉ cần duy nhất một bước di chuyển đĩa từ cọc A sang cọc C.

Bài toán tháp Hà Nội. Bài toán Tháp Hà Nội được đượ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 tuân thủ 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 chuyển được phép dùng cột B làm cọc trung gian. Bài toán đặt ra là: Tìm cách chơi và đưa ra từng bước di chuyển đĩa thoả mãn yêu cầu. (ảnh 1)

Với n = 2: Ta cần 3 bước di chuyển đĩa.

Bài toán tháp Hà Nội. Bài toán Tháp Hà Nội được đượ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 tuân thủ 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 chuyển được phép dùng cột B làm cọc trung gian. Bài toán đặt ra là: Tìm cách chơi và đưa ra từng bước di chuyển đĩa thoả mãn yêu cầu. (ảnh 2)

 

Bài toán tháp Hà Nội. Bài toán Tháp Hà Nội được đượ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 tuân thủ 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 chuyển được phép dùng cột B làm cọc trung gian. Bài toán đặt ra là: Tìm cách chơi và đưa ra từng bước di chuyển đĩa thoả mãn yêu cầu. (ảnh 3)

Với n = 3: Ta cần 7 bước di chuyển đĩa

 

Bài toán tháp Hà Nội. Bài toán Tháp Hà Nội được đượ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 tuân thủ 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 chuyển được phép dùng cột B làm cọc trung gian. Bài toán đặt ra là: Tìm cách chơi và đưa ra từng bước di chuyển đĩa thoả mãn yêu cầu. (ảnh 4)

a) Trong quá trình di chuyển đĩa gồm 7 bước với n=3, nhận thấy bài toán Tháp Hà Nội cho trường hợp n=2 được giải hai lần: lần giải đầu tiên bởi ba bước 1, 2, 3 và lần giải thứ hai bởi ba bước 5, 6, 7. Sau ba bước 1, 2, 3 hai đĩa trên cùng của cọc A được chuyển sang cọc B. Do đó, ở lần giải đầu tiên này, cọc A được gọi là cọc xuất phát, cọc B được gọi là cọc đích. Em hãy nêu tên cọc xuất phát và cọc đích ở lần giải thứ hai tương ứng với ba bước 5, 6, 7.

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) Xây dựng thuật toán đệ quy giải quyết bài toán Tháp Hà Nội với n đĩa và cài đặt thuật toán đề xuất bằng một hàm đệ quy.

d) Viết chương trình yêu cầu người dùng 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âu 2/2

Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái đĩa với n kích thước khác nhau (mỗi kích thước có hai 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:

a) Hình 4 và 5 minh hoạ cách di chuyển đĩa với n = 1 và n = 2 tương ứng. Bài toán với 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 = 2. Nêu tên cọc xuất phát và cọc đích ở từng lần giải đó.

b) 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 đó.

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

Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái đĩa với n kích thước khác nhau (mỗi kích thước có hai 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: a) Hình 4 và 5 minh hoạ cách di chuyển đĩa với n = 1 và n = 2 tương ứng. Bài toán với 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 = 2. Nêu tên cọc xuất phát và cọc đích ở từng lần giải đó. (ảnh 1)

Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái đĩa với n kích thước khác nhau (mỗi kích thước có hai 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: a) Hình 4 và 5 minh hoạ cách di chuyển đĩa với n = 1 và n = 2 tương ứng. Bài toán với 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 = 2. Nêu tên cọc xuất phát và cọc đích ở từng lần giải đó. (ảnh 2)

Lời giải

a) Hình 4 và 5 minh hoạ cách di chuyển đĩa với n = 1 và n = 2 tương ứng. 

b) 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 đó.

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

 

Đăng ký

Bạn đã có tài khoản?

Khóa học 1 - 12
THPT
THCS
Phòng luyện đề
ĐGNL - ĐGTD
Tốt nghiệp THPT
Ôn vào 10
Ôn vào 6
Tài liệu
THPT
THCS
Tin Tuyển Sinh
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
Giấy chứng nhận ĐKKD số: 0108307822 do Sở KH & ĐT TP Hà Nội cấp lần đầu ngày 04/06/2018
© 2017 Vietjack87. All Rights Reserved.
zalo Nhắn tin Zalo Hỏi bài tập