Chương trình C++ giải Tháp Hà Nội bằng phương pháp nhị phân

Giải bài toán Tháp Hà Nội sử dụng biểu diễn nhị phân. Mỗi đĩa tương ứng một bit: bit 0 = cọc ban đầu, bit 1 = cọc đích. Di chuyển được xác định bởi các phép toán bitwise.

Thuật toán

Bắt đầu
  Nhập số đĩa n.
  Với a từ 1 đến (1<<n) - 1:
    Cọc nguồn = (a & (a-1)) % 3
    Cọc đích = ((a | (a-1)) + 1) % 3
    In: "Di chuyển từ cọc [nguồn] sang cọc [đích]"
Kết thúc

Ví dụ mã nguồn

#include <iostream>
using namespace std;

int main() {
    int n, a;
    cout << "So dia: "; cin >> n;
    for (a = 1; a < (1 << n); a++) {
        cout << "Di chuyen tu coc " << (a & (a-1)) % 3
             << " sang coc " << ((a | (a-1)) + 1) % 3 << "\n";
    }
    return 0;
}

Đầu ra (n=3)

Di chuyen tu coc 0 sang coc 2
Di chuyen tu coc 0 sang coc 1
Di chuyen tu coc 2 sang coc 1
Di chuyen tu coc 0 sang coc 2
Di chuyen tu coc 1 sang coc 0
Di chuyen tu coc 1 sang coc 2
Di chuyen tu coc 0 sang coc 2