8. Consider the Lucas numbers: Ln = Ln1 + Ln-2, n > 1; L1 = 1;...

 

Transcribed Image Text:

8. Consider the Lucas numbers: Ln = Ln1 + Ln-2, n > 1; L1 = 1; Lo = 2. a). Write a recursive function to compute Ln using the above definition directly. Implement your solution and print Li5, where 0 i 10, as output. b). Write a recursive function/procedure to compute Ln with time complexity O(n) (more precisely, the time complexity should be O(nA(n)) when n is large, where A(n) is the com- plexity of adding Ln-1 and Ln-2). Implement your solution and print Li20, where 0 i 25, as output. This program must be able to compute Ln precisely for n < 500. Hint 1: Let Gn Gn = ( L ) : G = (1 1) Gn-1, n > 1; G = Go 0 ( 12 ) ; G = ( 2 1 ) -1 = Ln Ln-1 With this formulation, design a recursive algorithm for G such that the algorithm will return both Ln and Ln-1 with input parameter n. Hint 2: Can you use a primitive type to store L500? For programs in 8 a) and 8 b) of this question, you are NOT allowed to use Python. For C++ and Java, you can only use primitive types such as char, int, long and long long. You are not allowed to use large integer, such as BigInteger in Java, from the language library. You have to write your own large integer data type or object, if needed. 8. Consider the Lucas numbers: Ln = Ln1 + Ln-2, n > 1; L1 = 1; Lo = 2. a). Write a recursive function to compute Ln using the above definition directly. Implement your solution and print Li5, where 0 i 10, as output. b). Write a recursive function/procedure to compute Ln with time complexity O(n) (more precisely, the time complexity should be O(nA(n)) when n is large, where A(n) is the com- plexity of adding Ln-1 and Ln-2). Implement your solution and print Li20, where 0 i 25, as output. This program must be able to compute Ln precisely for n < 500. Hint 1: Let Gn Gn = ( L ) : G = (1 1) Gn-1, n > 1; G = Go 0 ( 12 ) ; G = ( 2 1 ) -1 = Ln Ln-1 With this formulation, design a recursive algorithm for G such that the algorithm will return both Ln and Ln-1 with input parameter n. Hint 2: Can you use a primitive type to store L500? For programs in 8 a) and 8 b) of this question, you are NOT allowed to use Python. For C++ and Java, you can only use primitive types such as char, int, long and long long. You are not allowed to use large integer, such as BigInteger in Java, from the language library. You have to write your own large integer data type or object, if needed.

Answer rating: 100% (QA)

a Here is a recursive function in Java to compute the Lucas n... View the full answer