Guessing Number in sequence

[hungrymouth]

Hello everyone,

I must reduce the number of iterations it takes the computer to guess my number. In this case, then number must be >= 1 and <= 100. I must reduce from O(n) time and get a better running time. If, for instance, if my number were to be 12, it would take 88 times to get my guess right... Maybe I could insert questions like "Is your number between 90 and 100 " and so on by reducing the interval of the number the machine is looking for, so when it asks "Is your number between 10 and 20?" The answer should be 'y' of 'Y', then the program should proceed and ask questions like "Is your number 20" ... "Is your number 12" and then you should answer 'y' or 'Y'... so I am doing this to reduce the number of iterations.

  // FILE: guess.cxx
// Demostrates a guessing game function that's used as a time analysis example.
#include <cassert>         // Provides assert
#include <iostream>        // Provides cout and cin
#include <cstdlib>         // Provides EXIT_SUCCESS
using namespace std;       // Allows all Standard Library items to be used
// Prototype for the function used in this demonstration program
void guess_game(int n);
// Precondition: n > 0.
// Postcondition: The user has been asked to think of a number between 1 and n.
// The function asks a series of questions, until the number is found.

int main( )
{
    guess_game(100);
    return EXIT_SUCCESS;
}
void guess_game(int n)
// Library facilities used: cassert, iostream
{
    int guess;
    char answer;
    assert(n >= 1);
    cout << "Think of a whole number from 1 to " << n << "." << endl;
    answer = 'N';
    // I have asked questions here with no success and same in the loop
    for (guess = n; (guess > 0) && (answer != 'Y') && (answer != 'y'); --guess)
    {
        cout << "Is your number " << guess << "?" << endl;
        cout << "Please answer Y or N, and press return: ";
        cin >> answer;
    }
    if ((answer == 'Y') || (answer == 'y'))
        cout << "I knew it all along." << endl;
    else
        cout << "I think you are cheating!" << endl;
}

I appreciate your help lots, Thank you!

[Disch]

You are correct in asking questions to narrow down the number. Though you probably want to do a binary search... that is... cut the number of possibilities in half with each question.

IE:

> 50? no (so you know it's <= 50)
> 25? yes (so you know it's between 25-50)
> 38? no (so you know it's between 25-38)
etc
etc

[giblit]

What I would do is ask if the number is less than or higher than. Then you could use a binary search and the number of iterations would be minimal.


Lets look at a range of 1-20 without binary search:

Answer we are looking for = 7

First guess 20

7 < 20

next guess 19

7 < 19
ect...

So it would take 13 guesses to get it right. With a complexity of O(n)


Now lets look at with binary search


Answer = 7

First guess = 20

7 < 20

next guess 10

7 < 10

next guess 5

7 > 5

next guess is 7

So it took 4 guesses to get the answer correct. IIRC the complexity is O(sqrt n) or maybe O(log2 n) think the latter now after thinking about it

Basically it is like this

L                 M                             R
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

L       M         R
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

        L   M     R
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

*EDIT Guess me and Disch had the same idea