653
樂在其中：無所不能用SQL挑戰經典遊戲漢諾塔
蘇旭暉，網名 newkid
ITPUB開發版資深版主，SQL開發專家
編輯手記：感謝蘇旭暉先生授權我們獨家轉載其係列精品文章，也歡迎大家向“Oracle”社區投稿。
SQL是一門非常靈活的語言，專家們用其挑戰一切看似不可能。
漢諾塔是源自印度神話裏的玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按大小順序摞著64片黃金圓盤。
大梵天命令婆羅門把圓盤從下麵開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。
傳說
在印度，有這麼一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裏，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下麵的法則移動這些金片：一次隻移動一片，不管在哪根針上，小片必須在大片上麵。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。
題目要求：用SQL找出最少移動次數，並且給出一種移法。
例子：3個圓盤
輸入：N=圓盤個數
VAR N NUMBER;
EXEC :N := 3;
輸出：
7
1->2,1->3,2->3,1->2,3->1,3->2,1->2
每個步驟表示將一個柱子上的最上麵一個圓盤移到另一個柱子。比如1->2 就是將1號柱最上方的圓盤放到2號柱的最上方。
思路分析
假設有N個盤，最底下的N號盤在移動的時候，目標的柱子一定是空的。所以所有的其他N-1個盤子必定全部在另一柱子上。
把N號盤移過去之後，N-1要疊加到這個盤上麵，和剛才移動N-1個盤子的方法是一樣的，隻不過柱子的編號不同。
用遞歸SQL和MODEL都可以輕易寫出來。
遞歸WITH:
WITH h(n,path,ended) AS (
SELECT 1,CAST('1->2' AS VARCHAR2(2000)),2 FROM DUAL
UNION ALL
SELECT n+1
,path
||',1->'||DECODE(ended,2,3,2)||','
||TRANSLATE(path,'123',DECODE(ended,2,'231','312'))
,DECODE(ended,2,3,2)
FROM h
WHERE n<:N
)
SELECT POWER(2,n)-1 AS steps,path FROM h WHERE n=:N;
MODEL解法：
SELECT POWER(2,:N)-1 AS steps,path
FROM (SELECT CAST('1->2' AS VARCHAR2(2000)) AS path,2 AS ended FROM DUAL)
MODEL RETURN UPDATED ROWS
DIMENSION BY (1 n)
MEASURES (path,ended)
RULES ITERATE(100) UNTIL(ITERATION_NUMBER=:N-2)
(
path[1]=path[1]
||',1->'||DECODE(ended[1],2,3,2)||','
||TRANSLATE(path[1],'123',DECODE(ended[1],2,'231','312')),
ended[1]=DECODE(ended[1],2,3,2)
)
;
大家是否已經能夠體會SQL的無窮魅力，參與定期的線上和線下技術分享，請加入我們的“雲和恩墨大講堂”！
本文出自數據和雲公眾號，原文鏈接
最後更新：2017-07-17 18:03:59