Given a number n and 3 different operations that you can perform: n = n/2 n = n/
ID: 3907456 • Letter: G
Question
Given a number n and 3 different operations that you can perform:
n = n/2
n = n/3
n = n?1
Give an algorithm that reaches n == 1 in the minimum number of operations for any given starting n.
Note that n/2 and n/3 compute floating point division, not integer division
Please provide the algorithm, Correctness Proof, and runtime analysis
Algorithm: Your algorithm generally has a correct idea and has a polynomial runtime
Correctness Proof: Your algorithm is correct on all inputs, has a polynomial runtime, and your proof of correctness is logically sound and complete
Runtime Analysis: Your algorithm has a polynomial runtime and you correctly analyzed the runtime of your algorithm
Explanation / Answer
Given that, 'n' is a number. We can consider 'n' as a real number or just as an integer. Let us say 'n' as a real number.Since we are doing divison operation, in C programming the result of a division operation is always an integer.But in other languages like JAVA, we will get floating values as a result. Therefore convert the 'n' into integer by using corresponding semantic rules.
From the given three operations, the use of n=n/1 operation is to convert the floating value into integer.For example int a=4.9/1 gives a=4 not a=4.9; The consequetive operations of n=n/2 and n/n=3 can be converted directly into n=n/6 without loss of data;
Algorithm to reach n==1:
while(n!=1) {
n=n/6; // n=n/2 && n=n/3 eventhough the result is floating value, there will be no error in the final result.
if(n<1) // for the values which are less than 6.
n=1;
else
n=n/1;
}
case1:
input n=11. Then n=11/6 which is n=1.833333 and n=n/1 gives n=1. Then the while loop will be broken.
case 2:
input n=5. Then n=5/6 which is n=0.833333 and n<1 therefor n will become 1. Then the loop will be broken.
Time Complexity : Since the loop will be run for n/6 times for any n value, the time complexity will be O(n) which is a polynomial time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.