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

杨廷琨,网名 yangtingkun

云和恩墨技术总监,Oracle ACE Director,ACOUG 核心专家

用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的思路如下:

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来进行表述,就可以方便快速地得到最终的结果。

近期文章

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

2015 Oracle 十大热门文章精选

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

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

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

三十八载,Oracle伴我同行—记我的成长之路

从Approx_Count_Distinct到M7的CPU集成

诊断工具与方法:从OS到数据库

Cloud时代DBA的DevOps最佳实践 - SQL 审核

Oracle Database 12.2新特性详解

数据驱动,成就未来。整合业界顶尖的技术与合作伙伴资源,围绕数据及相关领域,提供解决方案和专业服务。

业务架构

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

IT基础架构

分布式存储解决方案

数据架构

Oracle DB2 MySQL NoSQL

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

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

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

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

应用架构

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

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

原文发表时间:2016-01-18

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏圆方圆学院精选

【戴嘉乐 IPFS】基于IPFS和GeoHash构建具有地理位置价值服务的DDApp(理论篇)

打造地理位置信息与区块链的关系对象模型,建立一套 人->位置->真实世界->传递信任->价值转移->位置->人 的生态模型,实现用区块链来索引真实世界的愿景。

781
来自专栏HansBug's Lab

1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

2568
来自专栏区块链大本营

漏洞连载|浮点与精度处理不当的那些事儿

“言治骨角者,既切之而复磋之;治玉石者,既琢之而复磨之,治之已精,而益求其精也。”——宋·朱熹

881
来自专栏用户画像

实验3.2 复杂的单表查询

熟练掌握SELECT查询语句中的Group by 子句、Having子句的用法,以及汇总函数的使用。

733
来自专栏ml

NYOJ-------笨蛋难题四

笨蛋难题四 时间限制:1000 ms  |           内存限制:65535 KB 难度:3 描述 这些日子笨蛋一直研究股票,经过调研,终于发现xxx公...

33713
来自专栏数据结构与算法

BZOJ4819: [Sdoi2017]新生舞会(01分数规划)

Description 学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。有n个男生和n个女生参加舞会 买一个男生和一个女生一起跳舞...

3457
来自专栏Java Web

背包问题

问题描述 假设你是一个贪婪的小偷,背着可以装35磅重东西的背包,在商场伺机偷窃各种可以装入背包的商品。 ? 你力图往背包中装入价值最高的商品,你会用哪种算法呢?...

2505
来自专栏编程一生

架构师之路--从原理角度来分析性能

  埃及艳后Cleopatra,很小的时候看过妈妈买的一本书里把她的名字翻译成克娄巴特拉,里面有很多描写她美貌的场景描写。然而这个以美貌著称的奇女子,我看到书里...

662
来自专栏racaljk

Leetcode 746. Min Cost Climbing Stairs 最小成本爬楼梯 (动态规划)

有一个楼梯,第i阶用cost[i](非负)表示成本。现在你需要支付这些成本,可以一次走两阶也可以走一阶。 问从地面或者第一阶出发,怎么走成本最小。

793
来自专栏数据和云

网友过招老杨:Gauss和Poincare数学问题的另类解法

大家应该还记得前几天我们的一篇文章:用SQL解一道有趣的数学题:Gauss和Poincare ,错过的朋友请先回顾。感谢网友的反馈,发来新的解法一则。 如网友所...

2604

扫码关注云+社区