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!