1.4.34 #

解答 #

第一种方案，类似于二分查找，先猜测左边界(lo)，再猜测右边界(hi)，如果边界值猜中的话直接返回，否则：

如果右边界比较热，那么左边界向右边界靠，lo=mid；否则，右边界向左边界靠，hi=mid。其中，mid = lo + (hi – lo)/2。

每次二分查找都要猜测两次，~2lgN。

第二种方案，假设上次猜测值为 $lastGuess$，本次即将要猜测的值为 $nowGuess$，通过方程：

$(lastGuess + nowGuess)/2 = (lo + hi)/2$

可以求得 $nowGuess$，具体可以查看示意图：

数字是猜测顺序，黑色范围是猜测值的范围（$lastGuess$ 和 $nowGuess$），绿色的是实际查找的范围（lo 和 hi）。

代码 #

首先是 Game 类

internal class Game
{
    public int N { get; }                       // 目标值的最大范围。
    public int SecretNumber { get; }            // 目标值。
    public int LastGuess { get; private set; }  // 上次猜测的值

    /// <summary>
    /// 构造函数，新开一局游戏。
    /// </summary>
    /// <param name="n">目标值的最大范围。</param>
    public Game(int n)
    {
        var random = new Random();
        N = n;
        SecretNumber = random.Next(n - 1) + 1;
        LastGuess = -1;
    }

    /// <summary>
    /// 猜测，根据与上次相比更为接近还是远离目标值返回结果。
    /// </summary>
    /// <param name="guess">本次的猜测值</param>
    /// <returns>接近或不变返回 Hot，远离则返回 Cold，猜中返回 Equal。</returns>
    public GuessResult Guess(int guess)
    {
        if (guess == SecretNumber)
        {
            return GuessResult.Equal;
        }
        if (LastGuess == -1)
        {
            LastGuess = guess;
            return GuessResult.FirstGuess;
        }

        var lastDiff = Math.Abs(LastGuess - SecretNumber);
        LastGuess = guess;
        var nowDiff = Math.Abs(guess - SecretNumber);
        if (nowDiff > lastDiff)
        {
            return GuessResult.Cold;
        }

        return GuessResult.Hot;
    }

    /// <summary>
    /// 重置游戏，清空上次猜测的记录。目标值和最大值都不变。
    /// </summary>
    public void Restart()
    {
        LastGuess = -1;
    }
}

之后是实际测试的方法：

var game = new Game(1000);
var a = PlayGameA(game);
game.Restart();
var b = PlayGameB(game);
Console.WriteLine($"SecretNumber:{game.SecretNumber}");
Console.WriteLine("TestResultA:");
Console.WriteLine($"SecretNumber:{a.SecretNumber}, TryTimes:{a.TryTimes}");
Console.WriteLine();
Console.WriteLine("TestResultB:");
Console.WriteLine($"SecretNumber:{b.SecretNumber}, TryTimes:{b.TryTimes}");

// 方案一，用二分查找实现，需要猜测 2lgN 次。
static TestResult PlayGameA(Game game)
{
    TestResult result;
    result.TryTimes = 0;
    result.SecretNumber = 0;

    var hi = game.N;
    var lo = 1;

    // 利用二分查找猜测，2lgN
    while (lo <= hi)
    {
        var mid = lo + (hi - lo) / 2;

        var guessResult = game.Guess(lo);
        result.TryTimes++;
        if (guessResult == GuessResult.Equal)
        {
            result.SecretNumber = lo;
            return result;
        }

        guessResult = game.Guess(hi);
        result.TryTimes++;
        if (guessResult == GuessResult.Equal)
        {
            result.SecretNumber = hi;
            return result;
        }

        if (guessResult == GuessResult.Hot)
        {
            lo = mid;
        }
        else
        {
            hi = mid;
        }
    }

    return result;
}

// 方案二，根据 (lastGuess + nowGuess)/2 = (lo + hi) / 2 确定每次猜测的值。
static TestResult PlayGameB(Game game)
{
    TestResult result;
    result.TryTimes = 0;
    result.SecretNumber = 0;

    var hi = game.N;
    var lo = 1;
    var isRightSide = true;

    // 第一次猜测
    var guessResult = game.Guess(1);
    result.TryTimes++;
    if (guessResult == GuessResult.Equal)
    {
        result.SecretNumber = 1;
        return result;
    }

    while (lo < hi)
    {
        var mid = lo + (hi - lo) / 2;
        var nowGuess = (lo + hi) - game.LastGuess;

        guessResult = game.Guess(nowGuess);
        result.TryTimes++;
        if (guessResult == GuessResult.Equal)
        {
            result.SecretNumber = nowGuess;
            break;
        }

        if (guessResult == GuessResult.Hot)
        {
            if (isRightSide)
            {
                lo = mid;
            }
            else
            {
                hi = mid;
            }
        }
        else
        {
            if (isRightSide)
            {
                hi = mid;
            }
            else
            {
                lo = mid;
            }
        }

        isRightSide = !isRightSide;
        if (hi - lo <= 1)
        {
            break;
        }
    }

    if (game.Guess(lo) == GuessResult.Equal)
    {
        result.TryTimes++;
        result.SecretNumber = lo;
    }
    else if (game.Guess(hi) == GuessResult.Equal)
    {
        result.TryTimes++;
        result.SecretNumber = hi;
    }

    return result;
}

/// <summary>
/// 某种方案的测试结果，包含猜测结果和尝试次数。
/// </summary>
internal struct TestResult
{
    public int SecretNumber; // 猜测到的数字。
    public int TryTimes; // 尝试次数。
}