清空筛选条件
清空筛选条件

Writing a code for Fibonacci sequence that will return a number closest to the number entered?

2 次查看（过去 30 天）
S
S 2014-10-17
编辑： John D'Errico 2014-10-17
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
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
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.

更多回答（1 个）

Image Analyst
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....."

类别

在 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!

Translated by