Writing a code for Fibonacci sequence that will return a number closest to the number entered?
2 次查看(过去 30 天)
显示 更早的评论
How can I write a function that returns the largest Fibonacci number that is less than or equal to x. The Fibonacci number is defined as: f(n)=f(n-1)+f(n-2)
where f(0)=1 and f(1)=1 . Assume x is a positive integer.
1 个评论
Adam
2014-10-17
Probably use recursion, but as with my answer to your other question - work out the algorithm first and then code it up, or build it up from a simple case to a more complex case and keep doing that until you get the full result (e.g. TDD) if you prefer.
采纳的回答
John D'Errico
2014-10-17
编辑:John D'Errico
2014-10-17
He, he, he. Rolls Royce? Yes, it probably is.
But for this problem, I'd make use of good old Binet and his formulaic legacy, at least for a start.
If phi is the golden ratio, then we have
phi = (1 + sqrt(5))/2;
F = @(n) (phi^n - (-phi)^(-n))/sqrt(5);
For example, the 12th Fibonacci number is:
F(12)
ans =
144
It is not truly exact, at least not in terms of floating point numbers. But we need to learn to know when to trust a number to be an integer or not. This is an essential part of computing.
F(12) - 144
ans =
5.6843418860808e-14
I can verify that 144 value using my Rolls Royce engine.
fibonacci(12)
ans =
144
Note that for n reasonably large, we get a very good approximation by ignoring the second term in that formula. For example...
format long g
phi^12/sqrt(5)
ans =
144.001388875493
So a good approximation for the largest Fibonacci number that does not exceed some value k will be simply obtained by taking the log of that expression, and solving for n.
n_k = @(k) floor(log(k*sqrt(5))/log(phi));
n_k(145)
ans =
12
n_k(143)
ans =
11
For larger values of k, say 10^23,
n_k(1e23)
ans =
111
fibonacci(111)
ans =
70492524767089125814114
fibonacci(112)
ans =
114059301025943970552219
You will find that the formula works quite well even for small k.
0 个评论
更多回答(1 个)
Image Analyst
2014-10-17
I'm sure the Rolls Royce of Fibonacci programs is that uploaded by John D'Errico : http://www.mathworks.com/matlabcentral/fileexchange/34766-the-fibonacci-sequence. Take a look at how he does it.
"Often I see students asking for help on a tool to compute the Fibonacci numbers. Or, I'll find....."
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!