一个24点的算法

作者: loaf 分类: IT 发布时间: 2018-11-09 16:43
  1. 首先想到的是找规律,比如3*8=24,4*6=24,然后向这几个数来凑。但是想这个规则就有些复杂了。优化一下,比如按我教女儿的方法,先随机找一个数,假定它不动,比如3,然后列出可生成24的补数,比如,8、27、42,然后把问题变成用3个数求上面的补数,再递归一下,如果找不到有效数,就再用加减乘除先对两个数操作,生成一个数,列出这个数可求24的补数,把问题变成用另外两个数算出补数。想想有点复杂了。
  2. 在网上找了一下,大多数思路都是穷举,穷举就穷举吧,反正数也不多
    1. 比如这篇文章,他是用java来写的算法是,先把4个数排好,把任何计算分成三步,第一步,找两个数先算,第二步在第一步的基础上变成了3个数,再找2个数算,第三步,则只要考虑这两个数能否算出24即可。这可是真正的“硬”算,但是步骤很明确。
    2. 上一步应该是正常思路的第一步,再进一步,可以参考这篇文章,使用递归,思路很清晰。
    3. 又在网上看到这篇文章,里面的算法更加简洁,他不用考虑各种规则,反正做全排列,不合法的自然无法计算。

上面的代码由Python写成,里面涉及到了一个系统的库itertools,用于高效循环的迭代函数集合。上面涉及到一个函数为combinations_with_replacement,combinations的意思就是数学上的“组合”,所以这个过程其实是不带顺序的排列。而上面是指允许重复地使用相同的数。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注