2.3.4. Otras técnicas.

Expansión de recurrencias

• Aplicar varias veces la fórmula recurrente hasta encontrar alguna “regularidad”.

• Ejemplo. Calcular el número de mover, para el problema de las torres de Hanoi.

t(0) = 1

t(n) = 2 t(n-1) + 1.

• Expansión de la ecuación recurrente:

t(n) = 2 t(n-1) + 1 = 22 t(n-2) + 2 + 1 = 23 t(n-3)+4+2+1=

n-1 n

= ...... n ..... = 2n t(n-n) + ? 2i = ? 2i = 2n+1 - 1

i = 0 i = 0

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica