SRM157 Div.2 Easy GuessTheNumber

相変わらずの習慣。

コレ書いたら宿題しよ〜っと。

ゆとり

PROBLEM STATEMENT
A popular guessing game is "Guess the number", where one 
person selects a number in a known range, and another 
person tries to guess that number. After each guess, the 
first person reveals
whether the guess was correct, too high or too low.

Pretty soon one learns the best strategy, which is to 
guess the middle number among those not yet ruled out. If 
there is no single middle number, then there are two 
numbers to choose from. In that case, we choose the 
smallest of those numbers.

The algorithm can be described like this:


Init lower and upper bound
Repeat
  x = (lower bound + upper bound)/2  (round down if 
necessary)
  Make guess x
  If x is too low, set lower bound to x+1
  If x is too high, set upper bound to x-1
Until x is correct


For instance, assume that the lower and upper bound 
initally are 1 and 9, respectively. The middle number in 
this range is 5. If this is "too low", the new bounds 
become 6 and 9. This range contains four numbers, and 
there is thus no single middle number. The two numbers in 
the middle are 7 and 8, and the smallest of these is 7, so 
our next guess then becomes 7.

Create a class GuessTheNumber which contains the method 
noGuesses which takes an int upper, the initial upper 
bound of the range (the inital lower bound is always 1), 
and an int answer, the number selected by the first 
person. The method should return an int representing the 
total number of guesses required for the second person to 
guess the correct number using the method described above.

こ〜ど

class GuessTheNumber {
   public:
   int noGuesses(int upper, int answer)
  {
	int low = 1;
	int mid;
	int i = 1;
	while (true) {
		mid = (int)((low+upper)/2);
		if (mid < answer) {
			low = mid+1;
		} else if (mid > answer) {
			upper = mid-1;
		} else {
			break;
		}
		i++;
	}
	return i;
  }
};