问一个题目，谢谢。# JobHunting - 待字闺中
a*s
1 楼
一个线上有20个点，其中每个点可以和相邻3个之内的点通讯，例如节点10可以和7，8
，9，11，12，
13通讯。请问若20个点中有n个被拿走后仍可以保持两端通讯的概率。假设节点1和20不
会被拿走。当n
为1和2时比较简单，概率为1。 谢谢。
，9，11，12，
13通讯。请问若20个点中有n个被拿走后仍可以保持两端通讯的概率。假设节点1和20不
会被拿走。当n
为1和2时比较简单，概率为1。 谢谢。
g*y
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)，就是概率了。
问题貌似可以简化为，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
3 楼
1-(16*C(15,n-3))/C(18,n)
m*0
4 楼
wrong
n = 17 gives negative number
1-16*15/17
【在 y****e 的大作中提到】
: 1-(16*C(15,n-3))/C(18,n)
n = 17 gives negative number
1-16*15/17
【在 y****e 的大作中提到】
: 1-(16*C(15,n-3))/C(18,n)
f*r
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)
估计还可以化简一下.
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
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()是要排除的有三个或以上连续的情况吧，其实你不
如直接递归的算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
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是因为两个端点不选
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
8 楼
F=?
g*y
9 楼
F(N,n)：从N个点，选n个点出来，选出来的n点中，满足最长的连续不超过2。这样的选
择有多少种。
【在 H*****L 的大作中提到】
: F=?
择有多少种。
【在 H*****L 的大作中提到】
: F=?
相关阅读
求助如何在简历上写工作经历中的GAPopt extension I765上everify company identification number是cost of H1b application下周二投行面试，求祝福H1B Premium RFE! 求助.....周五下午面试的，说这周给消息 求祝福大家每天为找工作祈祷么？哪位大牛能给预测一下今年的H1B大概什么时候能用完？8月12号H1B PP,现在还没消息发包子问问题：拿到一个Offer，办H1B还来得及吗？郁闷，被amazon放鸽子。。7月20notice，9月下旬工作，需要expedite吗， CSCCPT 或者 H1B？？？？？请帮忙了！！！求教H1签证的transfer (转载)本科6万，研究生8万，MBA10万请问，电话面试后的thank you letter有什么特别要注意的吗？一般是公司负责H1B配偶H4的filing，还是个人自己负责？哪些人该写感谢信？没地址怎么办？Goldman现在支持新的H1B吗？再问道题