9780023606922, Chapter 2 4, Problem 24E

Prévia do material em texto

Chapter 2.4, Problem 24E Step-by-step solution Step 1 of 2 Specified algorithm: exp2 (a,n) == return a power = exp2(a,m) power = power X power if(n is even) return power else return power xa } It is a recursive algorithm as the algorithm calls We have to explain how the above algorithm computes a"- The function exp 2(a,n) is actually broken into smaller instance of exp 2(a,m) Here, m = n and each smaller instance is squared to give the desired result if n is even. 2 Step 2 of 2 When n is odd, the smaller instance exp 2(a,m) Here, m = and it is squared and multiplied by a to give the desired result. 2 At n=1, = the algorithm returns a. Therefore, for the inputs a = n = 32 the path goes in this way 2 n=2 24 n=32 Now if the input n is odd like n = 17 then the path would have been 2 n=2 Thus the algorithm exp 2(a,n) computes a" where the inputs are