โปรแกรม 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