请教3道 brain teasers - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教3道 brain teasers

请教3道 brain teasers# JobHunting - 待字闺中

h*y2011-03-11 08:03

1 楼

1，八匹马赛跑，考虑到tie的情况，比赛结果共有多少种可能？
2，37！=****************abcdefgh0000000，请问字母代表的数字是多少，不许用计
算器。
3，一个环形路线上运行两种车，慢车和快车，慢车10分钟一圈，快车5分钟。当车绕完
一圈之后，随机决定下一次是快还是慢。问一个乘客随机的到轨道的任意地方，平均的
等车时间是多少?

c*n2011-03-11 08:03

2 楼

answer for the first question:
f(n, k) = k*f(n-1, k-1) + k*f(n-1, k)
f(n, 1) = 1
sum of f(n, k), k = 1,2,...n

h*y2011-03-11 08:03

3 楼

不好意思，还是不太明白
您说的这个n在这道题中是8？然后 k 是说这 8 匹马分成 k个level上（比如说k=1 相
当于所有的马在一个level上，i.e. 全部并列）？
能不能麻烦详细说说？
谢谢！～

【在 c*******n 的大作中提到】

: answer for the first question:
: f(n, k) = k*f(n-1, k-1) + k*f(n-1, k)
: f(n, 1) = 1
: sum of f(n, k), k = 1,2,...n

l*r2011-03-11 08:03

4 楼

这么做对么？首先考虑rank的8个位置，有P(8，8)= 8*7*6*5*4*3*2*1种可能。
然后每个星号可以取>或者=两个值，所以就是14种可能。
所以总的就是 14P(8,8)

【在 h******y 的大作中提到】

: 1，八匹马赛跑，考虑到tie的情况，比赛结果共有多少种可能？
: 2，37！=****************abcdefgh0000000，请问字母代表的数字是多少，不许用计
: 算器。
: 3，一个环形路线上运行两种车，慢车和快车，慢车10分钟一圈，快车5分钟。当车绕完
: 一圈之后，随机决定下一次是快还是慢。问一个乘客随机的到轨道的任意地方，平均的
: 等车时间是多少?

g*s2011-03-11 08:03

5 楼

1. 用dp吧: f(1)= 1，
f(2)= f(1) * 3 (新多出来的马相对上一组group的关系) = 3，
f(3)= f(2) * 3
..............
f(8)= f(7) * 3 = 3 ^ (8 - 1) = 3 ^ 7
2.神马思路都没有...........
3.先假设乘客正好在车离开的地方等，那么一就是辆车绕一圈的平均时间(10+5)/2 = 7
.5 ，再假设乘客正好在车到达的地方等，时间为0. 所以乘客在任意地方等的总平均时
间为 (7.5 + 0) / 2 ＝ 3.75?

h*y2011-03-11 08:03

6 楼

这个好像有点小问题
比如说马分别叫 A, B, C, D, E, F, G, H
显然在 P(8,8) 中（1） A, B, C, D, E, F, G, H 和（2） B, A, C, D, E, F, G,
H 是计算成两种不同情况的；如果A和B中间的星号取等号，那么，实际上（1）和（
2）是同一种情况，应该只算1次

【在 l*********r 的大作中提到】

:
: 这么做对么？首先考虑rank的8个位置，有P(8，8)= 8*7*6*5*4*3*2*1种可能。
: 然后每个星号可以取>或者=两个值，所以就是14种可能。
: 所以总的就是 14P(8,8)

h*y2011-03-11 08:03

7 楼

1. f(3) 按照这个算法是 9；但是如果3匹马竞赛，考虑tie的情况，应该有12种不同
的情况吧（我直接用列举算的）

7

【在 g*******s 的大作中提到】

: 1. 用dp吧: f(1)= 1，
: f(2)= f(1) * 3 (新多出来的马相对上一组group的关系) = 3，
: f(3)= f(2) * 3
: ..............
: f(8)= f(7) * 3 = 3 ^ (8 - 1) = 3 ^ 7
: 2.神马思路都没有...........
: 3.先假设乘客正好在车离开的地方等，那么一就是辆车绕一圈的平均时间(10+5)/2 = 7
: .5 ，再假设乘客正好在车到达的地方等，时间为0. 所以乘客在任意地方等的总平均时
: 间为 (7.5 + 0) / 2 ＝ 3.75?

c*e2011-03-11 08:03

8 楼

2，37！=****************abcdefgh0000000，请问字母代表的数字是多少，不许用计
算器。
Only know h should be 0, as 37! should have 8 '0' , (count 5, 15, 25, 25, 35
, 10, 20, 30)

d*e2011-03-11 08:03

9 楼

two 25?

35

【在 c******e 的大作中提到】

: 2，37！=****************abcdefgh0000000，请问字母代表的数字是多少，不许用计
: 算器。
: Only know h should be 0, as 37! should have 8 '0' , (count 5, 15, 25, 25, 35
: , 10, 20, 30)

b*e2011-03-11 08:03

10 楼

上个简单易懂的：
f(n) = C(n, 1) * f(n-1) + // 第一名的有一个
C(n, 2) * f(n-2) + // 第一名的有两个
... + // ...
C(n, n) * f(0) // 第一名的有n个

f(0) = 1

【在 h******y 的大作中提到】

k*a2011-03-11 08:03

11 楼

第一题（程序算得）
#马 #可能结果
2 3
3 13
4 75
5 541
6 4683
7 47293
8 545835
附我的R code:
totalfor (n in 2:8)
{
xxcountfor (i in 0:(2^(n-1)-1))
{
yposdifdifdifcount}
newtotal}

【在 h******y 的大作中提到】

h*y2011-03-11 08:03

12 楼

哈，这个太给力了，谢了～

【在 k*******a 的大作中提到】

: 第一题（程序算得）
: #马 #可能结果
: 2 3
: 3 13
: 4 75
: 5 541
: 6 4683
: 7 47293
: 8 545835
: 附我的R code: