问一个题目，谢谢。# 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=?
相关阅读
小弟刚硕士毕业，面临选择，就高手们的意见CS master找不到intern会不会以后找不到工作？CPT 还是 OPT ？ (转载)关于背景调查里面的国内工作经历火急！！ palantir的programming challenge各路英雄有礼了请教两个Linux问题给LeetCode推荐一道题Modified Minimum Path Sum[合集] MS转Ph.D.后Quit Ph.D. 请问这种情况怎么才能合法工作？请教一道单链表问题这个offer怎么样？市场上Java programmer 位置不少，entry 的市场一般般，急问这个bonus条款是什么意思啊?For those who wants to apply GOOG超龄大妈要改行，寻求建议，谢谢！「急」h1b approval notice上的expire日期码工为啥没前途找工作转行 真诚求建议EE position