移動次數:0
目前移動:-
每柱由下而上堆疊盤子,盤寬與編號成正比(愈大盤愈寬);紅框標示剛移入的盤。
碰到一個大問題,如果它能拆成「形狀一樣、只是小一號」的問題,那就可以丟給「縮小版的自己」去解——這就是遞迴,像俄羅斯娃娃一層套一層,拆到最小那顆能直接回答,再一路往回把答案組起來。這頁用三個經典題示範遞迴的三種常見長相:河內塔只管把問題拆小、最大子陣列拆完還得把兩半的結果合併、N 皇后走不通就退回上一步換個走法重試。下面你可以一步步看它們怎麼往下拆、又怎麼往回收。
三個經典問題示範遞迴的三種典型用法:
將 n 個盤子從來源柱 A 移到目標柱 C,可借助輔助柱 B:先遞迴把上方 n-1 個盤子從 A 移到 B(借助 C), 再把第 n 個(最大)盤直接從 A 移到 C,最後遞迴把 n-1 個盤子從 B 移到 C(借助 A)。n=1 時直接移動,不再遞迴。
將陣列一分為二,答案要嘛完全落在左半、要嘛完全落在右半、要嘛跨越中點;跨中情形需從中點分別向左、向右各自累加取最大值再相加。 區段長度為 1 時直接回傳該元素(base case)。
逐列嘗試每一欄放皇后:若與已放置的皇后同欄或同對角線衝突,立即剪枝、跳過此欄,不再往下遞迴; 安全則放置並遞迴下一列,回溯時移除該皇后再嘗試下一欄。放滿 n 列即為一組解。