设为首页 加入收藏

TOP

笔试题:1—100猜数字
2014-10-30 18:30:03 来源: 作者: 【 】 浏览:37
Tags:试题 100 数字

问题描述:
小明在[1,100]之间猜数字。规则如下:
1、如果猜的笑了,会提示小明猜的小了。
2、如果猜的大了,只会提示对错,不会提示大小。
3、如果有一次猜的大了,以后猜的无论大小,都只会提示错误,不会提示大小。
问:至少几次可以猜对数字?第一次应该猜那个数字?
解答如下:
假设你猜的第一个数字是x。
那么最少次数最小也要为x,因为第一次如果猜的大了,会提示你猜的大了,你可以确定正确数字的范围是[1,x-1],所以,你最坏需要再猜x-1次,总共也就是x次。如果你第一次猜小了,会提示你猜的小了,你可以确定正确数字的范围是[x+1,100],接下来,你需要猜第二次,同样面临的是猜大还是猜小,猜第二次的时候,你所要关心的问题应该是如果猜的大了,在最坏的情况下,要猜对所需要的次数应该小于等于x-1。正因为如此,你第二次所要猜的数字,最大应该为x+(x-1)。如果猜的比2x-1小的话,可以保证第二次猜的次数小于等于x-1,但从总体考虑,如果第二次猜的数字小于2x-1的话,会增加后面猜的次数。为了最后结果的最优,所以第二次应该猜的数字为2x-1。以此类推,步长每次都比上一次少一次。
下面就是解x的值。猜的次数肯定不能为负数。所以
1+2+3+4+5+……+x=x(x+1)/2>100
最小次数就是上面不等式解的最小正整数,结果为14次,第一次猜14


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇10亿用户200万商品,已知每个用户.. 下一篇今天去UC面试回来了

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: