Question

高中数学 排列组合 求解

40个在一条线上距离一样的点，选9个，要求不能有这样三点ABC，AB=BC
有多少种选法
谁能用程序在1分钟内算出来也行啊

Answer 1

你这个题就像是在百万个数里面找所有的质数一样，200分都不一定有人做的，呵呵！

我说下我的方法吧，
用排除法
40个选9个是C（40，9）
有这样三点ABC，使AB=BC的情况总结如下
设40个点是1、2、3、4、。。。、40
1、间距是1个单位
取1、2、3则有C（37，6）种排法
取1、2、3、4则有C（36，5）种排法
C（37，6）-C（36，5）表示取1、2、3无4的排法也就是C（36，6）
同理取2、3、4有C（37，6）种排法
取2、3、4、5有C（36，5）种排法
C（37，6）-C（36，5）表示取2、3、4无5的排法也就是C（36，6）
。。。
一共37组
最后一组取38、39、40
下面无连续4个所以共有C（37，6）种排法
总结：有三个以上点满足一个间距的排法共有C（36，6）*37+C（37，6）种
2、间距是2个单位
取1、3、5则，要去掉间距是一个单位的连续排法相当于35个数字里面选6个
共有C（31，3）*32+C（32，3）种，还有有6、7无8的情况为C（32，4）
同理2、4、6有C（35，6）种排法，去掉间距是一个单位的连续排法相当于后面34个数字里面选6个，再加上含有1的情况（相当于34个数字里面选5个）。
也就是C（30，3）*31+C（31，3）+C（31，4）+C（30，2）*31+C（31，2）+C（31，3）
。。。
分析不下去了，太繁了，呵呵

追问

首先，
辛苦你了。。。
打了这么多字

但是，
你的思路没太明白

应该是只要有1 2 3之类的就是不行

但是有可能是1 2 3 7 8 9 ... 会被算两次
也有可能是 1 2 3 5.......有1 2 3和1 3 5两组间隔不同的情况

最后补充一点
找n以内的质数的复杂度只有O(n²)
100万还是可以忍的
但是，这个问题是NP问题
n=20用程序还能跑出来
n=40就彻底死了

追答

呵呵，是吗，
我的思路你可能没有看懂，
我用的排除法，
我是想罗列所有的不满足条件的可能性，可能是有疏漏，不过是可以研究的

找n以内的质数的复杂度只有O(n²)，没你说的那么简单吧，要不你找下相邻的两个质数最大的差是多少？如果你能找出来，我都可以证明哥德巴赫猜想了，呵呵。

Answer 2

真実はいつも一つ