Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Fibonacci challenge

Posted on 2016-09-09
11
Medium Priority
?
165 Views
Last Modified: 2016-09-11
Hi,

I am working on below challenge
http://codingbat.com/prob/p120015

Psedo code:
1. if first two numbers return same
2. else call same fibonacci method by passing n-1 and n-2 and sum it up

public int fibonacci(int n) {
  
   if ((n == 0) || (n == 1)) // base cases
      return n;
    else
      // recursion step
      return fibonacci(n - 1) + fibonacci(n - 2);
  

}

Open in new window




I am passing all tests
Expected      Run            
fibonacci(0) → 0      0      OK      
fibonacci(1) → 1      1      OK      
fibonacci(2) → 1      1      OK      
fibonacci(3) → 2      2      OK      
fibonacci(4) → 3      3      OK      
fibonacci(5) → 5      5      OK      
fibonacci(6) → 8      8      OK      
fibonacci(7) → 13      13      OK      
other tests
OK      

How to improve/modify my design, code and any other alternate approaches. please advise
0
Comment
Question by:gudii9
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +4
11 Comments
 
LVL 36

Assisted Solution

by:mccarl
mccarl earned 200 total points
ID: 41792555
No improvement necessary, that's about as simple as it gets!
0
 
LVL 16

Accepted Solution

by:
gurpsbassi earned 1000 total points
ID: 41792556
You could get rid of the extra brackets
1
 
LVL 35

Assisted Solution

by:ste5an
ste5an earned 200 total points
ID: 41792630
This again: These tests and tasks are pretty poor. Fibonacci is definied here over N0. Thus a test covering the input -1 should exist. And you should test the input first.
1
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 28

Assisted Solution

by:dpearson
dpearson earned 200 total points
ID: 41792714
No changes needed - you've nailed this one.

Doug
0
 
LVL 29

Assisted Solution

by:pepr
pepr earned 200 total points
ID: 41792752
I agree with ste5an. On the other hand, this is for learning the basics of programming, and the totally correct solution (with checking of everything, with unit test, and so on) is not necessary to understand the principle (of Fibonacci, and of the recursive solution).

What is important in this case is that you should not remember this recursive solution as the right approach. The reason is that it is extremely ineficient. The non-recursive solution is not more difficult here, and it is much more efficient.
0
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 200 total points
ID: 41792832
More advanced ways to compute fibonacci(n) really fast - no recursion, and no loops to get to the nth case.
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibformproof.html

The way I learned the closed form solution was to take the z-transform of the equation. Here is a link that describes how to do this.
http://mathforum.org/library/drmath/view/51540.html
The difference equation for the Fibonacci series is:
    u(n+2) = u(n+1) + u(n)   with   u(0) = 0,  u(1) = 1
So:

    u(n+2) - u(n+1) - u(n) = 0  

Taking the z-transforms:

    z^2[u(z) - u(0) - u(1)/z] - z[u(z) - u(0)] - u(z) = 0

    u(z)[z^2 - z - 1] - z^2*u(0) - z*u(1) + z*u(0) = 0

Putting u(0) = 0 and u(1) = 1 this becomes:

    u(z)[z^2 - z - 1] =  z

                 z
    u(z) =  -------------
             z^2 - z - 1

The denominator factorizes to:

    [z-1/2 -sqrt(5)/2)][z-1/2 +sqrt(5)/2]

The trick here is to express u(z)/z in partial fractions:

                                1                     1
    u(z)/z =   1/sqrt(5)[ ----------------   - ---------------- ]
                         z-1/2 - sqrt(5)/2     z-1/2 +sqrt(5)/2

and so: 

                            z                     z
    u(z) = 1/sqrt(5)[----------------  - ------------------ ]
                     z-1/2-sqrt(5)/2)      z-1/2+sqrt(5)/2

Then from table of inverse transforms:

       z
    -------  =  a^n    
     z - a

where a is constant. Then:

                              z                       z
    u(z) = 1/sqrt(5) [-------------------- - --------------------]
                       z - (1/2+sqrt(5)/2)    z - (1/2-sqrt(5)/2)

Now from the table of inverse transforms:
    u(n) = 1/sqrt(5)[(1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n]

Open in new window

2
 
LVL 32

Expert Comment

by:phoffric
ID: 41792846
Here's a graph of the continuous function (i.e., let n be a continuous real positive number) that I asked wolframalpha to plot.
 u(n) = [(1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n]/sqrt(5)

Open in new window

fib.pnghttp://www.wolframalpha.com/input/?i=plot+%5B(1%2F2%2Bsqrt(5)%2F2)%5En+-+(1%2F2-sqrt(5)%2F2)%5En%5D%2Fsqrt(5),+where+n+%3D+1+to+8

When n is a positive integer, then u(n) is also a positive integer. Pretty amazing!
In practice, when computing, you probably won't get a positive integer, but a real number that is very close. To get the positive integer, you need to use a round function.
http://www.tutorialspoint.com/java/number_round.htm
1
 
LVL 32

Expert Comment

by:phoffric
ID: 41792858
As n gets larger, the speed at which you compute fibonacci(n) really rocks over the other approaches, whether recursive or just looping. However, if you want a table of the first N values of fibonacci(n), then just adding the previous two integers and storing it into an array of length N will be faster than using fibonacci(n) for all values of n = 1..N, where n is an integer.
1
 
LVL 7

Author Comment

by:gudii9
ID: 41793631
public int fibonacci(int n) {
  
   if ( n == 0 || n == 1) // base cases
      return n;
    else
      // recursion step
      return fibonacci(n - 1) + fibonacci(n - 2);
  

}

Open in new window


got rid of extra brackets. when i have to put and when i can get rid of brackets?
0
 
LVL 36

Expert Comment

by:mccarl
ID: 41793635
They make absolutely NO difference (in this case) to the execution of the code, if it is easy for you to read with them there, leave them there. That's all that it comes down to, how easy it is to read for YOU.
0
 
LVL 28

Expert Comment

by:dpearson
ID: 41793704
Yes +1 for what mccarl said - I actually think it's a little better with the extra brackets.  You should always prefer clarity and to me the extra with the extra braces is clearer.

Doug
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Suggested Courses

604 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question