Bill Wood wrote:
On Wed, 2007-12-12 at 11:19 +0000, Andrew Coppin wrote: . . .
...and normal programmers care about the Fibonacci numbers because...?
Seriously, there are many, many programmers who don't even know what Fibonacci numbers *are*. And even I can't think of a useful purpose for them. (Unless you count Fibonacci codes?)
Knuth[1] pp. 417-419 discusses Fibonacci trees and Fibonacci search. According to Knuth (and who am I to argue with him) Fibonacci search has better average case running time than binary search, although worst case can be slightly slower.
Cormen et. al.[2] devotes chapter 20 to Fibonacci heaps, which they say are of primarily theoretical interest.
[1] Donald E. Knuth, The Art of Computer Programming, vol. 3, second edition, Addison Wesley Longman (1998).
[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, second edition, The MIT Press (2001).
Mmm, today I learned something. http://en.wikipedia.org/wiki/Fibonacci_heap http://en.wikipedia.org/wiki/Fibonacci_search It seems that at least the latter actually involves the Fibonacci numbers, rather than merely having "Fibonacci" in the name. [That was going to be my next question...]