乐在其中:无所不能用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都可以轻易写出来。

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的无穷魅力,参与定期的线上和线下技术分享,请加入我们的“云和恩墨大讲堂”!

近期文章

成就卓越:云和恩墨大讲堂期刊第三期

新年贺礼:云和恩墨大讲堂期刊第二期

删繁就简-云和恩墨的一道面试题解析

用SQL解一道数学题:Gauss和Poincare

新年贺礼:云和恩墨大讲堂期刊发行

2015 Oracle 十大热门文章精选

Oracle 12c ASM 防火防盗新特性揭秘

DBA入门之路:学习与进阶之经验谈

DBA入门之路:关于日常工作的建议

业务架构

电子渠道(网络销售)分析系统、数据治理

IT基础架构

分布式存储解决方案 | zData一体机 | 容灾环境建设

数据架构

Oracle DB2 MySQL NoSQL

专项服务:架构/安全/容灾/优化/整合/升级/迁移

运维服务:运维服务 代维服务

人才培养:个人认证 企业内训

软件产品:SQL审核、监控、数据恢复

应用架构

应用软件和中间件:数据建模 | SQL审核和优化 | 中间件服务

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2016-03-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang语言社区--【棋牌麻将开发一】四川麻将规则和番数计算

成都麻将简介 成都麻将最大的特点在于缺一门方可和牌,此外在成都麻将中还有类似上海麻将中的“喇”的概念,即有一个番数最高限制,称为“极品”。此外成都麻将还...

4076
来自专栏ImportSource

跟我扯分布式事务之Try-Confirm-Cancel

事情还得从事务说起。我说事情总是喜欢从字面意义说起。那事务究竟是什么意思呢?得从它的英文说起:Transaction。

952
来自专栏SAP最佳业务实践

SAP最佳业务实践:半成品的计划与处理(234)-4成品生产1

image.png 创建产成品的销售订单输入销售订单条目 (109) 客户需要物料 F234-1 或 F234-2 或这两种物料,并将这一需求发送给工厂 100...

2925
来自专栏FSociety

爬了链家二手房数据来告诉你深圳房价到底多恐怖!

需要说明一点,我们采集的数据中未包含大鹏新区/光明新区,因为这两个新区房源信息较少,加上pyecharts里面深圳的行政区也未包含这两个新区,所以没将这两个区的...

1522
来自专栏互联网杂技

有趣的算法、逻辑面试题

1、A、B两人分别在两座岛上。B生病了,A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西,但东西只能放在箱子里。只要箱子没被上锁,C...

2886
来自专栏腾讯技术工程官方号的专栏

支撑起腾讯公司计费业务的TDSQL(附PPT)

作者介绍:bluesea,腾讯金融云专家工程师,从事分布式数据库TDSQL研发工作。出版著作:《数据库查询优化器的艺术 原理解析与SQL性能优化》、《数据库事...

4738
来自专栏域名资讯

域名peza.com结拍 持有者身份未明

4字母入手成本低,但却具有一定的增长空间,因此受到投资人的青睐。这不,一域名peza.com最近传出交易的消息。

1916
来自专栏币圈

罗爷说币:7月11号主流币行情分析

将7.09日加仓头寸止损,并且于472美元将底仓降低至25%,于455-475进行浮动区间日内套利,仓位为25%-40%。

1414
来自专栏ml

NYOJ------汉诺塔(一)

汉诺塔(一) 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的...

1783
来自专栏机器人网

涨知识!原子是如何被发现,并进行核能利用的?

原子是一种非常神奇的粒子,它拥有复杂的结构,自然而然会发生神奇的变化。整个世界都是由大量微小的原子组成,原子又是由中子、质子和电子组成。两百多年来,科学家为了证...

2514

扫码关注云+社区