CS1101C Lab 3 (Odd Week)
Intelligent Number Guesser
The deadline for this lab question is Wednesday 12 October 2005,
23:59:59 hours.
The name of your C program file must be called guess.c,
files with any other name will not be marked.
Background
Nemo and Dory are at it again. You are a born-again shark who has gone
vegetarian. You are swimming nearby and you eavesdrop on their
conversation:
Dory: “Let’s play a number guessing game.”
Nemo: “Err...”
Dory: “Come on, it’ll be lots of fun!”
Nemo: “Ok ok... what is it?”
Dory: “I’ll think of a secret random number between 1 too
100 inclusive, and you have to guess it. After each guess, I’ll
tell you whether it is too high, too low, or correct. We’ll see
how many guesses you’ll take.”
Nemo: “Ok... but no cheating ok?”
Dory: “Ok, promise. I’ve thought of a random number.
Shoot!”
Nemo: “50.”
Dory: “Too low.”
Nemo: “75.”
Dory: “Too high.”
Nemo: “63.”
Dory: “Too low.”
Nemo: “69.”
Dory: “Too high.”
Nemo: “66.”
Dory: “Too high.”
Nemo: “65.”
Dory: “Correct! You took 6 guesses. This is so much fun. Shall we
play again?”
Nemo: “Hey, I know of a way that we can speed things up! I have a
shark friend who is learning Programming Methodology and he/she can
write a program for us! For each experiment, we just tell him/her the
random number seed we want, minimum and maximum possible values of the
secret number, and the number of simulations. The program can then tell
us the average number of guesses for the experiment. Is that cool or
what?”
Dory: “Cool...”
As proof of your born-again behavior, you step out from the shadows.
After giving them the fright of their life, as Nemo’s friend, you
offer your services once again.
Intelligent Guessing
If you examine Nemo’s pattern of guessing more closely, you
realize that he is not as dumb as he looks. His first guess is:
- (Min + Max) / 2 = (1 + 100) / 2 = 50. (after adjustment;
rounding down or rounding up (a guess of 51) are both acceptable).
Since this was too low, his second guess is:
Since this was too high, his third guess is:
- (50 + 75) / 2 = 62. (after adjustment; rounding down or rounding
up (a guess of 63) are both acceptable).
And so on. Do you see a pattern? Identify it and think about how you
would write the algorithm for intelligently guessing a random integer.
Implementation
You will be provided with an input file consisting of different
experiment scenarios. Each line in the input file gives the parameters
for a single experiment. Each experiment typically contains many
simulations (100, 1,000, or possibly more). A typical line from the
input file consist of four integers separated by blank spaces as shown
below:
122 1 100 1000
The explanation for each number is given as follows:
122 | Random number seed
|
1 | Minimum value for secret number
|
100| Maximum value for secret number
| 1000 | Number of simulations
| |
This says that for this particular experiment, the random number seed is
122, the minimum value for the secret number is 1,
the maximum value for the secret number is 100, and we wish to
carry out 1,000 simulations.
An Experiment
We illustrate how the experiment is performed for the above. First, we
initialize the random number seed to 122. The random number seed
should be initialized only at the beginning of each experiment; not in
between simulations. For the above experiment, we need to conduct
1,000 simulations.
A Simulation
We illustrate how a single simulation is performed using the parameters
given above. First, we choose a secret number which is a random integer
between 1 to 100 inclusive. Then, we keep simulating
Nemo’s guesses by intelligently guessing the secret number. We
also simulate Dory’s truthful responses (too high / too low /
correct) to Nemo. We take note of the number of guesses Nemo takes to
guess each secret number.
Experiment Data
After running 1,000 simulations, we calculate the average number
of guesses taken by Nemo to guess each random secret number correctly,
and display it rounded off to three decimal places.
Input File
Assume that the text input file is always called number1.txt. This sample input file
contains data for seven experiments:
121 1 100 100
122 1 100 1000
123 1 100 10000
123 2 101 10000
123 -49 50 10000
124 1 1000 10000
125 1 10000 10000
We will test your program with other experiment data, so your program
must work for the general case, and not just only for the sample input
file given.
Sample Run
The following shows a sample run for the input file numbers1.txt. Actual values for the
average number of guesses have been replaced with x’s.
You are reminded to follow the sample outcome exactly, else marks will
be deducted.
Seed: 121, min: 1, max: 100, average number of guesses: x.xxx.
Seed: 122, min: 1, max: 100, average number of guesses: x.xxx.
Seed: 123, min: 1, max: 100, average number of guesses: x.xxx.
Seed: 123, min: 2, max: 101, average number of guesses: x.xxx.
Seed: 123, min: -49, max: 50, average number of guesses: x.xxx.
Seed: 124, min: 1, max: 1000, average number of guesses: x.xxx.
Seed: 125, min: 1, max: 10000, average number of guesses: xx.xxx.
Take Note
- Note that the minimum and maximum values of the secret number may be
negative.
- Assume that the minimum value of the secret number is never greater
than the maximum value of the secret number.
- Assume that all the numbers in the input file will never be greater
than 1,000,000 or smaller than -1,000,000.
Tips
- Since you are supposed to write an intelligent guesser; you should code
intelligently.
- This may be the most complicated program you have ever designed. Go
to the drawing board and plan your program. Think about the individual
modules you want using the divide-and-conquer strategy. Write and test
each module / function individually. Do not ever write the complete
program, and then start compiling / running / testing it. You will end
up with numerous compilation and logic errors which will take a long
time to fix. Remember how I (Raymond) showed in lecture that you should
practice incremental coding by incrementally coding parts of the
program, then testing each part out before moving on to other parts of
the program.
- You should probably not use the input file given when testing
your program for the first time; you should create your own input file
(by using the Unix command “vim number1.txt”) with
manageable values, fewer (one?) experiments, and small number of
simulations. When you are confident that your program is working for
small number of simulations, increase it. Do the same for the number of
experiments.
- You should use many printf statements to give more
information of what your program is doing exactly. For example, you
should probably show the secret number, each of Nemo’s guesses, as
well as the outcome from Dory (too high / too low / correct). In
summary, you should print out as much debugging information as you need;
then before submission, comment out the debugging information.
- Ensure that your intelligent guesser works for all possible values
of the secret number, including both the minimum and maximum values.
Ponder
What is the relationship between (max - min + 1) and the average number
of guesses?
This document, index.html, has been accessed 17 times since 25-Jun-24 11:57:13 +08.
This is the 1st time it has been accessed today.
A total of 11 different hosts have accessed this document in the
last 445 days; your host, 216.73.216.39, has accessed it 1 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.