Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Example-Generalized Fibonacci Numbers

Consider the problem of computing the generalized Fibonacci numbers  . The generalized Fibonacci numbers of order tex2html_wrap_inline60145 are given by

  equation33080

Notice that the ``normal'' Fibonacci numbers considered in Section gif are the same as the generalized Fibonacci numbers of order 2.

If we write a recursive method that implements directly Equation gif, we get an algorithm with exponential running time. For example, in Section gif it is shown that the time to compute the second-order Fibonacci numbers is tex2html_wrap_inline67704.

The problem with the direct recursive implementation is that it does far more work than is needed because it solves the same subproblem many times. For example, to compute tex2html_wrap_inline67978 it is necessary to compute both tex2html_wrap_inline67980 and tex2html_wrap_inline67982. However, in computing tex2html_wrap_inline67980 it is also necessary to compute tex2html_wrap_inline67982, and so on.

An alternative to the top-down recursive implementation is to do the calculation from the bottom up. In order to do this we compute the series of sequences

eqnarray33098

Notice that we can compute tex2html_wrap_inline67988 from the information contained in tex2html_wrap_inline66813 simply by using Equation gif.

Program gif defines the method Fibonacci which takes two integer arguments n and k and computes the tex2html_wrap_inline57687 Fibonacci number of order k using the approach described above. This algorithm uses an array to represent the series of sequences tex2html_wrap_inline68000. As each subsequent Fibonacci number is computed it is added to the end of the array.

   program33111
Program: Dynamic programming example--computing generalized Fibonacci numbers.

The worst-case running time of the Fibonacci method given in Program gif is a function of both n and k:

displaymath67970


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.