在数学吧里看到的一个猜数游戏..给定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 追答： 我认为你的理解有问题，猜到了就是猜到了，总不能说要之后确认了对了才算对，对了游戏立即结束 下面是最初的次数个数字个数的对应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代入相减，得到一个没有常数项的式子，然后用特征根求，就不写了~