使用二進位制值解決漢諾塔問題的 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 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始