leetcode374：猜数字大小（guess-number-higher-or-lower）

[carloscn]

问题描述：

_guess-number-higher-or-lower_374

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num 1：我选出的数字比你猜的数字大 pick > num 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num 返回我选出的数字。

示例 1： 输入：n = 10, pick = 6 输出：6

示例 2： 输入：n = 1, pick = 1 输出：1

示例 3： 输入：n = 2, pick = 1 输出：1

示例 4： 输入：n = 2, pick = 2 输出：2  

提示： 1 <= n <= 231 - 1 1 <= pick <= n

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/guess-number-higher-or-lower

[carloscn]

问题分析

问题描述的比较复杂，实际上简化之后的意思是，给定选定值p，范围值n，p是n内的任意数字，要求找出p值。我们可以用递归和二分法结合的方法来解决该问题，猜大了减去自身的二倍，猜小了加上自身的二倍。

static int64_t pick_num = 0;

static void rec_guess(int64_t k, int64_t n)
{
    if (k == pick_num) {
        return;
    }
    k = k + ((k > pick_num) ? (-1 * k / 2) : (k / 2));
    LOG("the guess value is %ld\n", k);
    rec_guess(k, n);
}

static int64_t return_guess(int64_t n)
{
    rec_guess(n/2, n);
}

[carloscn]

code：

https://github.com/carloscn/structstudy/blob/master/c_programming/common/13_guess-number-higher-or-lower_374.c

result：