在經(jīng)典漢諾塔問題中，有 3 根柱子及 N 個不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。一開始，所有盤子自上而下按升序依次套在第一根柱子上(即每一個盤子只能放在更大的盤子上面)。移動圓盤時受到以下限制:
??(1) 每次只能移動一個盤子;
??(2) 盤子只能從柱子頂端滑出移到下一根柱子;
??(3) 盤子只能疊在比它大的盤子上。
??請編寫程序，用棧將所有盤子從第一根柱子移到最后一根柱子。
??你需要原地修改棧。
示例1:
輸入： A = [2, 1, 0], B = [], C = []
輸出： C = [2, 1, 0]
示例2:
輸入： A = [1, 0], B = [], C = []
輸出： C = [1, 0]
提示:
A中盤子的數(shù)目不大于14個。
??點(diǎn)擊此處跳轉(zhuǎn)題目。
二、C# 題解
??經(jīng)典的漢諾塔問題，使用遞歸求解：
public class Solution {
? ? public void Hanota(IList<int> A, IList<int> B, IList<int> C) {
? ? ? ? Partition(A.Count, A, B, C);
? ? }
? ? public void Partition(int n, IList<int> A, IList<int> B, IList<int> C) {
? ? ? ? if (n == 1) { // 只剩一個盤子，遞歸出口
? ? ? ? ? ? C.Add(A[^1]);
? ? ? ? ? ? A.RemoveAt(A.Count - 1);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? Partition(n - 1, A, C, B); // 將 A 上方 n - 1 個盤子先移動到 B
? ? ? ? C.Add(A[^1]);? ? ? ? ? ? ? // A 最下方的盤子移到 C
? ? ? ? A.RemoveAt(A.Count - 1);
? ? ? ? Partition(n - 1, B, A, C); // 剩余 n - 1 個盤子從 B 移動到 C
