SRM 157 DIV2 Level One - 数当てゲーム

C++ TopCoder

プログラミング始めた頃に作った気がする。


数当てゲームは、100個の数字の中からランダムに数字を選んで数を当てるゲーム。


もうちょっと簡単にして、上限が9答えが6だとすると、

  • 1〜9までの真ん中(1 + 9)/2の5を選ぶと、上です。と出る。
  • 5は選んだから一個増やして、6〜9までの間の半分(6 + 9)/2で7。下です。と出る。
  • 7は選んだから一個減らして、6〜6で、(6 + 6)/2で6。

3回で正解に辿りついた。

で、上限と回答が与えられるから、何回で答えられるか数えると。


二分検索の問題ですね。


1000までやっても、そんなにメモリを食わないので再帰で・・・と思ったら演算子の優先順位でハマリまくり。

class GuessTheNumber
{
private:
    static int guesses(int lower, int upper, int answer)
    {
        int res = (lower + upper) / 2;

        return (res == answer) ? 1 :
                                 1 + ((res > answer) ? guesses(lower, res - 1, answer) :
                                                       guesses(res + 1, upper, answer));
    }
public:
    static int noGuesses(int upper, int answer)
    {
       return guesses(1, upper, answer); 
    }
};

条件演算子の優先順位は結構低い。


演算子の優先順位なんてキライダ。全部括弧付けちゃいなよ。