<< Ejemplo de recurrencia con tabla >>

En la lección Recurencia con tablas se discute como resolver el siguiente problema de manera recursiva. En esta página aparece la versión en Basic.

Se define f(n) como la cantidad de formas distintas en que puede escribirse a n como suma de enteros positivos (sin importar en que orden se sumen, por ejemplo 15 = 7 + 3 + 5 y 15 = 5 + 3 + 7 se consideran la misma forma). Calcular f(120).

La idea es guardar en una tabla los valores que ya se calcularon para no volver a calcularlos otra vez.

Hay que definir una estructura del tipo:

Const True =-1
Const False =0
Type item
        v  As Long
        calculado As Integer 'no hay booleanos pero usando los valores
                             'de True y False definidos arriba
                             'es casi lo mismo
End Type
Dim Tabla(0 To 150, 0 To 150) as item

Y agregar un procedimiento para inicializarlo:

Sub initTabla()
    Dim i As Long
    Dim j As Long
    For i = 0 To 150 
        Tabla(i,1).v=1
        Tabla(i,1).calculado=True
    Next i
    For i = 0 To 150
        For j = 2 To 150 
            If j=1 Then Tabla(i,j).calculado=False
        Next j
    Next i
End Sub

Ahora G se ve así:

Function G&(n As Long, s As Long)
    'en algunas versiones se puede escribir tambien:
'Function G(n As Long, s As Long) As Long
    If n<0 Then
        G=0
    Else
        If Not Tabla(n,s).calculado Then
            'Si todavía no esta calculado, lo calculo
            Tabla(n,s).v=G(n,s-1)+G(n-s,s)
            Tabla(n,s).calculado=True
        End If
        G=Tabla(n,s).v
    End If
End Function

Lecciones relacionadas:

Recurrencia con tablas (Con la discusión original del problema)

OmaNet   Curso CyM98	OmaNet - Educación Interactiva    www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar