Consider the following number guessing game. A target integer chosen from 0 to n (inclusive) is known only to the referee. A player is given k chips and is allowed to ask a series of questions in order to identify the unknown integer as long as there is a chip available. Each question must be presented in the form "Is the target integer less than k?" where k is an integer. The referee will answer the question with either a "Yes" or a "No". The referee will always tell the truth. Each Yes costs the player one chip, while a No costs the player nothing Design a Java program to calculate the minimum number of questions needed to identify any target number for a given n and number of chips k. Your program should take in, as input arguments, values of k and n, and output the value of the minimum number of questions needed in the worst case. The following command finds the minimum number of questions needed for n= 32 and k = 3
java -jar Guess. jar 3 32 0
and returns the following:
Professor Danny
For a target number between 0 and 32, with 3 chips, it takes at most 6 questions to identify the target number in the worst case.
Specific Requirements:
1. Use the dynamic programming technique to design your program.
Explain in English your design and present pseudo code (4pts). Define the optimal substructure (4pts), i. e., recurrence. If your program passes all the test cases, you will receive 8 pts. Additionally, 4pts will be awarded for a bottom up implementation.
2. Make an interactive game where a user is the referee and the program will guess the target integer with the minimum number of questions. (Bonus Points: 4 pts)