Random number problem

Hello, I have been solving this problem and i seem to be stuck. The idea is to get the computer to guess the user selected number and computer should guess it correct in 7 or less tries. Most time i get 7 or under times, but sometimes it's more, like 10 or 9 tries. I would appreciate help. Thanks :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

int main(){

int user_choice=0;
int computer_guess;
int high=100;
int low=1;
int c=0;


cout<<"Enter your number"<<endl;
cin>>user_choice;
srand(time(0));
while(computer_guess!=user_choice){

    //(rand()%(high-low))+ low;

    computer_guess=rand()%(high-low+1)+low;



    cout<<"Computer guess is : "<<computer_guess<<endl;


   if(computer_guess>user_choice){ //The logic is to decrease the guessing interval by the guessed number and all lower numbers or guessed number and all higher numbers
        high=computer_guess-1;
   }
   if(computer_guess<user_choice){
        low=computer_guess+1;
   }

c++;
}
cout<<"Computer took: "<<c<<" tries"<<endl;

return 0;
}
The most efficient way to guess a number within a range is to divide the subset of possible answers in half each iteration. This type of technique can be seen in many places in computer science algorithms, such as sorting or mathematical transforms (FFT), and is known as "divide and conquer" https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

I'll give an example.

Say the number to guess is within the range 1-100, as you have it, and the number generated is 65.

On the first iteration, all options are equally possible. So what you should do is guess 50, because that will divide your set in half, which is, on average, the best way to remove the most possibilities at once.

The guess (50) was lower than the actual number (65), so the new low is 51, and your new range is [51, 100].
Now, your next guess should be the new halfway point: (51+100)/2 rounded, or 76.
76 is greater than 65, so the new high is 75.
Your range is now [51, 75].

Rinse and repeat... the maximum amount of iterations you should have to perform is log2(100) ("log base 2 of 100" or ~6.64), rounded up to 7 iterations. Why log2(100) though? Because that's the number of halvings it takes to get from 100 to 1: 50, 25, 12.5, 6.25, 3.125, 1.5625, 0.78125.

It can also be easier to think of it in binary.

01111111    127 = 27-1
00111111     63 = 26-1
00011111     31 = 25-1
00001111     15 = 24-1
00000111      7 = 23-1
00000011      3 = 22-1
00000001      1 = 21-1


tl;dr -- always guess the half-way point between the current range.
Last edited on
Registered users can post here. Sign in or register to post.