Guessing Game C program
The divide and conquor algorithm is a technique used to make a complicated problem easier to solve by splitting (or dividing) it into smaller more managable steps.
Let's look at the guessing game as an example to use the Divide and Conquer Algorithm by halfing our possible number of guesses. To play the guessing, a person (player A) will choose a random numer from n to m, another person (player B) will have to guess player A's number in "x" turns. Player A will assist player B by telling player B if the number they guessed is higher than or lower than player A's randomly chosen number. The Divide and Conquer Algoritm will tell you if it is possible to guess player A's number in the given amount of turns x, and will tell the maximum amount of tries or guesses you will need in order to guess there number correctly.
An example of how the game works:
Player A: I am thinking of a number from 1 to 100, can you guess my number within 4 turns ?
Player B: Sure, is your number 89 ?
Player A: Nope guess a lower number.
Player B: Okay, is your number 75 ?
Player A: Nope, guess a higher number.
Player B: Okay is your number 80 ?
Player A: Nope, guess a higher number.
Player B: Okay, is your number 88 ?
Player A: Yes, congratulations you guessed my number in 4 turns you win!
Now suppose Player A asked if Player B could always guess the correct number in 4 turns, would they ? The answer is no. The Divide and Conquor Algorithm will show us that it would take at most 6 turns to guess the right answer, so although it's possible to guess the number anytime before the 6th turn, you are only guaranteed to be able to guess the correct number in 6 turns.
Let's look at the guessing game example from before, but this time we will use the Divide and Conquer Algorithm to solve it
Player A: I am thinking of a number from 1 to 100, can you guess my number within 6 turns ?
Player B: Sure and in 6 turns or less, is your number 100/2 = 50 ?
Player A: Nope guess a higher number.
Player B: Okay, is your number (100 + 50) / 2 = 75 ?
Player A: Nope, guess a higher number.
Player B: Okay is your number round up (100 +75)/2 = 88?
Player A: Yes, congratulations you guessed my number in 3 turns you win!
Okay, so where did we get the guessing numbers 50, 75 and 88 ? They came from adding the lowest range "1" and the highest range "100" minus "1", which equals 100 (the total possible numbers you can guess), and then dividing by 2 to get 50. The player then says if our guess is low or high either way we now get rid of 50 possible numbers, in this case the number is higher, this means our guess was too low. So the new lowest range is 51 and the highest range is still 100 so (100 +51-1) /2 = 75, so our next guess is 75. So now we got rid of another half of the range, in total we have gotten rid of 3/4 of the numbers. This leaves us with 1/4 of 100 numbers left, which is 25 possible numbers,the numbers are 76 to 100. Now, to get the third number 87. First Player A will tell us if the number 75 is too high or too low, in this case it's too low, so our lowest possible number is 76 and the highest possible number is still 100, so add 100 + 76 - 1 = 175 and then divide it by 2, round up(175/2 = 87.5) = 88.The reason why we round is because we only deal in integers or whole numbers. Our guess 88 is the correct number !
Here is the actual Steps (Algorithm) we just used:
Now you know how to solve for the number quickly using the Divide and Conquer algorithm, but how do we know the maximum number of turns it would take to solve a Divide and Conquer Algorithm ? Well let's look at a smaller set of numbers for the guessing game. In this guessing game example we want to guess a number from 1 to 10 (10 possible numbers). Most people would say that the maximum number of guesses for this would be 10, which is one guess for each possible number, but this isn't true. Let's use the Divide and Conquer Algorithm and see how long it takes to go through every possible number.
So the maximum number of turns it took to guess Player A's number was 4 which is log2(10) rounded up. We get the log2 from dividing by 2 each time and we get the number 10 from the total possible number of guesses. This seems small for a set of 10 numbers but what if you had to guess numbers from 1 to 1,000,000, with the Divide and Conquer Algorithm it would only take 20 guesses before you would guess someones number correctly !
log2(N) → O(log N)