이 C++ 프로그램은 바이너리 값을 사용하여 하노이 타워 문제에 대한 솔루션을 표시합니다.
각 디스크에 대해 하나의 이진수가 있습니다.
최상위 비트는 가장 큰 디스크를 나타냅니다. 값 0은 가장 큰 디스크가 초기 페그에 있음을 나타내고 1은 최종 페그에 있음을 나타냅니다.
비트열은 왼쪽에서 오른쪽으로 읽혀지며 각 비트는 해당 디스크의 위치를 결정하는 데 사용할 수 있습니다.
비트가 이전 것과 동일한 값을 갖는 경우 해당 디스크는 동일한 페그의 이전 디스크 위에 쌓입니다.
다르면 해당 디스크가 이전 디스크의 왼쪽 또는 오른쪽 한 위치에 있음을 의미합니다.
알고리즘
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
예시
#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";
} 출력
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