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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
