1. 題目理解與整體思路拆解1.1 漢諾塔基礎回顧漢諾塔問題對我來說算是老朋友了每次刷OJ碰到它都有種“去年今日此門中”的感覺。這道東華OJ-基礎題-128題面很直接給你一個經典的漢諾塔游戲三根柱子n個盤子要求輸出移動過程中的第m步操作。乍一聽好像比“輸出全部步驟”要簡單但真正動手做起來才會發現這里面藏著一個挺有意思的思維坎。先花30秒回憶一下漢諾塔的規則三根柱子A、B、C初始時所有盤子按從大到小的順序摞在A柱上一次只能移動一個盤子任何時候大盤子不能壓在小盤子上面目標是把整摞盤子挪到C柱。遞歸解法是每個學編程的人都會背的那套邏輯要把n個盤子從A挪到C先借助C把上面n-1個盤子從A挪到B再把最大的盤子從A挪到C最后借助A把n-1個盤子從B挪到C。這套遞歸邏輯本身不復雜代碼也就五六行。但東華OJ這道題的刁鉆之處在于它不問你“總共移動多少步”也不問你“完整移動序列是什么”而是直接指定一個m問第m步到底是“從哪根柱子到哪根柱子”。如果你老老實實生成完整移動序列再取第m項小數據量下完全沒問題但題目顯然希望你去思考能不能不生成完整序列直接定位到第m步1.2 第m步問題的本質我第一眼看到這個題的時候腦子里冒出來的想法是“這不就是遞歸模擬嗎”。順著這個思路寫代碼思路倒是很清晰定義一個遞歸函數參數帶一個計數器cnt每次執行一步移動就cnt加一當cnt等于m時輸出當前步驟。這種做法沒有任何思維難度本質上就是“模擬 剪枝”——即使理論上會遍歷很多無效分支但一旦找到第m步就立刻停止遞歸不會白白浪費大量時間。不過這道題既然標注了“難度中”還專門點明“遞歸”那就說明單純的模擬可能不是出題人想考察的重點。我后來仔細琢磨了一下這道題的核心考點其實有兩個層次第一層能不能熟練寫出漢諾塔的遞歸過程這是基本功。第二層能不能理解遞歸過程內在的數學結構也就是“第m步出現在哪個遞歸子問題里”。打個比方你在電影院找座位一種方式是拿著票從頭到尾走一遍把整排座位都數一遍才找到自己的位置另一種方式是直接看票上的排號和座位號穿過大廳拐個彎就到了。第m步的定位問題本質上就是在問你能不能直接從m的值推算出它對應的“排號和座位號”。如果理解了這一層這道題就有很多種完全不同的解法難度也各不相同。我會在下面詳細拆解這些路徑。無論你選哪一種思路都需要先對“漢諾塔遞歸過程的分層結構”有一個直覺上的把握這一層想通了代碼怎么寫都順手。2. 核心細節解析與遞歸原理2.1 遞歸的分治思想每一層都在拆子問題漢諾塔的遞歸代碼幾乎是教科書級的“分治思想”案例。我見過不少初學者代碼能背下來但問一句“為什么n-1個盤子要借助C柱挪到B柱”就卡住了。其實關鍵在于角色轉換柱子名字雖然是固定的但在每一層遞歸里它們的“身份”是動態變化的。考慮move(n, from, via, to)這個函數它的含義是把n個盤子從from借助via挪到to。分解步驟是先遞歸調用move(n-1, from, to, via)把上面n-1個盤子從from挪到via注意此時via是“目標”to是“中轉”然后執行一步實際操作把一個盤子從from挪到to最后遞歸調用move(n-1, via, from, to)把n-1個盤子從via挪到to此時from是“中轉”。這里面的關鍵點是整個n個盤子的移動過程只有中間那一步是“真實移動最大的盤子”其余n-1個盤子的移動全是遞歸子問題。也就是說一次完整的move(n)調用在全局視角看起來就是第一步到第moveTotal(n-1)步正在處理n-1個盤子的子問題 第moveTotal(n-1)1步最大的盤子從from到to 第moveTotal(n-1)2步到第moveTotal(n)步另一個n-1個盤子的子問題。其中moveTotal(k) 2^k - 1也就是k個盤子全部挪完所需的總步數。這個公式怎么來的遞推關系是T(1)1T(n)2*T(n-1)1解出來就是2^n-1。n3時是7步n4時是15步n64時是18446744073709551615步這個數量級的概念在后面會派上用場。2.2 移動次序的數學規律第m步落在哪一層還是以三個盤子為例完整的移動序列是第1步A→C1號盤最小的第2步A→B2號盤第3步C→B1號盤第4步A→C3號盤最大的第5步B→A1號盤第6步B→C2號盤第7步A→C1號盤注意第4步這是三盤漢諾塔中唯一一次挪動最大盤3號盤的步驟也是整個過程的“分水嶺”。它前面有3步后面有3步兩邊恰好都是兩盤漢諾塔的完整子序列。再往深了想n個盤子的漢諾塔第(2^(n-1))步一定是對最大盤的一次唯一移動。如果你要找的m恰好等于2^(n-1)那答案直接就出來了。如果m小于這個值說明第m步發生在“把n-1個盤子從A借助C挪到B”這個子問題里如果m大于這個值說明第m步發生在“把n-1個盤子從B借助A挪到C”這個子問題里。于是這個題就變成了一個“剝洋蔥”的過程每次根據m和目標柱子之間的關系判斷當前屬于哪個子問題然后進入下一層遞歸。每一層剝下去n減小1m要么保持不變m在左側子問題里要么減去左側子問題的總步數m在右側子問題里。剝到最底層時n等于1m必然等于1這時候就是那一層唯一的移動操作。這個思路的奇妙之處在于你根本不需要模擬盤子的實際移動過程也不需要記錄任何狀態。每一步的結果完全由遞歸的“路徑”決定而這個路徑又完全由m的數值決定。說白了m就是一張“地圖”上的路徑編碼。2.3 三種解法思路對比針對這道題我梳理出三種常見解法各有優劣適合不同場景解法核心思想時間復雜度優點缺點模擬剪枝法遞歸模擬完整過程輸出到第m步就停止O(2^n)最壞但實際剪枝思路直白不容易寫錯遞歸深度大時浪費較多計算二進制映射法根據m的二進制特征確定盤號與移動方向O(log m)常數級復雜度非常巧妙推導過程對新手不友好分治定位法利用moveTotal(n-1)判斷m屬于左/右側子問題逐層剝開O(n)邏輯清晰與遞歸思想貼合需要理解遞歸子問題結構我個人的建議是如果你是來學遞歸的一定要把第三種“分治定位法”吃透因為它和漢諾塔遞歸本身的思維方式完全一致理解了它你對遞歸的把握會上一個臺階。第二種“二進制映射法”作為擴展閱讀了解一下能開闊眼界但不必強行掌握。3. 實操過程與C實現3.1 基礎遞歸框架先寫出標準漢諾塔不管用哪種思路一個能正確輸出全部移動步驟的漢諾塔遞歸函數是基本功。下面這段C代碼是標準模板我有一個習慣每次用它之前先在紙上手推一遍n3的過程確認輸出的7步符合預期再往里面加邏輯。#include iostream using namespace std; // 將n個盤子從 from 借助 via 移動到 to void hanoi(int n, char from, char via, char to) { if (n 1) { cout from - to endl; return; } hanoi(n - 1, from, to, via); cout from - to endl; hanoi(n - 1, via, from, to); } int main() { int n; cin n; hanoi(n, A, B, C); return 0; }你注意看這里的三個字符參數‘A’、‘B’、‘C’在每一層遞歸中會不斷交換位置。第一行輸出“A - C”是把A柱最上面的小盤子直接挪到C柱這個我第一次寫的時候根本想不通——不是說好借助C把上面的盤子挪到B嗎怎么第一步又跑到C上去了這里其實是一個很容易踩的坑三根柱子是環形的不是線性的。當n等于3時move(3, A, B, C)的第一步是move(2, A, C, B)而這又拆成move(1, A, B, C)——把1號盤從A挪到C。整個過程完全符合規則只是“路徑”看起來很繞。這也是為什么我建議你運行一遍標準代碼把輸出結果和手工推導對照起來看比死記代碼要有用得多。3.2 求解第m步的完整代碼現在回到128題的核心。我采用“分治定位法”來寫最終版本。先放出完整代碼再逐步講解#include iostream using namespace std; int cnt; int n; long long m; // 計算k個盤子完成移動所需的總步數 long long totalSteps(int k) { return (1LL k) - 1; } // src: 源柱 via: 中轉柱 dst: 目標柱 k: 當前要移動的盤子數量 void findKthStep(int k, char src, char via, char dst, long long m) { if (k 1) { // 只剩一個盤子第m步必然就是它 cnt; if (cnt m) { cout src - dst endl; } return; } long long leftSteps totalSteps(k - 1); if (m leftSteps) { // 第m步在左側子問題把k-1個盤子從src借助dst挪到via findKthStep(k - 1, src, dst, via, m); } else if (m leftSteps 1) { // 第m步恰好是當前層最大盤子的移動 cnt leftSteps 1; cout src - dst endl; } else { // 第m步在右側子問題把k-1個盤子從via借助src挪到dst findKthStep(k - 1, via, src, dst, m - leftSteps - 1); } } int main() { cin n m; findKthStep(n, A, B, C, m); return 0; }這段代碼的核心邏輯全在findKthStep這個函數里。注意兩個細節第一我有一個多余但無害的cnt變量它實際上只在k1的分支里累加而在“m恰好等于leftSteps1”的分支里我直接把它賦值成leftSteps1這樣做是為了讓代碼在邏輯上有一個“位置”的概念方便你對照標準輸出理解。去掉cnt也不會影響正確性保留它純粹是為了可讀性。第二moveTotal用(1LL k) - 1來計算注意這里用了long long因為題目里n的上限可能到30甚至更大2的30次方是1073741824而2的40次方就超過一萬億了int根本扛不住。3.3 關鍵代碼詳解剝洋蔥的每一層我們來手動走一遍n3、m5這個case看看這段代碼到底怎么運作的。初始調用findKthStep(3, A, B, C, 5)。leftSteps 2^2 - 1 3。m55 leftSteps1即5 4所以m落在右側子問題。遞歸調用變為findKthStep(2, B, A, C, 5-3-11)。注意這里的變化源柱變成了B目標柱變成了C中轉柱變成了A而新的m是1。這意味著第5步這個全局步驟在以B為起點、C為終點的兩盤漢諾塔子問題里恰好是它的第1步。接著findKthStep(2, B, A, C, 1)。leftSteps 2^1 - 1 1。m1恰好等于leftSteps所以m落在左側子問題。遞歸調用變為findKthStep(1, B, C, A, 1)。再往下k1進入出口分支輸出“B - A”。與我們前面列出的完整序列一一對照第5步確實是B→A完美命中。你看整個過程代碼其實沒有真正“移動”任何盤子它只做了一件事根據m的大小判斷目標步驟在哪棵子樹上然后沿著這條路徑走到葉子節點。這就像查字典一樣不需要把整本字典背下來只需要根據拼音/部首一路翻到目標頁碼即可。我額外說一下cnt變量的作用。如果你把cnt刪掉然后把出口分支改成直接輸出代碼也沒問題。但我保留它的原因是調試的時候你可以把它打出來和標準漢諾塔的逐步輸出對照一旦發現某個分支的cnt值對不上很容易定位是哪一層左側/右側判斷出了問題。對于競賽代碼來說可調試性也是一個很重要的維度。3.4 補一個模擬剪枝版本的實現方便你對照如果你覺得上面的分治定位法有點繞或者你只是為了快速過題那么模擬剪枝法也能AC。這個版本的優點是代碼邏輯完全跟著遞歸走幾乎不可能因為思路問題寫錯。#include iostream using namespace std; int n; long long m; long long cnt 0; bool found false; void hanoi(int k, char src, char via, char dst) { if (found) return; if (k 1) { cnt; if (cnt m) { cout src - dst endl; found true; } return; } hanoi(k - 1, src, dst, via); if (found) return; cnt; if (cnt m) { cout src - dst endl; found true; return; } hanoi(k - 1, via, src, dst); } int main() { cin n m; hanoi(n, A, B, C); return 0; }這個版本的時間復雜度在最壞情況下是O(2^n)也就是當m接近總步數時前面的步驟全都要模擬一遍。好在找到了之后立刻剪枝返回不會模擬到結尾。對于OJ上通常給的n范圍比如n≤302^30大約是10億最壞情況下C跑這個量級會超時但如果n只有10幾這個版本完全夠用。所以這里有個策略判斷如果題目給了n的上限而且這個上限比較大就不建議用模擬版本。4. 常見問題與排查技巧實錄4.1 邊界條件m1和mtotalSteps這道題最容易翻車的地方就是邊界條件。我一開始寫分治定位法的時候m恰好等于leftSteps和恰好等于leftSteps1這兩個分支我總是搞混導致提交一次WA一次后來把所有情況列成一張表才徹底理清。假設當前遞歸層次是k那么整個move(k)過程分成三段區間含義操作1 ~ totalSteps(k-1)左側子問題進入findKthStep(k-1, src, dst, via, m)totalSteps(k-1)1當前層最大盤的唯一移動直接輸出src → dsttotalSteps(k-1)2 ~ totalSteps(k)右側子問題進入findKthStep(k-1, via, src, dst, m - totalSteps(k-1) - 1)所以在代碼里判斷順序很重要先判斷m是否≤leftSteps注意這里用小于等于把等號劃歸到左側再判斷m是否恰好等于leftSteps1最后是剩余情況。如果把第一段寫成m leftSteps那么mleftSteps時就會掉到第二個分支輸出結果就錯了。另一個容易踩坑的點是m的類型。題目說m是一個正整數但沒明確說范圍。我建議一律用long long接收因為int在32位系統上最大值約21億而漢諾塔的總步數在n31時就達到21億以上了。我之前在本地測試時用int沒有問題換了一組n35的數據就瞬間溢出輸出完全亂掉。這種坑屬于“平時遇不到遇到就是WA一整版”的類型。4.2 遞歸深度與性能分治定位法的遞歸深度其實只有n層每次遞歸做的是常數次操作所以時間復雜度是O(n)空間復雜度是O(n)遞歸棧。這一點比模擬法優秀太多。但要注意n層遞歸意味著遞歸棧的深度也在n如果n很大比如30或者40這個深度完全在C的安全范圍內不用擔心爆棧。真正需要擔心的是totalSteps(2)這種計算時用到的位運算。1LL k這種寫法在k63的時候會溢出但漢諾塔的n一般不會超過30所以實際場景中基本不會踩到這個坑。不過寫代碼時養成好習慣用long long且控制k的范圍總是沒錯的。我還遇到過一個問題在Windows的OJ系統上有些老舊編譯器不支持1LL這種寫法。如果你用Visual C 6.0那種古董環境建議改成(long long)1 k或者干脆寫一個循環計算冪值long long power2(int k) { long long res 1; for (int i 0; i k; i) res * 2; return res - 1; }4.3 調試技巧用標準序列驗證你的輸出我每次寫完這道題不會直接交OJ而是先在本地跑一個“全量模式”來驗證寫一個普通的漢諾塔遞歸函數輸出完整序列然后再調用findKthStep分別查詢第1步、第2步……直到最后一步比較兩個函數輸出的是否完全一致。這一招幫我抓到了無數的分支判斷錯誤。具體做法很簡單在main函數里加一個循環for (long long i 1; i totalSteps(n); i)每次調用findKthStep并把輸出重定向到一個文件里再用標準遞歸函數生成完整序列兩者逐行diff。如果全對基本可以放心交OJ。我第一次寫這個驗證腳本的時候真的發現了一個很隱蔽的問題——在k1的出口分支里我忘了把cnt加一導致第m步輸出總是比標準序列早了一步。另外我再分享一個我常用的“單步觀察”技巧如果你想深入理解遞歸的走法可以在findKthStep的入口處加一行cerr輸出打印當前k、src、via、dst和m的值。運行一次n3的case看看輸出的日志順序你會直觀地看到遞歸是如何一層一層“剝”下去的。這個技巧比單步調試更快也更容易建立直覺。4.4 常見報錯與解決方案速查現象可能原因解決方案小數據通過大數據WAint溢出全部改用long long特別是m和totalSteps輸出多了前綴步數未正確剪枝/遞歸把所有步驟都打出來了檢查是否在找到目標步后立刻返回避免后續遞歸輸出為空m大于總步數題目保證m合法但可在代碼入口處加一個if (m (1LLn)-1) return 0;防御在k1分支輸出錯誤cnt更新順序不對先cnt再比較或者直接輸出src→dst不依賴cnt左側/右側子問題判斷混亂對totalSteps(k-1)的區間理解不清晰手工推導n3的完整序列用表格方式標注每個步驟屬于哪一段5. 從這道題延伸出去的思考5.1 為什么不建議背模板代碼我發現很多同學刷OJ時有個習慣碰到遞歸題就把漢諾塔模板背下來換了個問法就不知道怎么改。這道題就是個很好的反例——同樣是漢諾塔如果你只是機械地背下了“三步走”的模板那你大概只能寫出模擬剪枝法但如果你理解了“每層遞歸的三個區間”你就能自然地想到分治定位法。我始終覺得刷題不是為了AC那個綠色的對勾而是為了建立一種“問題結構的直覺”。漢諾塔這個模型非常有意思它其實是一種極其工整的遞歸結構整體問題分解成兩個同構子問題加一個常數操作這正是分治思想最純粹的體現。理解了這道題像快速排序、歸并排序、二叉樹遍歷這類“遞歸套遞歸”的算法你再看就會有“不過如此”的感覺。5.2 二進制映射法的彩蛋最后我再提一嘴前面說過的二進制映射法它算是這道題的一個彩蛋。漢諾塔問題和二進制的關聯非常經典n個盤子的漢諾塔總步數是2^n-1而每一步移動的盤號恰好等于“當前步數m的二進制表示中從最低位開始第一個1的位數”。比如m5二進制是101從最低位往上數第0位是1所以這一步動的是1號盤最小盤。再比如m6二進制是110第0位是0、第1位是1所以動的是2號盤。這個規律我第一次知道的時候真的被驚艷到了。但我要提醒你這個規律雖然優美推導起來卻需要花不少功夫而且和“借助中轉柱”的過程中盤子的移動方向也有一套循環規律。對我來說這種發現屬于“拿到AC之后錦上添花的彩蛋”不建議你在比賽時花時間現場推導。如果你感興趣可以在一個n4的完整序列上手動標記每個步驟的盤號和方向你會看到那個規律像鐘表一樣精確地循環著。這也是我特別喜歡漢諾塔這道題的原因——它不只是一道OJ題更像是一個藏著數學玩具的小盒子。