subject

C++ question Part 1
Write a recursive function definition for a function that has one parameter N of type int and that returns the Nth Fibonacci number. The Fibonacci numbers are F0 is 1, F1 is 1, F2 is 2, F3 is 3, F4 is 5, and in general
Fi+2 = Fi + Fi+1 for i = 2, 3, 4, ...
Your client code should prompt the user for N, call the function to compute and return the Nth Fibonacci number, and output the result.
Part 2
You need to have first completed Part 1 to work on this part.
When computing a Fibonacci number using the most straightforward recursive function definition, the recursive solution recomputes each Fibonacci number too many times. To compute Fi + 2 = Fi + Fi + 1, it computes all the numbers computed in F i a second time in computing Fi + 1. You can avoid this by saving the numbers in an array while computing Fi.
Write another version of your recursive Fibonacci function based on this idea. In this recursive solution for calculating the Nth Fibonacci number, create a dynamic array of size N+1, with the array elements at indices 0 and 1 initialized to 1, and the rest of the array elements (2, 3, ... N) initialized to some invalid value (e. g., a named constant NO_VALUE assigned to -1). When the ith Fibonacci number is computed the first time, store it in the array entry i. Then use the array to avoid any further (redundant) recalculation of the Fibonacci numbers.
For this part, your client code should prompt the user for N, create the dynamic array of size N+1, call the function with the array to compute and return the Nth Fibonacci number, and output the result.
part 3
You need to have first completed Part 1 to work on this part.
In this exercise, you will compare the efficiency of a recursive and an iterative function to compute the Fibonacci number.
Examine the recursive function computation of Fibonacci numbers. Note that each Fibonacci number is recomputed many times. To avoid this recomputation, redo Part 1 iteratively, rather than recursively; that is, do the problem with a loop. You should compute each Fibonacci number once on the way to the number requested and discard the numbers when they are no longer needed.
Time1 the solution for Part 1 and Part 3a in finding the 1st, 3rd, 5th, 7th, 9th, 11th, 13th, and 15th Fibonacci numbers. Determine how long each function takes. Compare and comment on your results.
Notes
To time execution of (part of) a C++ 11 program, you can use the chrono library, and the std::chrono nested namespace, as follows:
// main. cpp
#include
#include // for timing
int main()
{
using namespace std;
using namespace std::chrono;
// some program code
auto t0 = high_resolution_clock::now();
// code to be timed
auto t1 = high_resolution_clock::now();
cout << "\nElapsed time: "
<< duration_cast(t1 - t0).count()
<< " nanoseconds\n";
return 0;
}

ansver
Answers: 3

Another question on Computers and Technology

question
Computers and Technology, 22.06.2019 10:30
What can tanya do now to start preparing for the college and scholarship application process? think about her grades, activities in which she can get involved, possible part-time jobs at which she can work, and standardized tests she can take. (10 points) apex
Answers: 2
question
Computers and Technology, 22.06.2019 21:00
Kirk found a local community college with a two-year program and he is comparing the cost with that of an out-of-state two-year school. what is the expected total cost for one year at the local community college if kirk lives at home? what is the expected total cost for one year at the out-of-state school if kirk lives on campus?
Answers: 2
question
Computers and Technology, 23.06.2019 03:00
State 7 common key's for every keyboard
Answers: 1
question
Computers and Technology, 23.06.2019 18:30
How often does colleges update the cost of attendance on their website? . a)every two years b) every four years c) every year d) every semester
Answers: 1
You know the right answer?
C++ question Part 1
Write a recursive function definition for a function that has one paramet...
Questions
question
Mathematics, 03.12.2021 01:20
question
Mathematics, 03.12.2021 01:20