作业帮 > 数学 > 作业

在"数学吧"里看到的一个猜数游戏..

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/03/29 20:02:18
在"数学吧"里看到的一个猜数游戏..
给定1到n的一个整数,猜这个数是多少,每猜一次就可以知道所猜的数是大了还是小了.
现在由于种种原因,无法立刻知道所猜的数是大了还是小了,要猜了下一个数才可以知道上一个数是大了还是小了.
举个例子:猜1到10的一个数
猜数``回答
`5````无
`8```5大了
`3```8大了
`2```3小了
`4```2小了
`4```4对了
共猜了6次
在这种情况下,应采取什么样的策略才可以尽可能减少猜的次数?
在最好的策略下,对于1到n的范围,至多猜多少次保证猜对?
在回答中,看到有人说使用黄金分割法,楼主也说可以先试1~12,猜五次看看.
然而我不太理解如何使用黄金分割发来解答这题,以及我尝试找出1~12最快并保险的方法,但怎么算都是7次.
因此希望有人能够说明一下这题.
【俊狼猎英】团队为您解答~
还是以1~12为例,如果算上把数准确猜出的那次,需要6次
也不用黄金分割,就用1/3,2/3位置就可以了
第一次4,第二次9,这时如果4的情况
因为5~8有4个数,10~12有3个,因此在4~9中间猜,9是下一个验证的位置,因此猜6
如果>9则猜11,在猜出第五个的时候即可唯一确定
如果
再问: >v< 我也是这么算的..不过按照原题的意思看的话,应该是4,9,6,11,10,12,12..所以还是七次... 不过原题的第二问"在最好的策略下,对于1到n的范围,至多猜多少次保证猜对?" 让我很困扰, 我尝试了3个数字~12个数字的情况, 分别从猜4次增加至猜7次..所以我在想这个"猜多少次保证猜对"是一个数值还是一个公式..... 数值我在想应该不是的,但公式又不知道该怎么得出...
再答: 我认为你的理解有问题,猜到了就是猜到了,总不能说要之后确认了对了才算对,对了游戏立即结束 下面是最初的次数个数字个数的对应1-1 2-2 4-3,这应该没什么问题 然后把未知的问题转换成已知的问题,设n次猜最多可以判断a[n]个数 则a[n+1]=a[n]+a[n-1]+1 第一次猜一个数,数左边留a[n-1]个数,数右边留a[n]个数,再加上猜的数本身,即a[n+1]=a[n]+a[n-1]+1;无论如何,第二次猜都按照a[n]个数的猜法,在右边a[n]个数中猜 如果第二次验证比第一个数小,那么a[n-1]个数用n-1次即可;如果第二次验证比第一个数大,那么从第二次开始,一共有n次机会,a[n]个数;如果正好是猜的数就不用说了 用数学归纳法,可以证明猜n次最多可以判断a[n]个数 如果只是要找固定多少个数的算法,最好用递推,直接找到即可; 如果想要完整的通项公式,似乎很麻烦,应该可以用n和n+1代入相减,得到一个没有常数项的式子,然后用特征根求,就不写了~