今天不用写代码,就得到了欧拉项目53题的答案,现在总结下我的思路。
当n=23,r=10时,组合数就大于100万了。由此可知,r为10-13时,都是大于100万的。所以满足题目的数的个数是23+1-10*2=4个。
同时,n=24,r=10时,肯定也大于100万。
那么n=24,r=9的时候呢?拿科学计算器摁了一下,也大于100万。
可以得到一个结论,当r=9时,n=24是满足题意的最小的数字。
当n为24时,满足题意的数字有24+1-9*2=7个。
解释下上面出现的式子的原理。
r有n+1种取法,所以是23+1和24+1,r=9满足100万,那么r从0到8这九个数不满足,减去一个9,对称的,后面也有9个不满足题意。
接下来,寻找那个最小的n,当r=8时,就能满足题意。简单的计算了一下,结果是n=25。
以此类推,得到一个临界值组成的表:
23 10
24 9
25 8
28 7
33 6
44 5
72 4
这里说一下,不用每个数字都计算,利用类似于二分法的思想,只用计算很少的次数,就能得到这个表了。
这个时候利用Excel计算答案。
首先填充23,24,利用自动填充功能,把第一列填充为23-100。
把临界值表里面的数字填到第二列,利用自动填充功能,把第二列也都填好。
比如25到27都填充上8,28到32都填充7,72以后都填充成4。
第三列写上公式=A1+1-2*B1,第三列也可以自动都计算好。
在第三列最后,利用求和公式,得到答案。
至此,完成了题目。