手套选择 算法谜题

发布时间:2019-08-03 22:58     分类:算法谜题

在抽屉里有20只手套。其中,有5双黑手套,3双棕色手套和2双灰手套。你只能在黑暗中挑手套,并且只有将手套挑出来之后才能检查其颜色。最少要挑几次才能满足以下条件?

1、至少挑出一双颜色匹配的手套。

2、所有颜色的手套都至少挑出一双匹配的。

 

答案:问题1和问题2的答案分别是11和19.

1、最坏的情况是,在挑出至少一双匹配的手套之前,你已经挑出了5只黑手套、3只棕色手套和2只灰手套-----都是同一只手的。接下来挑出一只将必然会匹配出一双手套。因此,答案是11只。

2、最坏的情况是,在每个颜色中都挑出一双匹配的手套之前,你已经挑出了全部的十只黑手套,全部的6只棕色手套和2只同一只的灰色手套,接下来挑出的灰色手套将必然匹配,因此,答案是19只。

 

评论:这个谜题是一个队算法效率最坏情况分析的例子。

在绝大多数的谜题书中,此类问题的一种是不同颜色的球,不同颜色的手套,较之本题多了些额外的变化。

评论

推荐文章