普通汉诺塔问题

即3根柱子时 有n个盘子 移动的总次数是 \(2^n−1\)

#include <iostream>

using namespace std;

int moveCount;

int n;

void TowerOfHanoi(int n, char source, char destination, char auxiliary) {

    // 当只有一个盘子时，直接移动到目标塔，这是递归的基本情况

    if (n == 1) {

        // 直接移动一个盘子到目标塔，移动次数加一

        moveCount++;

        return;

    }

    // 递归移动上面n-1个盘子到辅助塔，以目标塔作为中转

    TowerOfHanoi(n - 1, source, auxiliary, destination);

    moveCount++; // 移动最底下的盘子到目标塔，移动次数加一

     // 再次递归移动上面n-1个盘子从辅助塔到目标塔，以原始塔作为中转

    TowerOfHanoi(n - 1, auxiliary, destination, source);

}

int main() {

    for(n=1;n<=12;n++){

        moveCount=0;

        TowerOfHanoi(n, 'A', 'C', 'B');

        cout<<moveCount<<endl;

    }

    return 0;

}

/*

1

3

7

15

31

63

127

255

511

1023

2047

4095

*/

⬅️ 奇怪的汉诺塔 🏠 00-刷题理模型 ➡️ 带分数