題目鏈接

????????面試題 08.06. 漢諾塔問題

題目描述

題目解析

1. 當只有一個盤子時：直接從A柱放到C柱即可。
2. 當有兩個盤子時：將A柱第一個盤子先放到B柱，再將A柱第二個盤子放到C柱，最后將B柱上的盤子放到C柱子。
3. 當有3個盤子時：先A柱上面兩個盤子借助C柱放到B柱子，再將A柱上最后一個盤子放入C柱，最后將B柱子上的盤子借助A柱放入C柱。
4. 當有n個盤子時：先A柱上n-1個盤子借助C柱放到B柱子，再將A柱上最后一個盤子放入C柱，最后將B柱子上的盤子借助A柱放入C柱。

解法1：純遞歸

// 方法一：純遞歸
// my_hanota：將A柱子中最上面的n個盤子經由B移動到C中；也就是將A中后n個元素經由B移動到C中。
void my_hanota(int n, vector<int>& A, vector<int>& B, vector<int>& C) {if (n == 1){C.push_back(A.back());  A.pop_back();return;}my_hanota(n - 1, A, C, B);C.push_back(A.back());  A.pop_back();my_hanota(n - 1, B, A, C);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {int n = A.size();my_hanota(n, A, B, C);
}

解法2：體會參數的遞歸過程

// 方法二：強迫使用一個參數，簡單換一種遞歸思考方式
// m參數用于體驗遞歸過程
// 用m表示最大的盤子在數組中的位置
void my_hanota(int n, int m, vector<int>& A, vector<int>& B, vector<int>& C)
{if (n == 1){C[m] = A[m];return;}my_hanota(n - 1, m + 1, A, C, B);//將A中后n-1個元素經由C放入BC[m] = A[m];my_hanota(n - 1, m + 1, B, A, C);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {int n = A.size();B.resize(n);C.resize(n);int m = 0;my_hanota(n, 0, A, B, C);
}