This course will help prep you to earn the CompTIA Healthcare IT Technician certification showing that you have the knowledge and skills needed to succeed in installing, managing, and troubleshooting IT systems in medical and clinical settings.
public int fibonacci(int n) {
if ((n == 0) || (n == 1)) // base cases
return n;
else
// recursion step
return fibonacci(n - 1) + fibonacci(n - 2);
}
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
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]
u(n) = [(1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n]/sqrt(5)
http://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+8public int fibonacci(int n) {
if ( n == 0 || n == 1) // base cases
return n;
else
// recursion step
return fibonacci(n - 1) + fibonacci(n - 2);
}
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.
Have a better answer? Share it in a comment.