Với giải Vận dụng 1 trang 24 Chuyên đề Tin học 11 Kết nối tri thức chi tiết trong Bài 4: Tháp Hà Nội giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

Giải Chuyên đề Tin học 11 Bài 4: Tháp Hà Nội

Vận dụng 1 trang 24 Chuyên đề Tin học 11: Hãy chứng minh công thức

H(n) = 2ⁿ - 1 bằng quy nạp toán học. Hãy tính H(64) và so sánh với con số các bước đã được đưa ra trong tờ quảng cáo của trò chơi vào năm 1883.

Lời giải:

- Nếu chỉ có một đĩa (n=1), H(n) = 1.

- Nếu có n đĩa, để chuyển tất cả các đĩa từ tháp ban đầu sang tháp đích, ta phải thực hiện các bước sau:

Chuyển n-1 đĩa từ tháp ban đầu sang tháp trung gian.

Chuyển đĩa cuối cùng (đĩa lớn nhất) từ tháp ban đầu sang tháp đích.

Chuyển n-1 đĩa từ tháp trung gian sang tháp đích.

Số bước chuyển tất cả các đĩa là H(n) = 2 * H(n-1) + 1.

- Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học:

Bước 1: Giả sử công thức đúng với n-1, tức là H(n-1) = 2^(n-1) - 1

Bước 2: Chứng minh công thức đúng với n, tức là H(n) = 2^n - 1

Ta có:

H(n) = 2 * H(n-1) + 1 (theo công thức đề bài)

= 2 * (2^(n-1) - 1) + 1 (theo giả sử ở bước 1)

= 2^n - 2 + 1

= 2^n - 1

Vậy ta đã chứng minh được công thức đúng với mọi n.

Để tính H(64), ta áp dụng công thức đã chứng minh:

H(64) = 2^64 - 1

= 18446744073709551615

Vậy H(64) = 18446744073709551615 trùng với con số ở trên bài báo