Hãy chứng minh công thức trang 24 Chuyên đề Tin học 11

Hãy chứng minh công thức

Giải Chuyên đề Tin 11 Bài 4: Tháp Hà Nội - Kết nối tri thức

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

Lời giải bài tập Chuyên đề Tin 11 Bài 4: Tháp Hà Nội hay, chi tiết khác: