珍珠湾ART

标题: 一副奇怪的扑克牌 [打印本页]
作者: ob    时间: 2006-4-1 08:57
标题: 一副奇怪的扑克牌

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

 
作者: 有空想想    时间: 2006-4-1 20:42
标题: 可不可以问“大于”“小于”

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




作者: ob    时间: 2006-4-1 22:25
标题: Yes

  Yes




作者: 有空想想    时间: 2006-4-1 23:45
标题: 回复：Yes

可用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)www.ddhw.com
No[cover 21 cards]---->=5? 
          Yes[cover 11 cards]--->5?
                    Yes[cover 6 cards]---(6)
                    No[cover 5 cards]----(5)www.ddhw.com
          No[cover 10 cards]---->3?
                    Yes[cover 4 cards]---(4)
                    No[cover 6 cards]---->2?www.ddhw.com
                                 Yes[cover 3 cards]---(3)
                                 No[cover 3 cards]---->1?www.ddhw.com
                                            Yes[cover 2 cards]---(2)
                                            No[cover 1 card]-----(1)
 
www.ddhw.com

 




欢迎光临 珍珠湾ART (http://zzwav.com/) Powered by Discuz! X3