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 08:00
Someone with this coz i don’t really know what i can choose, just pick whatever u want. homework - you need to choose a website that you like or use frequently. you must visit the website and discuss 6 different features/parts/aspects of the website that you think makes it good. (100 words)
Answers: 2
question
Computers and Technology, 22.06.2019 19:20
Consider the following code snippet: #ifndef cashregister_h#define cashregister_hconst double max_balance = 6000000.0; class cashregister{public: cashregister(); cashregister(double new_balance); void set_balance(double new_balance); double get_balance() const; private: double balance[12]; }; double get_monthly_balance(cashregister bk, int month); #endifwhich of the following is correct? a)the header file is correct as given.b)the definition of max_balance should be removed since header files should not contain constants.c)the definition of cashregister should be removed since header files should not contain class definitions.d)the body of the get_monthly_balance function should be added to the header file.
Answers: 1
question
Computers and Technology, 23.06.2019 01:10
Are special combinations of keys that tell a computer to perform a command. keypads multi-keys combinations shortcuts
Answers: 1
question
Computers and Technology, 23.06.2019 18:30
Write a program that prints the day number of the year, given the date in the form month-day-year. for example, if the input is 1-1-2006, the day number is 1; if the input is 12-25-2006, the day number is 359. the program should check for a leap year. a year is a leap year if it is divisible by 4, but not divisible by 100. for example, 1992 and 2008 are divisible by 4, but not by 100. a year that is divisible by 100 is a leap year if it is also divisible by 400. for example, 1600 and 2000 are divisible by 400. however, 1800 is not a leap year because 1800 is not divisible by 400.
Answers: 3
You know the right answer?
C++ question Part 1
Write a recursive function definition for a function that has one paramet...
Questions
question
Mathematics, 19.09.2019 20:00