密码486

来自计算思维百科
跳转至: 导航搜索
密码486.jpg

宰勋每戒一次烟,就会更换电子邮件的密码。密码总以no-smokeX的形式设置,X是个位数以上的自然数。不仅如此,第K次戒烟时,宰勋会选择具有k个约数的数值X。例如,第12次戒烟时修改的密码是no-smoke486。因为486有1、2、3、6、9、…、243、486共12个约数。

有一天,宰勋睡觉前下定决心要戒烟,并修改了邮箱密码。第二天清晨,他发现自己忘记了新设定的密码,只记得密码中的数值具有4个约数,且取值范围是10~20(包含10和20),那么该范围中共有几个可能的密码?

解决方案

解决该问题的主要步骤是求取值范围中每个数的约数。

方案一:蛮力法

对于取值范围10~20中的每个数n,用2~√n除n,找出其所有约数,其中具有4个约数的可能是密码。

10的约数:1、2、5、10

12的约数:1、2、3、4、6、12

14的约数:1、2、7、14

15的约数:1、3、5、15

16的约数:1、2、4、8、16

18的约数:1、2、3、6、9、18

20的约数:1、2、4、5、10、20

所以,可能的密码有10、14、15三个。

运用的计算思维

蛮力法需要遍历计算约数集可能范围中的每个数,运用的是机械化的计算思维,但是效率不高。

方案二:埃拉托色尼筛选法

埃拉托色尼筛选法是用于求一定范围自然数中的质数,步骤如下(以1,2,3,4,5……为例):

(1)先把1删除(现今数学界1既不是质数也不是合数)

(2)读取队列中当前最小的数2,然后把2的倍数删去

(3)读取队列中当前最小的数3,然后把3的倍数删去

(4)读取队列中当前最小的数5,然后把5的倍数删去

(5)如上所述直到需求的范围内所有的数均删除或读取

我们利用埃拉托色尼筛选法将取值范围10~20中的质数11、13、17、19去除,然后将剩下的数进行素因子分解。例如对18进行素因子分解得到,18=2×3^2。这表示18的约数是由不同个数的2和3的乘积得到,根据2和3的右上角的指数,其中2的个数不大于1(0,1),3的个数不大于2(0,1,2),所以,18有2×3=6个约数。

运用的计算思维

首先我们对取值范围中的数做了预处理,减少了操作数。接着将数转化成素因子乘积的表示方式,求出素因子的组合数就求出了约数个数,运用了“转化”的计算思维。同时埃拉托色尼筛选法的引入使得求解问题变得高效,是“嵌入”计算思维的体现。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015