珍珠湾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