Mathematica 谜中智 | 奥运五环 数字谜题(谜底)

奥运五环中的秘密,你找到了吗?

谢谢@翁德平的回答。

共有8组答案,数字按下图位置和顺序摆放。答案分别是:

925461738, 837164529, 941832567, 765238149, 765283194, 491382567, 861743295, 592347168。

解题

使用函数:Permutations,Select, Union, MemberQ, FromDigits, Timing。

方法一:数学思维

本题虽小,但我们也可以探讨一下解题思路,如下从两个层次,数学和算法分别来探讨一下。

先从数学上讲,本题属于离散和组合数学,1-9个数字的全排列,用Wolfram语言可以表示如下。

它们构成了本题全部的数据组合,正确答案肯定在这个范围内。接下来就是我们如何通过定义满足题意条件或规则,来把正确答案从以上的集合中找出来。

根据题意要求,每个环内的数字相加之和相等。再通过观察,我们不难发现,两环相交处中间的数字被用到了两次。其实就是第一个环是由2个数字相加,第二、第三和第四个环是由3个数字相加,第五个环又是由2个数字相加。9个数字中间有4个数字被两侧的环重复利用了,5个中间的数字仅使用了一次。

如下我们来构造一个自定义函数,它的功能就是根据题意分别为每个环的相加之和。

随后,我们将1-9的全排列permutation,代入自定义函数ringSumFunction,来计算环内之和,并将它们中5个环相等的情况挑选出来。如下我们认为5环的环内之和数值相等,因此合并之后长度为1。

结果出来了,共有8组解,而且可以得知,是环内之和为 11,13 和14的情况是正确解。但是具体9个数字的排列顺序目前还不知。没关系,接下来我们根据以上结论,环内之和数相等ringSumEqual,从permutation中把符合的情况都挑选出来。最后用FromDigits将链表在转换为数字形式。

恭喜你!获得了正确的答案。从数学角度而言,这种方法定义了一个数据库,然后通过一定规则或条件,从数据库中搜索找到正确答案。因此这种方法比较简单、直接,当然也便于理解,从数学角度而言是它或许是可以接受的。但是它也存在一个问题,接下来我们进一步讨论。

我们回顾一下之前解题的代码,并且用Timing来测试一下运行时间。

代码4行,倒也不算复杂。但运行时间达到约8秒,这个其实有点差劲了。心理学家曾测试,计算机用户如果等待计算机响应的时间大于5秒,就能明显感觉是在等待。分析一下造成运行时间较长的原因是1-9个数字的全排列permutation实际是一个大数据团。

其实1-9个数字的全排列也就是9的阶乘,数据的量级在36万组,计算量当然也就是36万次了。

离散数学中排列组合问题就是这样,往往是按照指数级别向上增长,看看没几个数字,但组合在一起就是个大谜团。

方法二:算法思维

接下来我们从算法设计的角度,再来讲解一下。之前的方法从算法上讲,属于“蛮力法”或是“暴力法”,也就是让计算机“充分地”去做所有的计算,包括必要的和“不必要”的任务。

同时,根据之前的分析,我们也知道了问题所在,组合数量庞大。那么让我们换个思路,如何降低排列组合数量,提高计算机运行的效率。

通过之前的一轮解题,我们发现其实每个环内数之和也就是从11到14的范围内。那么我们不必把每个数字都排列出来了,而仅仅挑选两环相交的数字numberBetweenRings 生成排列,剩余的数字我们可以通过环内数之和sumRings间接计算而得。

同样地,我们来构造以供由4个环间数字和1个环内数之和作为函数的输入变量,构成的9个数字的链表。

这样构造9个数字链表,可能未必正好是1-9这九个数字,再通过Sort把符合1-9数字情况挑选出来。如下我们假设环内数之和等于11。看一下计算结果,运行时间大幅缩短,达到0.1秒以内。

当然以上计算的其实仅是一种特殊情况,即环内数之和等于11。但仔细想想,其实环内数之和的范围也是极为有限的,它的最小值是1+2=3,它的最大值7+8+9=24,从3到24也就是环内数之和的有效范围。我们再次计算,来获得环内数之和ringSum变量在全部有效范围内的解。

通过Select把空解过滤掉,也用FromDigits将链表在转换为数字形式。

可见,得到了同之前方法相同的正确答案。同样使用4行代码,运行时间明显下降了一个数量级,现在仅需0.8秒了。

其实质是计算量小了一个数量级,目前的组合数仅3千组,再乘以20多种环内数之和的情况。通过我们合理的分析和理解,大幅减少了组合情况,仅计算"最必要"的部分,而将一些简单的冗余计算抛弃。

从8秒降低到0.8秒,运行效率提升一个数量级。使原有明显的等待时间,降低到一种使用者很难发现的等待时间,是实现人机动态和高效交互的基础。

演示


参考文献

[1] F. Wu, "Pandigital Olympic Circles Puzzle", Wolfram Demonstrations Project.

原文发布于微信公众号 - WOLFRAM(WolframChina)

原文发表时间:2017-04-15

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大史住在大前端

javascript基础修炼(8)——指向FP世界的箭头函数

箭头函数是ES6语法中加入的新特性,而它也是许多开发者对ES6仅有的了解,每当面试里被问到关于“ES6里添加了哪些新特性?”这种问题的时候,几乎总是会拿箭头函数...

1043
来自专栏落花落雨不落叶

一个比较有意思的C语言问题

2987
来自专栏精讲JAVA

面向对象VS面向过程

1 前言 向伟人致敬 其实这个问题真的是被问烂了,特别是刚入门的同行,我感觉这个问题应该是大家都听说过了,但是有多少人真的是理解这两个区别呢,这两...

2025
来自专栏java一日一条

由字符串反转(使用递归)引申出来一道Java面试题

在Java中,最好的实现就是用JDK中StringBuffer的反转方法,它不仅速度快,效率高,而且还知道如何处理unicode代理对(surrogate p...

731
来自专栏编程

编程老司机带你玩转C语言指针

很多初学编程的小伙伴都会选择C语言作为第一门学习的编程语言,应为C语言作为一门底层语言相对于其他的高层语言来说更加容易学习。可以来帮助正在学习编程的小伙伴更加快...

2406
来自专栏take time, save time

你所能用到的数据结构(三)

三、对于效率提高的初次尝试     对于最自然的几种排序算法,数学家们开始思考如何提高排序算法的效率,可以通过数学证明出来如果想达到这个目的,必须想办法将相距...

2837
来自专栏Java技术栈

国外大神总结的 10 个 Java 编程技巧!

2582
来自专栏平凡文摘

国外大神总结的 10 个 Java 编程技巧!

1232
来自专栏java一日一条

由字符串反转(使用递归)引申出来一道Java面试题

如何面试一个从事编程工作的开发人员既困难又乏味,幸好还有很多值得参考的指南,比如:《Joel Guerilla Guide to interviewing》,...

852
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

1314

扫码关注云+社区

领取腾讯云代金券