神马?SQL竟然可以解脑筋急转弯的题目?
我在很多公开演讲中都明目张胆的羡慕过一类人,他们把SQL当做艺术,把旁人眼中的枯燥演绎成经典,云和恩墨专家团队中的杨廷琨、罗海雄就都是这样的SQL专家。
今天,这个周六,杨长老正在恩墨学院开坛授课,讲授他的SQL哲学,我在次整理一下他曾经分享过的小案例,让大家一起感受一下SQL的魅力。
用SQL解海盗分金的问题
热爱Oracle技术的专家们,他们的世界就是这样的:见猎心喜,遇难而技痒。
崔华老师曾经在朋友圈贴了一个问题,这是一个经济学中一个经典问题-海盗分金:
大家可以思考一下,应该如何去解决这个问题。
有人给出的第一个答案是这样的(我不知道是不是书上给出的答案):
答案是——第一个人会说:"100两金子全归我!",而且这个方案一定会被一半以上的人同意,这个人不会被杀掉。
整个分析的思路是如下这样:
我们从抓到最后一个阄的人开始考虑。对于这个人来说,他知道,当轮到他提方案的时候,其他人都已经死掉了,金子将全是他一个人的。所以,他利益最大化行为便是,不管前边谁,包括第一个人,提了任何方案,他都一概摇头,不同意。
再看第四个人,他知道,不管自己提出什么方案,第五个人都不会同意,都会被杀掉,所以,他的利益最大化行为是,尽量不要轮到自己提方案。所以,不管第一个人提了怎样的方案,他都会表示同意。
第三个人,知道第四和第五个人的选择策略,所以,他的利益最大化的方案是100两金子全归自己。这个方案,因为自己和第四个人同意,超过了此时的一半以上的人的同意,可以行得通,所以,不管第一个人提出什么样的方案,第三个人都会反对。
第二个人,知道自己提什么方案,第三个人、第五个人都将反对,一旦轮到自己提,自己就死定了,所以,他会同意第一个人提出的任何方案,这是他的利益最大化行为。
所以,不管第一个人提出怎样的方案,第二个人与第四个人都会同意,加上第一个人自己的票,就是三票,一半以上,可以通过。
既然任何方案都可以通过,而第一个人又要追求自己利益的最大化,所以,他的方案是:100两金子全归自己。
这个逆向推导法是一个很好的思路,但是是有瑕疵的,其结果也是错误的。
每个人在这里不仅要考虑自己的生死,还要考虑利益最大化;
所以他们有机会在表达意见时兼顾获得自己的利益的可能;
依据以上原则,第五个人不一定一直投反对票,因为他可能会一无所获;
第四者完全可以从第二个的分配中获得更佳的回报,他也可以不赞成第一个人的“独吞”方案。
杨长老看到问题就忍不住手痒,马上动手用SQL写出了一个简单的解答。老杨说:一时手痒写了一小段实现非常丑陋的代码,算是抛砖引玉吧。如果你有其他实现方法,欢迎投简历给我 ( eygle@enmotech.com )。
为了保持原汁原味,就截取了杨长老的图;当然这个问题还有一个可能解,大家可以求证一下,欢迎反馈你的SQL给我们。
用SQL为解析一道数学题
Oracle的SQL语句功能强大,它可以实现一些你意想不到的功能。比如下面这个数学问题,如果使用常规的数学方法进行手工分析将会十分麻烦,而使用SQL来求解则要简单得多。且看杨廷琨用一个SQL解析一道数学难题。
这是一个流传已久的故事:
Gauss和Poincare在天堂相遇了,上帝说:你们都是人间最伟大的数学家,那我来出道题考考你们谁更聪明。我在左手写一个大于1小于100的数,在右手同样写一个大于1小于100的数,然后把他们的和写在Gauss手上,把积写在Poincare手上,看看你们能不能猜出这两个数字是几。
Gauss看了手上的数字,说:“我不知道这两个数字是几,可我保证Poincare也不知道。”
Poincare看了手上的数字,说:“我原来的确不知道那两个数字是几,可我现在知道了。”
Gauss说:“那我也知道了。”
问题:那两个数字是几?
以下是来自维基百科关于两位数学家的简要介绍
约翰·卡尔·弗里德里希·高斯(英语:Gauss;1777年4月30日-1855年2月23日), 德国著名数学家、物理学家、天文学家、大地测量学家。高斯被认为是历史上最重要的数学家之一,并有“数学王子”的美誉。 高斯独立发现了二项式定理的一般形式、数论上的“二次互反律”、素数定理、及算术-几何平均数。1796年,19岁的高斯得到了一个数学史上极重要的结果,就是《正十七边形尺规作图之理论与方法》。
儒勒·昂利·庞加莱(法语:Jules Henri Poincaré,1854年4月29日—1912年7月17日),法国最伟大的数学家之一,理论科学家和科学哲学家。庞加莱被公认是19世纪后和20世纪初的领袖数学家,是继高斯之后对于数学及其应用具有全面知识的最后一个人。 他对数学,数学物理,和天体力学做出了很多创造性的基础性的贡献。
这道题给出的已知条件十分隐蔽,首先来分析一下已知条件。
根据题意,最终所求的是两个数字,而这两个数字的范围是在1和100之间。题目中明确说明的条件仅此而已,剩下的条件就要依靠分析才能得出了。
对于Gauss来说他知道两个数之和,而不知道两个数的积,但是Gauss却肯定的说,他保证Poincare也不知道这两个数是什么。这句话就很有深意。
举个例子,如果两个数分别是3和7,那么这两个数之积就是21。由于这两个数都是大于1的,因此两个数乘积为21的只有3和7这一种可能。如果Poincare手中的值是21,那么Poincare肯定可以确定这两个数是什么,因此对于Gauss而言,手中的值肯定不可能是10(3和7这两个数的和)。如果这个值是10,那么这两个数就有可能是3和7,而3和7的乘积又是唯一的,所以Gauss就无法确定Poincare也不知道结果。
当然这只是举了一个例子,如果归纳一下就是说,对于Gauss而言,所有满足相加与手中数值相等的两个数,它们的积都不是唯一的。只有满足这个条件,他才能确认Poincare不知道这两个数是什么。
对于Poincare来说,他开始并不知道两个数是什么,但是Gauss说出了他的推断之后,Poincare居然知道了这两个数是什么。这说明由于Gauss刚才的推断所排除的一些数值组合后,使得Poincare手中的积可以唯一确定这两个数值了。
随后Gauss说他也知道了,意味着根据Poincare能够确认这两个数的信息,Gauss也可以唯一的确定这两个数了。
题目已经分析完了,那么如何用SQL来求解呢,为了便于描述,这里先给出最终的结果,然后描述一下这个SQL的思路如下:
SQL> WITH T_NUM AS
2 (SELECT ROWNUM + 1 NUM FROM DUAL CONNECT BY LEVEL < 99)
3 SELECT A, B
4 FROM
5 (
6 SELECT
7 A,
8 B,
9 TOTAL,
10 MUL,
11 MUL_P,
12 COUNT(DECODE(MUL_P, 1, 1)) OVER(PARTITION BY TOTAL) VALUE
13 FROM
14 (
15 SELECT
16 A,
17 B,
18 TOTAL,
19 MUL,
20 COUNT(*) OVER (PARTITION BY TOTAL) TOTAL_P,
21 COUNT(*) OVER (PARTITION BY MUL) MUL_P
22 FROM
23 (
24 SELECT
25 A,
26 B,
27 TOTAL,
28 MUL,
29 MIN(MUL_P) OVER (PARTITION BY TOTAL) MUL_M
30 FROM
31 (
32 SELECT
33 A.NUM A,
34 B.NUM B,
35 A.NUM + B.NUM TOTAL,
36 A.NUM * B.NUM MUL,
37 COUNT(*) OVER (PARTITION BY A.NUM + B.NUM) TOTAL_P,
38 COUNT(*) OVER (PARTITION BY A.NUM * B.NUM) MUL_P
39 FROM T_NUM A, T_NUM B
40 WHERE A.NUM < B.NUM
41 )
42 )
43 WHERE MUL_M != 1
44 )
45 )
46 WHERE MUL_P = 1
47 AND VALUE = 1;
A B
---------- ----------
4 13
SQL有点长,下面简单分析一下。
首先看一下WITH语句,这个语句其实就是构造大于1小于100的所有的数。
31 (
32 SELECT
33 A.NUM A,
34 B.NUM B,
35 A.NUM + B.NUM TOTAL,
36 A.NUM * B.NUM MUL,
37 COUNT(*) OVER (PARTITION BY A.NUM + B.NUM) TOTAL_P,
38 COUNT(*) OVER (PARTITION BY A.NUM * B.NUM) MUL_P
39 FROM T_NUM A, T_NUM B
40 WHERE A.NUM < B.NUM
41 )
首先从SQL的最内层开始分析,这一层很简单,构造符合大于1小于100的两个数的笛卡儿积,得到所有的可能性。
根据题目的描述,第一个数是2,第二个数是3的情况,与第一个数是3,第二个数是2没有区别,所以这层SQL在连接时加上了限制条件A > B,这样可以去掉重复的结果。在SELECT列表中分别列出A、B两个数值,以及两个数值之和(A+B)、两个数值之积(A*B),还通过分析函数计算所有可能性中两个数之和与当前两个数之和相等的组合的个数,以及所有可能性中两个数之积与当前两个数之积相等的组合的个数。
23 (
24 SELECT
25 A,
26 B,
27 TOTAL,
28 MUL,
29 MIN(MUL_P) OVER (PARTITION BY TOTAL) MUL_M
30 FROM
31 (
32 SELECT
33 A.NUM A,
34 B.NUM B,
35 A.NUM + B.NUM TOTAL,
36 A.NUM * B.NUM MUL,
37 COUNT(*) OVER (PARTITION BY A.NUM + B.NUM) TOTAL_P,
38 COUNT(*) OVER (PARTITION BY A.NUM * B.NUM) MUL_P
39 FROM T_NUM A, T_NUM B
40 WHERE A.NUM < B.NUM
41 )
42 )
接着看第二层SQL,除了列出A和B两个数外,还列出了A和B之和、A和B之积以及一个很重要的值:根据两个数之和进行分组,找出这两个数之积的组合的最小个数。这样描述确实很抽象,不过没有关系,马上要分析的第三层,会对这个值的含义做进一步的说明。
14 (
15 SELECT
16 A,
17 B,
18 TOTAL,
19 MUL,
20 COUNT(*) OVER (PARTITION BY TOTAL) TOTAL_P,
21 COUNT(*) OVER (PARTITION BY MUL) MUL_P
22 FROM
23 (
24 SELECT
25 A,
26 B,
27 TOTAL,
28 MUL,
29 MIN(MUL_P) OVER (PARTITION BY TOTAL) MUL_M
30 FROM
31 (
32 SELECT
33 A.NUM A,
34 B.NUM B,
35 A.NUM + B.NUM TOTAL,
36 A.NUM * B.NUM MUL,
37 COUNT(*) OVER (PARTITION BY A.NUM + B.NUM) TOTAL_P,
38 COUNT(*) OVER (PARTITION BY A.NUM * B.NUM) MUL_P
39 FROM T_NUM A, T_NUM B
40 WHERE A.NUM < B.NUM
41 )
42 )
43 WHERE MUL_M != 1
44 )
第三次列出的仍然包括A和B两个数,以及两个数之和、两个数之积。除此之外,还列出了与当前记录中两个数之和相同的组合数;与当前记录中两个数之积相同的组合数,更关键的是这里进行了过滤,在第二层得到的MUL_M不等于1。
目前得到的结果就是Gauss虽然自己不知道两个数是什么,但是可以确认Poincare也不知道。前面已经举过3和7的例子来说明这个问题了,这里就不再重复了。如果归纳起来,就是Gauss手中的两数的和,分解为任何一种可能所得到的两个数的积,都不是唯一的。在SQL中表示的结果就是MIN(MUL_P) OVER (PARTITION BY TOTAL) != 1。
随后要解决的问题就是Poincare说他原来并不知道两个数分别是什么,而当Gauss说完那句话后他已经知道这两个数的值了。也就是说到目前为止,两个数的积已经可以唯一确定这两个数是什么了,数学描述就是两个数乘积分组后值相同的个数是1。在SQL中的表示也就是最外层SQL的限制条件MUL_P = 1。
随后还有最后一个条件,就是Gauss这时也知道了两个数是什么,说明Gauss根据Poincare确定两个数的数值这个事实,进一步推断出了最终的结果。这个SQL的实现是通过COUNT(DECODE(MUL_P, 1, 1)) OVER(PARTITION BY TOTAL) = 1来实现的。前面提到了,只有MUL_P为1的情况,Poincare才能唯一确定两个数的值,而Gauss根据这个结果也推断出两个数的值,说明在当前两个数之和的分组中,只有一种情况满足MUL_P的值为1。
因此整个SQL组合起来,就是这道题的解。
这道题本身解决问题的思路只有穷举法,如果手工计算会非常麻烦且容易出错,而利用穷举法解决问题正是SQL所擅长的。将数学语句通过SQL来进行表述,就可以方便快速地得到最终的结果。
老杨带你用SQL解释经典的扑克牌魔术
一个偶然的机会在电视上看到一个有关扑克牌的魔术,觉得很有意思。这个魔术明显不是靠手快或者做假来实现的,奥妙在于魔术中包含了数学原理。
首先描述一下这个魔术,有兴趣的话,可以按照这个方法试一试。
从一副扑克牌中随意抽取21张牌。让观众从这些牌中随意选择一张,这张牌就是最后通过魔术需要找到的目标牌。让观众牢记后将其放回到其余20张牌中,然后任意洗牌。
下面开始进行发牌的工作,发牌和普通扑克的发牌规则一样。将牌发成3叠,每叠7张。将每叠牌依次展示给观众,要求观众确认目标牌在3叠的哪一叠中即可。
之后将3叠牌合在一起,将包含目标牌的一叠放在其他两叠牌中间。注意此时不要打乱每叠牌的顺序。
然后再次发牌,和刚才完全一样,还是将牌发成3叠。让对方确认目标牌所在的一叠,将这叠牌放到另外两叠牌的中间。
最后,再次重复上面的发牌、确认此过程,仍然将包含目标牌的那叠牌,放到另外两叠牌的中间。
下面神奇的时刻到来了:从这叠扑克牌的上面每次拿起一张,每拿起一张牌的同时要说一句话:“你要相信魔术你的牌是”。说完这句话,下一张牌就是目标牌了。
看上去这个魔术很神奇,而且最神奇的是,这个魔术任何人都可以来表演。这就说明无论这张牌最初在哪个位置,只要按照这个规则最后都一定会来到这个指定的位置。
看了这个魔术,不禁有点手痒,既然是DBA出身,就用SQL来演示一下这个魔术的过程吧,见如下代码:
SQL> WITH A AS
2 (SELECT ROWNUM P FROM DUAL CONNECT BY LEVEL <= 21)
3 SELECT
4 7 + CEIL(
5 (7 + CEIL(
6 (7 + CEIL(P/3))
7 /3))
8 /3)
9 FROM A;
7+CEIL((7+CEIL((7+CEIL(P/3))/3))/3)
-----------------------------------
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
已选择21行。
解释一下这个SQL:
设WITH查询中的P表示这张牌的初始位置,这个位置的取值范围是从1到21。而后将牌按照发牌的顺序分成3份,于是这张牌的位置变为CEIL(P/3)。由于在魔术表演的过程中,目标牌所在的那一叠牌会放在其他两叠牌的中间,也就是说目标牌的前面增加了7张牌,因此目标牌的位置要增加7。
魔术中上面的步骤重复了3次,因此在SQL中这个过程也重复3次,最终SQL返回的结果就是目标牌21种不同初始位置所对应的魔术结束时刻目标牌的最终位置。
根据计算结果可以看到,无论这张牌在哪里,最终都会达到第11张的位置。这也就是这个魔术的奥秘之所在。
不过SQL只是演示了结果,并没有给出为什么会出现这种结果的答案,下面通过数学手段简单分析一下:
由于第一次平均分的时候这张牌的位置是任意的,所以这次平均分的意义不大。这次平均分的目的只是将目标牌的那一份放到中间的位置。所以可以认为这张牌在中间位置第1到7的任何一个位置上,因此这张牌的位置就是7 + p。下面将牌分成三份,然后将目标牌堆放到中间,这时这张牌的位置变为7 +(7+p)/3。最后再重复一次这个动作,最终结果变为:7 + (7 + (7+p)/3)/3。
对上面的表达式进行通分计算后,结果变成(7*9 + 7*3 + 7 + p)/9,进一步简化变成(91 +p)/9,最后变成了10 + (1+p)/9,而p的位置是1到7,也就是说无论取何值,(1+p)/9都不会大于1,所以最终的结果是11。
最后,应该修改一下魔术中咒语:“你要相信数学你的牌是”。