一副奇怪的扑克牌

ob · 发表于 2006-4-1 08:57:51

有一副奇怪的扑克牌，共有45张，1点（A）有1张：2点有2张......9点有9张。搅和以为背面放在桌上，让某人来秘密地抽一张。你问他几个问题，他只回答是或非，设法把他手中的点数问出来。你怎样使你必须问的问题数目尽可能地少？请注意，我们要找的是无论他选到什么牌都能问出的通用程序。如你设计的第一个问题是：“你的牌是不是5点？”那么当他的牌正是5点时，你一次就问出来了。但这不是通用程序，因为如若不是5点，你的第一个问题起的作用就太小了。

有空想想 · 发表于 2006-4-1 20:42:04

可不可以问“大于”“小于”

ob · 发表于 2006-4-1 22:25:22

Yes

有空想想 · 发表于 2006-4-1 23:45:17

可用binary search.

但用binary search 时，最好两边的可能性一样多。所以可以从7 问起。如下：

（最多用5步，谁有空算算期望步数吧。）

>＝ 7 ?

Yes[cover 24 cards]--->＝8?

Yes[cover 17 cards]--->8?

Yes[cover 9 cards]---(9)

No[cover 8 cards]---->(8)

No[cover 7 cards]----(7)

No[cover 21 cards]---->=5?

Yes[cover 11 cards]--->5?

Yes[cover 6 cards]---(6)

No[cover 5 cards]----(5)

No[cover 10 cards]---->3?

Yes[cover 4 cards]---(4)

No[cover 6 cards]---->2?

Yes[cover 3 cards]---(3)

No[cover 3 cards]---->1?

Yes[cover 2 cards]---(2)

No[cover 1 card]-----(1)

		自动登录	找回密码
密码			立即注册

动态微博

一副奇怪的扑克牌

可不可以问“大于”“小于”

Yes

回复：Yes