一个逻辑的算法
二人游戏,甲从1-1024中预想一个数,乙问甲问题 甲只回答"是"或者"否",甲可以撒谎,但只有一次撒谎的机会,也可以不撒谎,请问乙至少问多少次才能猜出甲预想的数?这是一个逻辑的算法题,不是脑筋急转弯题,不恩给你凭运气得到答案。
谁能给出解决答案及详细的算法 --------------------编程问答-------------------- 口头表达的二分查找
撒谎是关键,很有可能会找错方向
--------------------编程问答-------------------- 急需答案。。。。。 --------------------编程问答-------------------- 一 备注
1 是否小于等于512 是 否 如果撒谎
2 是否小于等于256 是 否 这里必须回答否,第三问就再问第一问,肯定也回答否,就知道第一句说谎了,再问他关于>512的问题9次+3次=12次
3 是否小于等于128 是 否
4 是否小于等于64 是 否
5 是否小于等于32 是 否
6 是否小于等于16 是 否
7 是否小于等于8 是 否
8 是否小于等于4 是 否
9 是否小于等于2 是 否
10 是否小于等于1 是 否
二
1 是否小于等于512 是 否
2 是否小于等于256 是 否 如果撒谎
3 是否小于等于128 是 否 这里必须回答否,第四问就再问第二问,肯定也回答否,就知道第一句说谎了,再问他关于256->512的问题8次+4次=12次
4 是否小于等于64 是 否
5 是否小于等于32 是 否
6 是否小于等于16 是 否
7 是否小于等于8 是 否
8 是否小于等于4 是 否
9 是否小于等于2 是 否
10 是否小于等于1 是 否
以此类推这样行吗 总共12次
--------------------编程问答-------------------- 至少。。那就是1次咯,直接猜到,并且对面不说谎~ --------------------编程问答--------------------
X2就行了笨蛋哈哈哈,最简单的算法,虽然未必高效,就是每次都问他2遍
--------------------编程问答-------------------- 哦能问大于小于啊,那当我没说好了 --------------------编程问答-------------------- 最少2次。最理想的情况,猜测的人知道这个数字(1/1024的概率),并且连问2次,确认。
如果允许出错,最少0次。最理想的情况,猜测的人知道这个数字,无需提问确认。
最多无穷多次。 --------------------编程问答-------------------- 最少2次,最多2048次,不是1?,不是2?......每个数这样问2次 --------------------编程问答--------------------
乙问甲问题 甲只回答"是"或者"否",甲可以撒谎,但只有一次撒谎的机会
可以大于小于的好么? --------------------编程问答-------------------- console.writeline("至少询问2次")
补充:.NET技术 , 非技术区