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). -- Bill Wood