Question

程序编程题。求助，求大神帮忙。

A从1-100里面选一个数让B猜，如果B猜的数比A的小了，A就会提示他小了。一旦B猜的数字比A的数字大，A就只回答对还是不对，自此以后，无论B猜大了还是猜小了，A都不会提示，只回答对还是不对。请问B至少猜多少次才能才对，第一个数字应该猜数字几。说下思路。求大神帮忙。

Answer 1

猜14次，先猜14
我的思路是这样：
设fun(n)表示一共n个数需要猜的次数
猜数字的方法如下：
假设第一个数猜a1，如果a1大了，那么以后每次-1，如果a1小了，那么还需要猜 f(n-a1)次。以a1做分界，如果左边和右边猜的次数相同或只差1，那么就是最好的策略。
左边猜的次数是a1-1，右边猜的次数是f(n-a1)
下面依次递推：
1个数，猜1次
那么要猜2次的最大个数可以这样构造：
在这1个数左边添加1个数
再在左边添加 f(1)个数
这样先猜第一次添加的那个数，然后无论是大了还是小了都只用再猜1次

同理，假设猜n次，最大个数为x（x+1个数就要猜n+1次），即f(x)=n
那么，要猜n+1次才能猜对的最大个数应该这样构造：
在这 x 个数左边添加一个数
再在左边添加 n 个数
这样，先猜添加的那一个数，然后无论是大是小都只用再猜 n 次

以上是思路，下面附C++代码
#include<iostream>
using namespace std;

int fun(int n) //用来判断n个数需要猜多少次
{
if(n<=0)
return 0;
if(n==1)
return 1;
int times=1; //times初始化为1个数需要猜的次数
for(int i=1;i<n;)
{
i = i + 1 + times; //i表示猜times次的最大的数，初始化为猜1次最大的个数——1
//如果n比这个数大，那么构造下一个最大个数，同时times++
times++;
}
return times;
}

int main()
{
printf("%d",fun(100));
getchar();
}

追问

能举个例子嘛。我没看懂你的思路。“1个数，猜1次
那么要猜2次的最大个数可以这样构造：
在这1个数左边添加1个数
再在左边添加 f(1)个数
这样先猜第一次添加的那个数，然后无论是大了还是小了都只用再猜1次”，这个简单说是什么意思。举个例子可以么？大神。

追答

现在有下面一列数：
1 2 3 4 5 6
那么至少猜3次就一定可以猜对是不是？先猜3，如果3大了就依次猜2 1，如果小了就猜5，然后就猜出来了。
也就是猜三次一定可以猜出6个数中的一个数，那么猜4次一定可以猜出多少个数中的某个数呢？
如果是7个数

1 2 3 4 5 6 7，那么先猜1，然后如果1小了，右边6个数按照上述方法3次一定能猜对，总计4次
1 2 3 4 5 6 7 8，先猜2，然后如果2大了，就猜1，小了右边的数3次也能猜出来
……
1 2 3 4 5 6 7 8 9 10，先猜4，如果4大了，以此向左边猜，3次可以猜出来，如果4小了，右边一共6个数，3次也能猜出来，所以10个数猜4次一定能猜出来。
而1 2 3 4 5 6 7 8 9 10 11这组数不管先猜4还是5，总有一边要猜4次才行

接着说构造的问题：
有一列数：5 6 7 8 9 10,共6个数，知道猜3次就可以猜出来
那么猜4次可以猜出的数列的长度是多少？
就先任意选一个数（第一次猜的数），比如 10，那么如果10大了，就在10左边添加比10小的三个数（如依次猜9 8 7），共猜4次。
如果10小了，就在10右边添加比10大的6个数，10右边的数也能3次猜对，共计4次
所以4次能猜对的数列的长度 = 3 + 1 + 6
即是 f(4)=3 + 1 + f(3)

Answer 2

用的是什么语言