【欧拉计划】一个组合问题

Balls_Banner
Standard

前几天又开始刷欧拉计划,遇到一道很有意思的题,把它化简之后,核心在于解这样一个组合问题:

一个袋子里有4个红球、2个蓝球,按顺序从中取出不多于2个球,问有多少种结果?(计取出顺序,且认为同色球都相同)

全部列出来就知道共有6种组合,分别是r, b, rr, rb, br, bb。

推广到一般情形,即:

有 $m$ 种不同的元素,分别有 $n_1, n_2, \ldots , n_m$ 个,其中 $n=n_1+n_2+\ldots+n_m$ 。现在要从中取出不多于 $L$ 个,问有多少种可能的取法?

对于 $m=2, n_1=4, n_2=2, L=2$ 的情形,结果是6。

那对于一般的情形,又该如何计算这个值呢?

下面我将给出两种解答这个问题的思路:第一种是我当时解答这个问题的思路,第二种则是在论坛里看到的高人的解答。

Continue reading

【欧拉计划 #49】记一次神奇的解题经过

Standard

了解我的人应该都知道欧拉计划吧,就不多介绍了,这次是第49题,如下:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

 

翻译概括如下:

寻找一个3位的序列,满足:

  1. 每个数都是4位数的质数
  2. 构成等差数列
  3. 每个数的4个数字是另两个数的置换(例如1487, 4817, 8147)

已知这样的序列一共只有两组,一组是(1487,4817,8147),问另一组是什么?

 

这道题我想了半天,没有在数学上把它化简出来,就准备用枚举法做了。

因为要求的是一个3个数的有序序列,其总的可能数不超过9000^3/3!≈1.215e+11,直接枚举每个数会死人的。

由条件2,它是等差序列,这样知道两个数就能算第三个数,枚举的压力小了一点,上限是9000^2/2!/2≈2.0e+7,大概是两千万这个量级,依旧无法接受。

再由条件1,或许可以先生成1000~9999间的质数列表,再从中进行枚举,经计算这一区间内共有1061个质数,于是枚举量上限为1061^2/2!≈562860,五十万次。。唔。。还行吧。

但还有最后一个条件,每个数的数字构成必须相同,这个条件的验证还是有点麻烦的,目前还没想到特别高效的验证方法。但是其生成确是比较高效的。

 

想着想着,我就在想能否归纳出这类带约束的枚举类问题的通性,最终我画出了如下的表:

类型 验证 生成
质数 简单 简单
等差数列 相当容易 困难,情况数十分多
数位同构 比较麻烦,不够效率 中等,共C104 = 210组,每组至多24个元素

 

枚举固然有很多种方式,但说到底还是在于你对每一个维度选择了生成策略还是验证策略,而且其可能难度很不相同,这颇有点NP问题的感觉。

Continue reading

Euler Project(欧拉计划)刷题记(Problem 1~50)

Standard

EulerProject官网地址)是一系列问题的集合,涉及数学与计算机方面。有的问题看起来是一个计算机问题,但却可以用数学推导去化简,有的问题化简到最后,也需要用编程技巧写代码来求解它。

EulerProject不限制你所用的语言,你可以使用Mathematica这样的数学工具,也可以使用PythonC++,甚至可能连编程语言都不需要,如果是自己推导算出答案的话。在解决完一道题后,会开放该题的讨论区,在那里你就能看到其他人是怎么解决这道题的。

EulerProject强调的是解决问题的想法,而不是你用什么编程语言。并且上面的题都是围绕一个很有趣的“一分钟法则”来设计的。这个法则是说,有可能你写了一个算法花了很长时间才算出结果,但总存在一个高效的算法能够在一分钟内得出结果,即使在一台性能比较差的计算机上。

然后,我就是开始了在EP上艰难的旅程,我用的是Mathematica语言。

 

如果说把每一道题的解答过程都写出来的话,就会显得很麻烦,而且已经有人做过这种事了。如果不写的话,又没什么好说的,真是太纠结了。干脆就这么水掉吧。

转念一想,很多人可能是第一次听到EulerProject,为了让更多人了解它,我觉得还是有必要举点例子,把一些有代表性的题拿出来说一下的。

 

EP Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

 

题目意思是这样的:如果把10以下的3或5的因子列出来的话,有3,5,6,9,它们的和是23. 现在问1000以下3或5的因子之和是多少。

这道题作为整个EulerProject的第一题,一定程度上能传达出整个系列题目的风格,也侧面反映出能刷它的要求。就这道题而言,一般有两种做法,一种做法是写个算法枚举,另一种是通过数学推导直接求和。两种思路都能解决问题,并且实现起来也不难,就看你喜欢哪一种了。

如果是前者,只要有一点基本的代码功底,写一个这样的程序算一下应该没什么问题,实际上,对编码能力的要求并不是很高。因为它不是POJ,它不考验你算法理论、数据结构学的怎么样,只要求你能够用代码的工具去把问题实现即可。(像Python这种轻巧的脚本式语言就是不错的选择)

如果是后者,只要你能反应过来是“3的倍数+5的倍数-15的倍数”就足够了,容斥原理而已。拥有较强数学思维能力的同学可能会觉得后者更加适合。毕竟闭上眼睛想象,画画草稿纸就能蹦出一个答案,还是很了不起的。

 

EP Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

 

好逗的题目啊,问你第10001个质数是什么?

100内的质数还能背一下,可第10001个质数恐怕没人能直接报出来吧。

我用Mathematica我自豪,下面的代码可以直接得到答案:

Prime[10001]

用Python的话就要长一点了。

 

好像上面的题都有点水了,就没有有点挑战性的题目么?别急,前面题号才是个位数呢。

Continue reading