编辑代码

#include <iostream>
#include <string>

using namespace std;

// 将编号为n的盘从源柱子挪到目标柱子上
int move(int no, string src, string dst){
    int count = 1;
    cout << "Move " << no << " from " << src << " to " << dst << endl;
    return count;
}

// n表示有几个盘子
// src表示源柱子
// tmp表示辅助柱子
// dst表示目标柱子
// 返回值表示挪动了多少步
int hanoi(unsigned int n, string src, string tmp, string dst) {
    int count = 0;
    // 0表示没有挪动
    if (n == 0) {
        return 0;
    }

    // 终止条件，只有一共盘子，直接从源挪动到目的
    if (n == 1) {
        count += move(n, src, dst);
    }
    else {
        // 将n-1个盘子通过dst柱子从src柱子挪动到tmp柱子上
        count += hanoi(n-1, src, dst, tmp);
        // 将第n个盘子从src柱子挪动到dst柱子上
        count += move(n, src, dst);
        // 将n-1个盘子通过src柱子从tmp柱子挪动到dst柱子上
        count += hanoi(n-1, tmp, src, dst);
    }
    return count;
}

int main()
{
    unsigned int n = 0;
    cin >> n;
    int count = hanoi(n, "S", "T", "D");
    cout << "I moved " << count << " steps." << endl;
}