Csalculzate the nth fibonacci number n<> 1000

Question

1.00/5 (2 votes)

See more:

Write a method to calculate the nth Fibonacci number for n<1000. The nth Fibonacci number is the sum of the two previous numbers. The first two numbers are both 1. Return 0 for n<=0 or n>1000. E.g.,
Fibonacci(1) returns 1
Fibonacci(2) returns 1
Fibonacci(3) returns 2
Fibonacci(4) returns 3
Fibonacci(5) returns 5
Fibonacci(6) returns 8
Fibonacci(N) returns Fibonacci(N-1) + Fibonacci(N-2)
First complete the simple method below. Then describe how you could make it more efficient.
public int Fibonacci(int N)
{
if (N <= 0 || N > 1000)

What I have tried:

I have no clue how to do this Write a method to calculate the nth Fibonacci number for n<1000. The nth Fibonacci number is the sum of the two previous numbers. The first two numbers are both 1. Return 0 for n<=0 or n>1000. E.g.,
Fibonacci(1) returns 1
Fibonacci(2) returns 1
Fibonacci(3) returns 2
Fibonacci(4) returns 3
Fibonacci(5) returns 5
Fibonacci(6) returns 8
Fibonacci(N) returns Fibonacci(N-1) + Fibonacci(N-2)
First complete the simple method below. Then describe how you could make it more efficient.
public int Fibonacci(int N)
{
if (N <= 0 || N > 1000)

Posted 17-Jun-16 17:25pm

patelv61

Updated 17-Jun-16 21:50pm

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Dave Kreskowiak · Answer 1 · 2016-06-17T17:37:00

Solution 1

We're not going to do your homework for you.

If you have a question about where you're stuck, great, describe the problem.

Posted 17-Jun-16 17:37pm

Dave Kreskowiak

Garth J Lancaster · Answer 2 · 2016-06-17T17:55:00

Solution 2

A wise man once said

"to understand recursion you must first understand recursion"

that being said, there's at least three ways to solve this issue - iteratively, or recursively, or matrix (Donald Knuth algorithm) in O(log(n)) time !

for a small 'n', it probably doesnt matter stack-wise, iteratively or recursively would do.

So, why dont you give iteratively or recursively a shot, posting back when you have specific questions if/when you get stuck

Posted 17-Jun-16 17:55pm

Garth J Lancaster

Comments

Sergey Alexandrovich Kryukov 18-Jun-16 3:58am

Sorry... (sigh)... I think if you were a little slower in your effort to produce an answer, you would easily see that there is absolutely no any reasonable room for recursive algorithm. Usually, the benefit of recursion is the ease of the implementation when the formulation of the problem is recursive; then one would just act by definition. Obviously, you understand that even in this cases iterative solution can be possible and better, but not always.

However, Fibonacci formulation has is not really recursive. Of course, it cannot be formulated in a recursive way, but only artificially. The original and simplest formulation of the sequence is recurrent, which is not the same as recursive. Look at the formulation, and you will see that it directly suggests the simple iteration solution.

Please see Solution 3.

—SA

Sergey Alexandrovich Kryukov · Answer 3 · 2016-06-17T21:50:00

The problem is quite simple. It definition is, practically, the description of the algorithm: Fibonacci number — Wikipedia, the free encyclopedia.

It's apparent that there is nothing recursive in the algorithm. Instead, it is recurrent, which is not the same:
Recurrence relation — Wikipedia, the free encyclopedia.

The solution should be purely iterative, in just one simple loop. Note that you don't even need to current sequence. You only need to know two previous elements, which you have to store outside the loop.

—SA