使用二进制值解决汉诺塔问题的 C++ 程序

此 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

思美塔·卡普斯

更新于：30-07-2019

276 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始