一起 学习 一下, 为 以后 少交点 学费 做准备。
m种颜色, n双袜子问题。
假设 第 x 次 后, 取到 第 n 双 y 颜色 的 袜子 ,则:
1) x-1次及之前取到的都没有 n双 ,任意组合 前面 取 袜子的顺序不影响最后第x次取才取到n双 的 结果 。
2) 前面 成双 的 颜色的袜子 有 2(n-1) 只 。
3) y颜色的袜子 除去 成双的袜子(成双数可能为0) 还有1只单独的。
根据前面 3个推论,有:
x-1的次数最少为 : 成双的 袜子 次数 2(n-1) ,加上 y颜色的 1只。
最多为: 成双的 袜子 次数 2(n-1) ,加上 y颜色的 1只,加上其他颜色各1只。
因此, 最好的情况 x-1=2(n-1)+1,即 x=2n。
最坏的情况 x-1=2(n-1)+1+(m-1), 即 x=2n+m-1。
可以扩展一下,问小孩子, 这n双成双的袜子是同一种颜色, 2种颜色,3种颜色,。。 会影响 最坏情况的次数么?
引用:
原帖由 winy_c 于 2010-5-21 09:38 发表 
昨天晚上看到这个帖子把答案抄到作业上去了,却没来得及仔细看题解。
今天再来学习,总算...总算...看懂了:此类题的“通项式”是:(m-1)+2n (其中,m为颜色数,n为袜子的双数)。
谢谢~~
.