H*M
发帖数: 1268 | 1 1. 一个公车站，有两路车，一路每5分钟一班，一路10分钟一班
你刚看到有辆车通过（不知道哪路），问，间隔下一辆车到来的时间的期望值是多少？
2. 招聘问题。 decide一个策略使得招到最牛的人的概率最大。
1. There is a single secretarial position to fill.
2. There are n applicants for the position, and the value of n is known.
3. The applicants can be ranked from best to worst with no ties.
4. The applicants are interviewed sequentially in a random order, with ea
ch order being equally likely.
5. After each interview, the applicant is accepted or rejected.
6. The decision to |
g*******y
发帖数: 1930 | 2 你看到的是5分钟的车的概率是2/3，看到这个是10分钟的车的概率是1/3
看到5分钟的车：
下一个车是10分钟的车：
平均等待时间，积分 x*1/10, 0<=x<=5,
下一个车是5分钟的车：1/2的概率，5*1/2
总的：2.5+1.25 = 3.75
看到的是10分钟的车，下一个来的必定是5分钟的车
平均等待时间2.5
总的： 3.75*2/3 + 2.5*1/3 |
g*******y
发帖数: 1930 | 3 第二个题以前讨论过，当时是说n个房间，挑身高最高的人的最佳策略的成功概率，很
难。
ea
the
【在 H*M 的大作中提到】
: 1. 一个公车站，有两路车，一路每5分钟一班，一路10分钟一班
: 你刚看到有辆车通过（不知道哪路），问，间隔下一辆车到来的时间的期望值是多少？
: 2. 招聘问题。 decide一个策略使得招到最牛的人的概率最大。
: 1. There is a single secretarial position to fill.
: 2. There are n applicants for the position, and the value of n is known.
: 3. The applicants can be ranked from best to worst with no ties.
: 4. The applicants are interviewed sequentially in a random order, with ea
: ch order being equally likely.
: 5. After each interview, the applicant is accepted or rejected.
: 6. The decision to
|
H*M
发帖数: 1268 | 4 对对，就是那题。。
叫秘书问题
我看到过特例是3个的，比较好解，通的就难了
【在 g*******y 的大作中提到】
: 第二个题以前讨论过，当时是说n个房间，挑身高最高的人的最佳策略的成功概率，很
: 难。
:
: ea
: the
|
a********a
发帖数: 219 | 5 是现在面试难度就这么高还是你跑偏了？或者你面试高级职位？
known.
with ea
the
【在 H*M 的大作中提到】
: 1. 一个公车站，有两路车，一路每5分钟一班，一路10分钟一班
: 你刚看到有辆车通过（不知道哪路），问，间隔下一辆车到来的时间的期望值是多少？
: 2. 招聘问题。 decide一个策略使得招到最牛的人的概率最大。
: 1. There is a single secretarial position to fill.
: 2. There are n applicants for the position, and the value of n is known.
: 3. The applicants can be ranked from best to worst with no ties.
: 4. The applicants are interviewed sequentially in a random order, with ea
: ch order being equally likely.
: 5. After each interview, the applicant is accepted or rejected.
: 6. The decision to
|
k***e
发帖数: 556 | 6 第2题是clrs书上random algorithm的一个例子 |
n******r
发帖数: 1247 | 7 设X为10分钟的车和前一班5分钟的车之间的间隔，没有额外信息情况下，假定X～U[0,5]
E[等待时间|X]=(X/10)*(5-X)+((5-X)/10)*5+(1/2)*X
E[等待时间]=积分 (1/5)*E[平均等待时间|X],0<=X<=5
35/12
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
从这里开始就应该积分
【在 g*******y 的大作中提到】
: 你看到的是5分钟的车的概率是2/3，看到这个是10分钟的车的概率是1/3
: 看到5分钟的车：
: 下一个车是10分钟的车：
: 平均等待时间，积分 x*1/10, 0<=x<=5,
: 下一个车是5分钟的车：1/2的概率，5*1/2
: 总的：2.5+1.25 = 3.75
: 看到的是10分钟的车，下一个来的必定是5分钟的车
: 平均等待时间2.5
: 总的： 3.75*2/3 + 2.5*1/3
|
g*******y
发帖数: 1930 | 8 呵呵，我想简单了，你这个方法很好
,5]
【在 n******r 的大作中提到】
: 设X为10分钟的车和前一班5分钟的车之间的间隔，没有额外信息情况下，假定X～U[0,5]
: E[等待时间|X]=(X/10)*(5-X)+((5-X)/10)*5+(1/2)*X
: E[等待时间]=积分 (1/5)*E[平均等待时间|X],0<=X<=5
: 35/12
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 从这里开始就应该积分
|
n******r
发帖数: 1247 | 9 呵呵，我觉得原题这样表述比较清楚
一路车5分钟一班，另一路车10分钟一班，假设你到站时排的位置使你没法上第一班来
的车，但是可以上第二班来的车，求在第一班车离开和第二班车到来之间平均等待时间。
【在 g*******y 的大作中提到】
: 呵呵，我想简单了，你这个方法很好
:
: ,5]
|
k***e
发帖数: 556 | 10 请问你能稍微解释一下吗
suppose x is given which is from [0,5],
did you mean with prob x/10 wait 5-x
(5-x)/10 wait 5
1/2 wait 5
1/2 wait x
then the total prob is more than 1.
am i missing something? Thanks.
,5]
【在 n******r 的大作中提到】
: 设X为10分钟的车和前一班5分钟的车之间的间隔，没有额外信息情况下，假定X～U[0,5]
: E[等待时间|X]=(X/10)*(5-X)+((5-X)/10)*5+(1/2)*X
: E[等待时间]=积分 (1/5)*E[平均等待时间|X],0<=X<=5
: 35/12
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 从这里开始就应该积分
|
|
|
n******r
发帖数: 1247 | 11 Esorry typo there, fixed, the answer is the same
~~~~~~~~~~~~~~~no this term
【在 k***e 的大作中提到】
: 请问你能稍微解释一下吗
: suppose x is given which is from [0,5],
: did you mean with prob x/10 wait 5-x
: (5-x)/10 wait 5
: 1/2 wait 5
: 1/2 wait x
: then the total prob is more than 1.
: am i missing something? Thanks.
:
: ,5]
|
k***e
发帖数: 556 | 12 hi, i think you have solved the problem that:
the person arrive at anytime. he waited for one train to pass but did not
take that one. he waited for the second one and take that one.
however, the problem says, he just saw one train passed. he take the next
one. thus i think we have to make the assumption that： with prob 1/3 he saw
the 10 min train and with prob 2/3 the 5 min train.
【在 n******r 的大作中提到】
: Esorry typo there, fixed, the answer is the same
:
: ~~~~~~~~~~~~~~~no this term
|
g*******y
发帖数: 1930 | 13 其实就是画一个时间轴的10min重复片段，从一辆10min的车到下一辆10min的车
这样算这个题就很清楚了，novastar这个方法很不错的～
【在 k***e 的大作中提到】
: 请问你能稍微解释一下吗
: suppose x is given which is from [0,5],
: did you mean with prob x/10 wait 5-x
: (5-x)/10 wait 5
: 1/2 wait 5
: 1/2 wait x
: then the total prob is more than 1.
: am i missing something? Thanks.
:
: ,5]
|
k***e
发帖数: 556 | 14 我觉得他解决的不是原题目的情形 请看我上个回复
【在 g*******y 的大作中提到】
: 其实就是画一个时间轴的10min重复片段，从一辆10min的车到下一辆10min的车
: 这样算这个题就很清楚了，novastar这个方法很不错的～
|
n******r
发帖数: 1247 | 15 that 1/3 2/3 assumption is not valid. Think in the case that the 10 minute
bus arrives right before one 5 minute bus, then the probability that the bus
you just saw is the 10-minute one is 0.
Since no information is given about the time interval between the two types
of buses, we can only assume X～U[0,5]
I made a post after that to make the problem statement more practical:
一路车5分钟一班，另一路车10分钟一班，假设你到站时排的位置使你没法上第一
班来的车，但是可以上第二班来的车，求在第一班车离开和第二班车到来之间平均等待
时间。
saw
【在 k***e 的大作中提到】
: hi, i think you have solved the problem that:
: the person arrive at anytime. he waited for one train to pass but did not
: take that one. he waited for the second one and take that one.
: however, the problem says, he just saw one train passed. he take the next
: one. thus i think we have to make the assumption that： with prob 1/3 he saw
: the 10 min train and with prob 2/3 the 5 min train.
|
k***e
发帖数: 556 | 16 hi, i agree with you that you get the correct solution basing on your
assumption.
However, for the 1/3, 2/3 assumption, it is also based on the hypothesis
that the schedule of two buses are independent decided without knowing the
other. thus
the case you given out has prob 0 of happenning.
bus
types
【在 n******r 的大作中提到】
: that 1/3 2/3 assumption is not valid. Think in the case that the 10 minute
: bus arrives right before one 5 minute bus, then the probability that the bus
: you just saw is the 10-minute one is 0.
: Since no information is given about the time interval between the two types
: of buses, we can only assume X～U[0,5]
: I made a post after that to make the problem statement more practical:
: 一路车5分钟一班，另一路车10分钟一班，假设你到站时排的位置使你没法上第一
: 班来的车，但是可以上第二班来的车，求在第一班车离开和第二班车到来之间平均等待
: 时间。
:
|
n******r
发帖数: 1247 | 17 If you think each bus has an arrival stream and you have an arrival stream (
which is what gets you the 1/3 and 2/3 "probability" I guess,) then the
event you come at a certain time point and see a bus (you meet the bus) is a
ZERO measure event.
That's why the problem needs to be modified a little to be solvable.
If you still have problem, we can make it like:
When you are at a certain distance from the bus stop, you can see the bus
arriving and leaving (this makes you seeing a bus leaving not
【在 k***e 的大作中提到】
: hi, i agree with you that you get the correct solution basing on your
: assumption.
: However, for the 1/3, 2/3 assumption, it is also based on the hypothesis
: that the schedule of two buses are independent decided without knowing the
: other. thus
: the case you given out has prob 0 of happenning.
:
: bus
: types
|
i****l
发帖数: 135 | 18 翻了一下，原来我笔记上面的题是这样的，记错了，呵呵……
buses arrive accordint to a poisson process with rate = 1 bus/20min.
passenger arrive at some arbitrary point in time. what's the waiting time?
没仔细算，但好像是 uniform 和 poisson 算法起来不一样。
ea
the
【在 H*M 的大作中提到】
: 1. 一个公车站，有两路车，一路每5分钟一班，一路10分钟一班
: 你刚看到有辆车通过（不知道哪路），问，间隔下一辆车到来的时间的期望值是多少？
: 2. 招聘问题。 decide一个策略使得招到最牛的人的概率最大。
: 1. There is a single secretarial position to fill.
: 2. There are n applicants for the position, and the value of n is known.
: 3. The applicants can be ranked from best to worst with no ties.
: 4. The applicants are interviewed sequentially in a random order, with ea
: ch order being equally likely.
: 5. After each interview, the applicant is accepted or rejected.
: 6. The decision to
|
