On Wed, 12 Dec 2007, 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).
Worst case analysis of AVL trees also leads to Fibonacci numbers, as far as I remember.