Advanced Search

Question: need help with the code

Question:need help with the code

kristavaldes 15 Maple
homework fibonacci
July 19 2018
0


If n people (numbered 1 to n) stand in a circle and someone starts going around the circle and eliminating every other person till only one person is left, the number J(n) of the person left at the end is given by 

    J(n) = 1                           if n = 1
    J(n) = 2*J(n/2) - 1          if n > 1 and n is even
    J(n) = 2*J((n-1)/2) + 1   if  n > 1 and n is odd

(i) Write a recursive procedure to compute J. [As a check the first 16 values (starting with 1) of J(n) are 1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1]. 
(ii)Compute the value of J(10000). 
(iii) Can you explain why this is so much faster than our recursive procedure to compute the n-th Fibonacci number?
Please Wait...