Câu hỏi:

11/05/2023 259

Năm 1883, tại một số tỉnh thành của Việt Nam và tại Pháp xuất hiện một trò chơi được quảng cáo với tên “Tháp Hà Nội” (La tour d’Hanoi). Trò chơi này được bán rộng rãi và theo một tờ quảng cáo vào thời gian đó là sẽ trao giải hàng triệu francs cho ai có thể giải được tất cả các mức từ thấp đến cao nhất là 64 đĩa. Trong tờ rơi đó cũng đưa ra con số 18446744073709551615 bước chuyển cho trường hợp 64 đĩa và khuyến cáo rằng sẽ cần hàng tỉ năm để giải được trò chơi này. Trò chơi như sau: có ba cái cọc (ví dụ cọc 1, 2, 3) và n cái đĩa được xếp tại cọc 1 theo thứ tự to dần từ trên xuống. Yêu cầu chuyển n đĩa này sang cọc 3 với điều kiện là được dùng cọc 2 làm trung gian, mỗi lần chỉ được phép chuyển 1 đĩa và không cho phép đặt đĩa to chồng lên đĩa nhỏ.

Em hãy suy nghĩ và thử giải trò chơi trên với n = 1,

Hình 4.1. Tờ quảng cáo trò chơi “Tháp Hà Nội”, 1883

Xem lời giải

Câu hỏi trong đề: Chuyên đề Tin Học 11 KNTT Bài 4. Tháp Hà Nội có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3?

Với n = 2, ta có hai cái đĩa, ta sẽ di chuyển đĩa lớn nhất từ cọc 1 sang cọc trung gian 2, sau đó di chuyển đĩa nhỏ từ cọc 1 sang cọc đích 3, và cuối cùng di chuyển đĩa lớn từ cọc 2 sang cọc đích 3

Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4).

Xem đáp án

Lời giải

1. Di chuyển 3 đĩa từ cọc 1 sang cọc 3:

1.1 Di chuyển 2 đĩa từ cọc 1 sang cọc 2:

- Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

- Di chuyển 1 đĩa từ cọc 1 sang cọc 2.

- Di chuyển 1 đĩa từ cọc 3 sang cọc 2.

1.2. Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

1.3. Di chuyển 2 đĩa từ cọc 2 sang cọc 3:

- Di chuyển 1 đĩa từ cọc 2 sang cọc 1.

- Di chuyển 1 đĩa từ cọc 2 sang cọc 3

- Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

2. Di chuyển 1 đĩa từ cọc 1 sang cọc 2.

3. Di chuyển 3 đĩa từ cọc 3 sang cọc 2:

3.1 Di chuyển 2 đĩa từ cọc 3 sang cọc 1:

- Di chuyển 1 đĩa từ cọc 3 sang cọc 2. 3.1.2

- Di chuyển 1 đĩa từ cọc 3 sang cọc 1.

- Di chuyển 1 đĩa từ cọc 2 sang cọc 1.

3.2 Di chuyển 1 đĩa từ cọc 3 sang cọc 2.

3.3 Di chuyển 2 đĩa từ cọc 1 sang cọc 2:

- Di chuyển 1 đĩa từ cọc 1 sang cọc 3.

- Di chuyển 1 đĩa từ cọc 1 sang cọc 2.

- Di chuyển 1 đĩa từ cọc 3 sang cọc 2.

Vậy, tổng số bước để di chuyển 4 đĩa theo quy trình trên là:

- Di chuyển 3 đĩa từ cọc 1 sang cọc 2: 7 bước

- Di chuyển đĩa còn lại từ cọc 1 sang cọc 3: 1 bước

- Di chuyển 3 đĩa từ cọc 2 sang cọc 3: 7 bước

Vậy tổng số bước cần thiết để di chuyển 4 đĩa trong bài toán tháp Hà Nội là 15 bước.Top of Form

Câu 2

Hãy chứng minh công thức $H (n) = 2^{n} - 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.

Xem đáp án

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

Câu 3