Chương trình C ++ này hiển thị lời giải cho vấn đề Tháp Hà Nội bằng cách sử dụng giá trị nhị phân.
Có một chữ số nhị phân cho mỗi đĩa.
Bit quan trọng nhất đại diện cho đĩa lớn nhất. Giá trị 0 cho biết rằng đĩa lớn nhất đang ở trên chốt ban đầu, trong khi giá trị 1 cho biết rằng nó đang ở chốt cuối cùng.
Chuỗi bit được đọc từ trái sang phải và mỗi bit có thể được sử dụng để xác định vị trí của đĩa tương ứng.
Đĩa tương ứng được xếp chồng lên đĩa trước đó trên cùng một chốt nếu một bit có cùng giá trị với đĩa trước đó.
Nếu nó khác có nghĩa là đĩa tương ứng nằm ở một vị trí bên trái hoặc bên phải của đĩa trước đó.
Thuật toán
Begin Take the number of disk n as input. Declare n and a. Make a for loop a = 1 to (1<<n) – 1 // Here, (a & a – 1) = bitwise AND with a and a – 1. (a | a – 1) = bitwise OR with a and a – 1. Here % means modulus operator. // Print the result indicating that moving disks from peg number (a & a – 1) % 3 to peg number ((a | a – 1) + 1) % 3 End
Ví dụ
#include<iostream>
using namespace std;
int main() {
int n, a;
cout<<"\nEnter the no of Disks: ";
cin>>n;
for (a = 1; a < (1 << n); a++) {
cout<<"\nDisk Move from Peg "<<(a&a-1)%3 <<" to Peg "<<((a|a-1)+1)%3;
}
cout<<"\n";
} Đầu ra
Enter the no of Disks: 3 Disk Move from Peg 0 to Peg 2 Disk Move from Peg 0 to Peg 1 Disk Move from Peg 2 to Peg 1 Disk Move from Peg 0 to Peg 2 Disk Move from Peg 1 to Peg 0 Disk Move from Peg 1 to Peg 2 Disk Move from Peg 0 to Peg 2