Implement a class called fibonacci

Assignment Help Programming Languages
Reference no: EM131264400

Assignment

Part 1

The Fibonacci sequence is defined as follows. If Fib(k) denotes the kth number in the Fibonacci sequence, then, for non-negative positions in the sequence,

Fib(1) = 1

Fib(2) = 1

Fib(n) = Fib(n-1) + Fib(n-2)

In English, we may say that a Fibonacci number is ***** sum of its two immediate predecessors, except for the first two Fibonacci numbers, which are both 1.

Implement a class called Fibonacci. This class should provide a single class method (static) with the following signature:

double Fibonacci::getNthFibonacciRecursively(int n)

which should do exactly that. It calculates and returns the nth Fibonacci number and does so recursively, by invoking itself for certain input values of n. Note that its parameter n is an integer, but its return value is a double. Why? Answer this question in a single short sentence within the header comment of this method.

From your main(), issue calls to Fibonacci for various values of n in the range 1 to 10 and make sure that the output concurs with your paper-and-pencil calculation. Handle the case for n <= 0 by returning an invalid value and note it in the documentation of the function (within comments). For example you'd say that the function will return -1 for n <= 0. That's perfectly acceptable.

Part 2

In this part of the answer you are going to profile your function. But rather than use the system profiler which was not part of this course's instruction, you will build and use a very simple measurement tool.

Windows users:

The following function returns a timestamp in milliseconds since the system started.

double getMillis() {

return (double) getTickCount();

}

To use it in your code, include the system header "WinSock2.h" as follows, immediately following your standard header declarations:

#include

The exact value returned by getMillis() doesn't matter for the purposes of this question. What matters is the difference in the return value between two successive calls to the function. If you call it at times A and B, then the difference between the two return values is the number of milliseconds elapsed. You are going to call this function to measure something about your Fibonacci function.

In your main(), you must call Fibonacci::getNthFibonacciRecursively(n) in a loop with progressively increasing values of n from 1 to 40. You must call getMillis() both immediately before and after your call for the nth Fibonacci number. E.g.

double timeStamp1 = getMillis();

Fibonacci::getNthFibonacci(n);

double timeStamp2 = getMillis();

double millisToCompute = timeStamp2 - timeStamp1;

•For each n, you must print the time taken to compute your result.

•You must study the relation between n and the time taken and predict the time it will take to calculate Fibonacci(100). It is important that you don't actually calculate the 100th Fibonacci number (especially not using your recursive function). You must simply study the time taken to calculate the first 40 numbers in the sequence and predict the time it will take to calculate the 100th number. Report this time in the most intuitive and appropriate time unit (whether it's microseconds, milliseconds, minutes or hours is up to you, but don't say it will take********** milliseconds. Convert this into a time unit humans can naturally relate to.

•You can use a method of your choice to do the prediction - Eyeballing and intuiting, plotting on a sheet of graph paper, using a spreadsheet program if you have one, or using WolframAlpha.com. For example, at wolframalpha.com, you can enter the "Exponential fit: num1, num2, num3, ..." and it will try to infer an exponential equation to calculate the numbers as a function of its position in the input sequence.

Reference no: EM131264400

Questions Cloud

What you have learned about fddi : Using Microsoft Word, write a two to three paragraph summary of what you have learned about FDDI. Include all of the URL addresses of the links that you used at the end of your summary.
Explain task that would occur in each step if use sdlc model : Consider a different SDLC Model (4 step or 12 step). Describe the events/tasks that would occur in each step if your company were to use this SDLC model instead. - 2 pages
Provide a holistic discussion of all factors : Provide a holistic discussion of all factors, but rather to provide a more in-depth debate of the key elements important to the organization/international firm you have chosen to analyze.
What is daphne and david adjusted gross income : What is Daphne's and David's Adjusted Gross Income (AGI) and Taxable Income for 2015? What is Daphne's and David's marginal tax rate? Their effective tax rate (using AGI)
Implement a class called fibonacci : Implement a class called Fibonacci. This class should provide a single class method (static) with the following signature: double Fibonacci::getNthFibonacciRecursively(int n)
Find the largest allowable value of t : The cylindrical tank of 10-in. diameter is fabricated from 1/4-in. plate. The tank is subjected to an internal pressure of 400 psi and a torque T. Find the largest allowable value of T according to the maximum distortion energy theory. Use σyp = 3..
Demonstrate your learning of marketing using an organisation : In light of this your task is to write a 3000-word magazine style article that explains how an organisation you have selected has utilised a Blue Ocean Strategy and some of the components of The Circle of Satisfaction to become successful.
How often a player would win if they rolled the dice : Write a program that simulates how often a player would win if they rolled the dice 100 times.The program will output a message such as "The player rolled 14 sevens and 5 elevens for a total of 19 wins out of 100."
Find the largest axial load p that can be applied : Use the maximum shear stress theory to find the largest axial load P that can be applied in addition to the pressure without causing yielding.

Reviews

Write a Review

Programming Languages Questions & Answers

  Write a haskell program to calculates a balanced partition

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition,

  Create an application to run in the amazon ec2 service

In this project you will create an application to run in the Amazon EC2 service and you will also create a client that can run on local machine and access your application.

  Explain the process to develop a web page locally

Explain the process to develop a Web page locally

  Write functions

These 14 questions covers java class, Array, link list , generic class.

  Programming assignment

If the user wants to read the input from a file, then the output will also go into a different file . If the user wants to read the input interactively, then the output will go to the screen .

  Write a prolog program using swi proglog

Write a Prolog program using swi proglog

  Create a custom application using eclipse

Create a custom Application Using Eclipse Android Development

  Create a application using the mvc architecture

create a application using the MVC architecture. No scripting elements are allowed in JSP pages.

  Develops bespoke solutions for the rubber industry

Develops bespoke solutions for the rubber industry

  Design a program that models the worms behavior

Design a program that models the worm's behavior.

  Writing a class

Build a class for a type called Fraction

  Design a program that assigns seats on an airplane

Write a program that allows an instructor to keep a grade book and also design and implement a program that assigns seats on an airplane.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd