Write a program that asks the user to think of an integer between 1 and 1,000,00
ID: 3545790 • Letter: W
Question
Write a program that asks the user to think of an integer between 1 and 1,000,000 and then guesses the number through a series of yes/no questions. To guess the number, the program calls a recursive function guess that has two parameters low and high. The precondition for the function requires that the user's number lie in the range low...high so that the program's initial call is to guess(1,1000000). What is a good, stopping case for guess, when it can guess the user's number with little or no work? Answer: if(low==high), then there is only one possible number, and the function can guess that number. On the other hand, if (low<high), then the function should calculate a point near the middle of the range.
midpoint= (low + high) / 2;
then the function asks the user whether the midpoint is the correct number. If so, the function is finished. On the other hand, if the midpoint is not the user's number, then the function asks whether the correct number is larger than midpoint. If so, the function knows that the user's number lies in the range midpoint+1 to high, and a recursive call can be made to solve the smaller problem of findinga users number in the range midpoint + 1 to high. On the other hand, if the user's number is not larger than midpoint, then a recursive call can be made to solve the smaller problem of finding a user's number in the range low to midpoint -1. This method of searching is called binary search.
Explanation / Answer
/**The basic structure of the program is same, just the input/output options are different from the previous JAVA program. Please let me know if you have any doubt in this **/
#include <iostream>
using namespace std;
void search(int low, int high){
if(low == high) cout<<"We believe that you guessed "<<low<<", provided that you picked a number within the given range"<<endl;
else if(low < high){
char ch;
int midpoint = (low+high)/2;
cout<<"Did you Guess "<<midpoint<<"?(y/n)";
cin>>ch;
if(ch == 'Y' || ch =='y') {
cout<<"Congrats! we guessed the number correctly as "<<midpoint<<endl;
}
else{
cout<<"Did you Guess a number higher than "<<midpoint<<"?(y/n)";
cin>>ch;
if(ch == 'Y' || ch =='y') {
search(midpoint+1,high);
}
else if(ch == 'n' || ch == 'N'){
search(low,midpoint-1);
}
}
}
}
int main()
{
cout << "Guess a Number between 1 and 1,000,000" << endl;
search(1,1000000);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.