How do i return the largest Fibonacci number that is less than or equal to x?
14 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
Mohannad Abboushi
il 21 Apr 2016
Modificato: Mohannad Abboushi
il 21 Apr 2016
I wrote a recursive code to get the fibonacci number, but I need to get the fibonacci value that is less than or equal to x. For instance, lastfibonacci(7) ans = 5 Here's my code:
function n= lastfibonacci2(x)
if x==0||x==1
n = x;
else
n=lastfibonacci2(x-1)+lastfibonacci2(x-2);
end
end
I was trying to figure out a way to stop the else statement when n<=1 && n<=x, but every time I try to make a statement it doesnt give the right value.
0 Commenti
Risposta accettata
John D'Errico
il 21 Apr 2016
You misunderstand Fibonacci numbers, at least in terms of the recursion.
The basic Fibonacci recursion, i.e.,
f(n) = f(n-1) + f(n-2)
refers to the index of the Fibonacci number. Thus, we have
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
etc. That is not what you are apparently computing in the code. It is NOT true that the last Fibonacci number less than or equal to the number x will satisfy the same recursion on x.
Anyway, the recursion as you have written it is a terrible way to compute Fibonacci numbers. The recursive scheme as you implement it will be extremely inefficient for large index. In fact, you won't even need to go that far before it bogs down your computer.
Why not just do it using a while loop? No recursive calls are needed at all.
function lfib = largefib(x)
% compute the largest fibonacci number <= x
% Code only works for positive values of x, even though
% the Fibonacci sequence can be extended for a
% negative index.
if x <= 1
lfib = 1;
return
end
fnminus2 = 0;
fnminus1 = 1;
fn = -inf;
while fn <= x
fn = fnminus1 + fnminus2;
fnminus2 = fnminus1;
fnminus1 = fn;
end
lfib = fnminus2;
The point is, by making this a simple direct loop, the computation will be O(log(n)) in time, where n is the Fibonacci index.
Finally, a by far easier way to solve this problem is to use the Binet formula for the Fibonacci numbers. Take the log, being careful in the mathematics. I.e., can you drop one of those terms in the Binet formula?
1 Commento
Più risposte (1)
Walter Roberson
il 21 Apr 2016
I recommend that you do not use recursion for this. Instead, loop forward from [0, 1] until you find that the number is > x, at which point you take the previous one.
0 Commenti
Vedere anche
Categorie
Scopri di più su Loops and Conditional Statements in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!