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

Tháp Hà Nội

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

Bài toán tháp Hà Nội là một bài toán truyền thống trong lĩnh vực toán học. Bài toán này yêu cầu di chuyển một số lượng đĩa từ cột A sang cột C, với điều kiện mỗi lần chỉ di chuyển một đĩa và không được đặt đĩa lớn hơn lên đĩa nhỏ.

Bài toán này có thể được giải quyết bằng đệ quy. Với n đĩa, ta có thể chia bài toán thành ba bước:

  1. Di chuyển n-1 đĩa từ cột A sang cột B, sử dụng cột C làm cột trung gian.
  2. Di chuyển đĩa còn lại từ cột A sang cột C.
  3. Di chuyển n-1 đĩa từ cột B sang cột C, sử dụng cột A làm cột trung gian.

Với mỗi bước, ta lại lặp lại cách giải quyết bài toán với số đĩa là n-1 cho đến khi số đĩa còn lại là 1.

Dưới đây là một ví dụ giải bài toán tháp Hà Nội với 3 đĩa:

Bước 1: Di chuyển 2 đĩa từ cột A sang cột B, sử dụng cột C làm cột trung gian.

  • Di chuyển đĩa 1 từ cột A sang cột C.
  • Di chuyển đĩa 2 từ cột A sang cột B.
  • Di chuyển đĩa 1 từ cột C sang cột B.

Bước 2: Di chuyển đĩa 3 từ cột A sang cột C.

Bước 3: Di chuyển 2 đĩa từ cột B sang cột C, sử dụng cột A làm cột trung gian.

  • Di chuyển đĩa 1 từ cột B sang cột A.
  • Di chuyển đĩa 2 từ cột B sang cột C.
  • Di chuyển đĩa 1 từ cột A sang cột C.

Với ba đĩa, ta cần thực hiện 2^3 – 1 = 7 bước di chuyển.

Cài đặt bài toán tháp Hà Nội với Python

def thap_ha_noi(n, cot_nguon, cot_dich, cot_trung_gian):
    if n == 1:
        print("Chuyển đĩa 1 từ cột", cot_nguon, "sáng cột", cot_dich)
        return
    thap_ha_noi(n-1, cot_nguon, cot_trung_gian, cot_dich)
    print("Chuyển đĩa", n, "từ cột", cot_nguon, "sang cột", cot_dich)
    thap_ha_noi(n-1, cot_trung_gian, cot_dich, cot_nguon)

# Ví dụ sử dụng hàm thap_ha_noi với 3 đĩa
n = 3
thap_ha_noi(n, 'A', 'C', 'B')

Cài đặt bài toán tháp Hà Nội với C++

#include <iostream>
using namespace std;

void thapHanoi(int n, char cot_nguon, char cot_dich, char cot_trung_gian)
{
    if (n == 1)
    {
        cout << "Chuyen dia 1 tu cot " << cot_nguon << " sang cot " << cot_dich << endl;
        return;
    }
    thapHanoi(n - 1, cot_nguon, cot_trung_gian, cot_dich);
    cout << "Chuyen dia " << n << " tu cot " << cot_nguon << " sang cot " << cot_dich << endl;
    thapHanoi(n - 1, cot_trung_gian, cot_dich, cot_nguon);
}

// Ví dụ sử dụng hàm thapHanoi với 3 đĩa
int main()
{
    int n = 3;
    thapHanoi(n, 'A', 'C', 'B');
    return 0;
}

Cài đặt bài toán tháp Hà Nội với Pascal

program thap_hanoi;

procedure thapHanoi(n: integer; cot_nguon, cot_dich, cot_trung_gian: char);
begin
  if n = 1 then
  begin
    writeln('Chuyen dia 1 tu cot ', cot_nguon, ' sang cot ', cot_dich);
    exit;
  end;
  thapHanoi(n - 1, cot_nguon, cot_trung_gian, cot_dich);
  writeln('Chuyen dia ', n, ' tu cot ', cot_nguon, ' sang cot ', cot_dich);
  thapHanoi(n - 1, cot_trung_gian, cot_dich, cot_nguon);
end;

// Ví dụ sử dụng hàm thapHanoi với 3 đĩa
begin
  thapHanoi(3, 'A', 'C', 'B');
end.

Kết quả thực hiện bài toán

Chuyen dia 1 tu cot A sang cot C
Chuyen dia 2 tu cot A sang cot B
Chuyen dia 1 tu cot C sang cot B
Chuyen dia 3 tu cot A sang cot C
Chuyen dia 1 tu cot B sang cot A
Chuyen dia 2 tu cot B sang cot C
Chuyen dia 1 tu cot A sang cot C

Trong đó, A, B, C lần lượt là tên của các cột, và số thứ tự đĩa được di chuyển từ cột nguồn (cot_nguon) đến cột đích (cot_dich).

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *