Câu hỏi:

11/05/2023 261

Mô tả lời giải bài toán với n = 1, 2, 3 nếu yêu cầu là di chuyển các đĩa từ cọc 1 sang cọc 2 (cọc 3 là cọc trung gian).

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

* Giải trò chơi Tháp Hà Nội với n=1:

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

* Giải trò chơi Tháp Hà Nội với n=2:

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

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

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

* Giải trò chơi Tháp Hà Nội với n=3:

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

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

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

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

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

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

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

Nhận xét: Với n = 1, chỉ cần di chuyển một đĩa từ cọc 1 sang cọc 2. Với n = 2, ta thực hiện ba lần di chuyển. Với n = 3, ta thực hiện bảy lần di chuyển. Với mỗi tăng thêm một đĩa, số lần di chuyển tăng lên gấp đôi và cộng thêm một.

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