---
title: "普通汉诺塔问题"
created: 2025-11-28
tags:
  - 算法
---

# 普通汉诺塔问题

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

```cpp
#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-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/递归与递推模型/递归/带分数|带分数]]