苏旭晖，网名 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都可以轻易写出来。
SQL解答
递归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的无穷魅力，参与定期的线上和线下技术分享，请加入我们的“云和恩墨大讲堂”！
本文出自数据和云公众号，原文链接