1

Why are my numbers not calculating correctly? My teacher wouldn't give me more help because he thought it was close enough to his output. But I'm not satisfied. First of all here is my finished code:

#include <iostream>
using namespace std;

void playOneGame();
char getUserResponseToGuess(int);
int getMidpoint(int, int);
bool shouldPlayAgain();

int main()
{
  do
  {
    playOneGame();
  } while (shouldPlayAgain());

  return 0;
}

void playOneGame()
{
  int min = 0;
  int max = 100;
  int num;
  char answer;
        
  cout << "Think of a number between 1 and 100." << endl;
  num = getMidpoint(min, max);
  answer = getUserResponseToGuess(num);
  
  while(answer != 'c')
  {
    if(answer == 'l')
    {
      max = num;
      max--;
      num = getMidpoint(min, max);
      answer = getUserResponseToGuess(num);
    }
    else if(answer == 'h')
    {
      min = num;
      min++;
      num = getMidpoint(min, max);
      answer = getUserResponseToGuess(num);
    }
  }
}

bool shouldPlayAgain()
{
  char playAgain;
  
  cout << "Great! Do you want to play again? (y/n): ";
  cin >> playAgain;
  
  if(playAgain == 'y')
  {
    return true;
  }
  else
  {
    return false;
  }
}

char getUserResponseToGuess(int guess)
{
  char input;
  cout << "Is it " << guess << "? (h/l/c):";
  cin >> input;
  
  return input;
}

int getMidpoint(int low, int high)
{
  double midP = (low + high) / 2;
  return midP;
}

This is the expected output:

Think of a number between 1 and 100

Is the number 50? (y/n/c): h

Is the number 75? (y/n/c): l

Is the number 62? (y/n/c): h

Is the number 69? (y/n/c): h

Is the number 72? (y/n/c):

This is the output MY program gets:

Think of a number between 1 and 100

Is the number 50? (y/n/c): h

Is the number 75? (y/n/c): l

Is the number 62? (y/n/c): h

Is the number 68? (y/n/c): h

Is the number 71? (y/n/c):

I just want to know why my numbers aren't calculating correctly. As you can see it is not by a huge difference but it still bothers me! I also can't change the int parameters, they must be ints!

Community
  • 1
  • 1
andreaq
  • 17
  • 5
  • Why did you expect it to round up? And how do you believe it impacts the function of the algorithm? You are doing a binary search either way. – patatahooligan Apr 05 '18 at 16:21

2 Answers2

1

When min is 62 and max is 75, mid is computed as (62 + 75)/2, which is 137/2. When you compute that using (low + high)/2, integer math is used to find the result, which is 68. It's not clear to me why you expect it to be 69.

double midP = (low + high) / 2;  // midP is 68, not 68.5
return midP;

Even if you change that to use floating point arithmetic,

double midP = 0.5*(low + high);  // midP is 68.5
return midP;

when it is returned from the function, it will be truncated since the return type of the function is int.

R Sahu
  • 204,454
  • 14
  • 159
  • 270
  • I expect it to be 69 because my teacher's sample output is that. They weren't really worried because it is not off by a lot but I was a bit frustrated that they wouldn't care to explain more. Thank you for explaining! – andreaq Apr 05 '18 at 16:43
0

The expression (low + high) / 2 is an integer, any fractional component is discarded. We call this integer arithmetic.

If you want to round such that an odd number value of low + high rounds up, then you could use

double midP = std::round(0.5 * (low + high));

My use of 0.5 forces the argument of std::round to be a double type. There are some hidden depths in this: for an IEEE754 double precision type, this multiplication of 0.5 will be exact up to the 52nd power of 2, and std::round will work perfectly in that range. Binary floating point arithmetic is a very complex topic. For an introduction, see Is floating point math broken?.

Reference http://en.cppreference.com/w/cpp/numeric/math/round

Bathsheba
  • 231,907
  • 34
  • 361
  • 483