1.4.34

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

第一种方案,类似于二分查找,先猜测左边界(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 类

using System;

namespace _1._4._34
{
    /// <summary>
    /// 某次猜测的结果。
    /// </summary>
    enum GuessResult
    {
        Hot = 1,        // 比上次猜测更接近目标。
        Equal = 0,      // 猜中目标。
        Cold = -1,      // 比上次猜测更远离目标。
        FirstGuess = -2 // 第一次猜测。
    }

    /// <summary>
    /// 游戏类。
    /// </summary>
    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)
        {
            Random random = new Random();
            this.N = N;
            this.SecretNumber = random.Next(N - 1) + 1;
            this.LastGuess = -1;
        }

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

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

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

之后是实际测试的方法:

using System;

namespace _1._4._34
{
    /*
     * 1.4.34
     * 
     * 热还是冷。
     * 你的目标是猜出 1 到 N 之间的一个秘密的整数。
     * 每次猜完一个整数后,你会直到你的猜测距离该秘密整数是否相等(如果是则游戏结束)。
     * 如果不相等,你会知道你的猜测相比上一次猜测距离秘密整数是比较热(接近),还是比较冷(远离)。
     * 设计一个算法在 ~2lgN 之内找到这个秘密整数,然后设计一个算法在 ~1lgN 之内找到这个秘密整数。
     * 
     */
    class Program
    {
        /// <summary>
        /// 某种方案的测试结果,包含猜测结果和尝试次数。
        /// </summary>
        struct TestResult
        {
            public int SecretNumber;// 猜测到的数字。
            public int TryTimes;// 尝试次数。
        }

        static void Main(string[] args)
        {
            Game game = new Game(1000);
            TestResult A = PlayGameA(game);
            game.Restart();
            TestResult 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}");
        }

        /// <summary>
        /// 方案一,用二分查找实现,需要猜测 2lgN 次。
        /// </summary>
        /// <param name="game">用于猜测的游戏对象。</param>
        /// <returns>返回测试结果,包含猜测结果和尝试次数。</returns>
        static TestResult PlayGameA(Game game)
        {
            TestResult result;
            result.TryTimes = 0;
            result.SecretNumber = 0;
            GuessResult guessResult;

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

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

                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;
                }
                else if (guessResult == GuessResult.Hot)
                {
                    lo = mid;
                }
                else
                {
                    hi = mid;
                }
            }

            return result;
        }

        /// <summary>
        /// 方案二,根据 (lastGuess + nowGuess)/2 = (lo + hi) / 2 确定每次猜测的值。
        /// </summary>
        /// <param name="game">用于猜测的游戏对象。</param>
        /// <returns>返回测试结果,包含猜测结果和尝试次数。</returns>
        static TestResult PlayGameB(Game game)
        {
            TestResult result;
            result.TryTimes = 0;
            result.SecretNumber = 0;
            GuessResult guessResult;

            int hi = game.N;
            int lo = 1;
            bool isRightSide = true;

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

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

                guessResult = game.Guess(nowGuess);
                result.TryTimes++;
                if (guessResult == GuessResult.Equal)
                {
                    result.SecretNumber = nowGuess;
                    break;
                }
                else 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;
        }
    }
}
上一题 下一题