LINK: https://www.dropbox.com/s/lzkah4knd1kzfog/Homework_%20Interval%20Halving.h
ID: 3671081 • Letter: L
Question
LINK: https://www.dropbox.com/s/lzkah4knd1kzfog/Homework_%20Interval%20Halving.html?dl=0
Assume you are given the power method specified as follows:
/**
* Returns {@code n} to the power {@code p}.
*
* @param n
* the number to which we want to apply the power
* @param p
* the power
* @return the number to the power
* @requires Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE and p >= 0
* @ensures power = n ^ (p)
*/
private static int power(int n, int p) {...}
Use your answers to the previous questions to implement the root method specified below. Be sure to use the idea of interval halving.
/**
* Returns the {@code r}-th root of {@code n}.
*
* @param n
* the number to which we want to apply the root
* @param r
* the root
* @return the root of the number
* @requires n >= 0 and r > 0
* @ensures root ^ (r) <= n < (root + 1) ^ (r)
*/
private static int root(int n, int r) {...}
Additional Questions
In the number guessing game, how many guesses at most will be needed to guess a secret number in the interval [0, n) where n > 0 when using the interval halving strategy discussed above?
Explain how you answered the previous question.
/**
* Returns {@code n} to the power {@code p}.
*
* @param n
* the number to which we want to apply the power
* @param p
* the power
* @return the number to the power
* @requires Integer.MIN_VALUE <= n ^ (p) <= Integer.MAX_VALUE and p >= 0
* @ensures power = n ^ (p)
*/
private static int power(int n, int p) {...}
Explanation / Answer
1.
4^3 = 64 and 5^3 = 125
So, The expression floor(3rd root of 82) = 4
2.
Yes, we can conclude that.
Since root^r <= n < (root + 1)^r,
taking rth root of all sides,
root <= rth root of n < (root + 1)
So, floor(rth root of n) = root
3.
No, there is no reason to try a guess g, where g < 0.
Because, if n > 0, that its rth root can be negative if r is even, but we can easily determine the negative root once we know the positive root.
Also, there is no need to guess g where g > n, because if g > n, its rth power will surely be greater than n
4.
lowEnough = n
highEnough = n + 1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.