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