a*******s
发帖数: 4 | 1 一个线上有20个点，其中每个点可以和相邻3个之内的点通讯，例如节点10可以和7，8
，9，11，12，
13通讯。请问若20个点中有n个被拿走后仍可以保持两端通讯的概率。假设节点1和20不
会被拿走。当n
为1和2时比较简单，概率为1。 谢谢。 | g*******y
发帖数: 1930 | 2 是要写算法解决吧，不是直接一下子就能给出答案的吧。
问题貌似可以简化为，N个点中随机选n中个点，选中的n个点里不出现3点或者3点以上连续的概率是多少。
于是乎，考虑对n划分为很多截，每截不超过2:
n = 1, 1, 1, 1, 1, 1, ..... n截
n = 2, 1, 1, 1, 1, 1, ..... n-1截
n = 2, 2, 1, 1, 1, 1, ..... n-2截
。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。n/2截
将 n-i截这样的东西，插入到 剩下N-n个节点的缝隙中（有N-n-1个缝隙）
可能的情况数目就是：P(n-i, N-n-1)/i!/(n-2i)!
注意到有限制的，n-i不能超过N-n-1
上面的表达式，在满足限制条件下，对i求和，就是总的允许的情况数。
最后再除以C(n，N-2)，就是概率了。 | y****e
发帖数: 158 | 3 1-(16*C(15,n-3))/C(18,n) | m********0
发帖数: 2717 | 4 wrong
n = 17 gives negative number
1-16*15/17
【在 y****e 的大作中提到】
: 1-(16*C(15,n-3))/C(18,n)
| f*********r
发帖数: 68 | 5 想了一下, 更一般的结果好像是
f(N, n) = f(N-1, n) + f(N-2, n-1) + f(N-3, n-2)+ C(N-6, n-3)
N=20, 小n如题意, 结果是1-f(N-2, n)/C(N-2, n)
估计还可以化简一下. | g*******y
发帖数: 1930 | 6 你这个好像有问题。。。
不过你的思路挺不错的，你算的f()是要排除的有三个或以上连续的情况吧，其实你不
如直接递归的算F(N,n): 从N个点里选n个点，满足：选出来的点，最大的连续长度是2
F(N,n) = F(N-1,n) + F(N-2, n-1) + F(N-3,n-2) = 不选第一个点 + 选第一个不选第
二个 + 选前两个不选第三个
最后答案直接就是 F（N-2,n)/C(N-2,n) 减掉2是因为两个端点不选
【在 f*********r 的大作中提到】
: 想了一下, 更一般的结果好像是
: f(N, n) = f(N-1, n) + f(N-2, n-1) + f(N-3, n-2)+ C(N-6, n-3)
: N=20, 小n如题意, 结果是1-f(N-2, n)/C(N-2, n)
: 估计还可以化简一下.
| f*********r
发帖数: 68 | 7 笔误, 我该一下
2
【在 g*******y 的大作中提到】
: 你这个好像有问题。。。
: 不过你的思路挺不错的，你算的f()是要排除的有三个或以上连续的情况吧，其实你不
: 如直接递归的算F(N,n): 从N个点里选n个点，满足：选出来的点，最大的连续长度是2
: F(N,n) = F(N-1,n) + F(N-2, n-1) + F(N-3,n-2) = 不选第一个点 + 选第一个不选第
: 二个 + 选前两个不选第三个
: 最后答案直接就是 F（N-2,n)/C(N-2,n) 减掉2是因为两个端点不选
| H*****L
发帖数: 5705 | | g*******y
发帖数: 1930 | 9 F(N,n)：从N个点，选n个点出来，选出来的n点中，满足最长的连续不超过2。这样的选
择有多少种。
【在 H*****L 的大作中提到】
: F=?
|
|
