Presentación

Comenzaremos la sesión con un problema clásico de la programación dinámica, como es el cálculo de los coeficientes binomiales. Este ejercicio se corresponde con el problema 369 del juez on-line de la UVA:

PROBLEMA 369. Combinations: Enunciado del problema en el juez on-line de la UVA

Vamos a detenernos en este punto a estudiar el enunciado en la página del juez on-line antes de continuar, de modo que en lo que sigue supondremos que el problema ha sido al menos leído y comprendido.

Si el alumno se siente capaz, puede intentar resolver el problema sin seguir leyendo más adelante el análisis que sigue a continuación.

Continuar con la lectura del análisis del problema y su enunciado.

Análisis del problema y su enunciado

El enunciado de este problema es en cierto modo capcioso. Se nos plantea la expresión del coeficiente binomial C(n, k) en forma de cociente de determinados términos factoriales que de por sí son enormes. No obstante, en descargo del autor del problema hay que decir que avisa de esta circunstancia, pues con el único propósito de que quede constancia de ello nos hace saber cuál es el valor de 100!, y de este valor podemos extraer una idea de cuál es el orden de magnitud de los valores que están involucrados en la expresión que se nos ofrece para el término C(n, k) que se nos pide calcular. Podemos descartar, por tanto, la realización del cálculo en base a esta expresión.

En este enunciado podemos encontrar algunos datos significativos que nos pueden servir de ayuda para la resolución del ejercicio:

• Se nos dice que el valor máximo para n, y por tanto también para k (puesto que k ≤ n), es de 100.
• Se nos dice que el resultado final de cualquier par n, k propuesto será representable en un entero de 32 bits.

Continuar leyendo pistas de resolución del ejercicio.

Primera pista:

Existe una expresión recursiva del coeficiente binomial C(n, k) que nos evita realizar los cálculos en la forma que sugiere la expresión del término tal como aparece en el enunciado.

Esta expresión es la siguiente:

Donde C(n, 0) = 1 para n ≥ 0, y C(0, k) = 0 para k > 0.

Continuar leyendo la siguiente pista para de resolución del ejercicio.

Segunda pista:

La expresión recursiva anterior resulta computacionalmente ruinosa si diseñamos una función que la implemente tal cual debido al gran número de cálculos que se repiten innecesariamente en su aplicación.

Como curiosidad, el alumno interesado puede probar el tiempo de ejecución del siguiente programa C que resuelve este problema desde un punto de vista conceptual y matemático, pero que computacionalmente está muy lejos de ser una solución aceptable. Se puede observar que para valores pequeños de n funciona aceptablemente bien, sin embargo el tiempo crece exponencialmente conforme n y k aumentan:

#include <stdio.h>

unsigned long int funcionChunga (int n, int k)
{
    if (!k)
        return 1;
    if (!n)
        return 0;

    return funcionChunga (n-1, k-1) + funcionChunga (n-1, k);
}

int main (void) {
    int n, k;

    while (scanf ("%d %d", &n, &k), (n || k))
        printf ("%d things taken %d at a time is %lu exactly.\n", n, k, funcionChunga (n, k));

    return 0;
}

Podemos, no obstante, utilizar esta expresión recursiva para aplicar la técnica de programación dinámica y realizar una única vez cada uno de estos cálculos.

Ver la última pista.

Última pista:

Utilizando una tabla, el anterior cálculo recursivo podría hacerse evitando la explosión exponencial en la complejidad que provoca la expresión recursiva del término C(n, k). El tamaño de esta tabla debería ser de al menos 100 × 100, ya que 100 es el valor máximo de n y k, lo cual es un tamaño razonable. Podríamos diseñar un programa que combinase la técnica de la programación dinámica con un "cálculo perezoso" de los coeficientes C(n, k) según vayan siendo solicitados, es decir, conforme se vayan leyendo pares de valores <n, k> se fuesen calculando únicamente éstos y, por supuesto, todos aquellos que fuesen necesarios para obtenerlos.

Sin embargo, y habida cuenta de que en la tabla tenemos todos los posibles valores que pueden sernos solicitados, en este tipo de problemas suele ser más conveniente precalcular todos estos valores antes siquiera de comenzar a leer los datos de la entrada. De este modo, a partir de ese punto el problema se reduce a leer datos de entrada y a escribir el valor de la correspondiente posición de la tabla.

Para el tipo de los elementos de esta tabla podemos hacer uso de lo que se nos indica en el enunciado y utilizar un tipo entero de 32 bits que, según la precondición que se nos da, es suficiente para almacenar cualquier resultado.

Ver el listado del programa que resuelve el problema.

Listado del programa:

Programa C:

#include <stdio.h>

#define MAXN    100

unsigned long int t[MAXN+1][MAXN+1];

int main (void) {
    int n, k;

    for (k = 0; k<=MAXN; k++) t[0][k] = 0;
    for (n = 1; n<=MAXN; n++) t[n][0] = 1;

    t[1][1] = 1;
    for (n = 2; n<=MAXN; n++) {
        for (k = 1; k < n; k++)
            t[n][k] = t[n-1][k-1] + t[n-1][k];
        t[n][n] = 1;
    }

    while (scanf ("%d %d", &n, &k), (n || k))
        printf ("%d things taken %d at a time is %lu exactly.\n", n, k, t[n][k]);

    return 0;
}

Programa Pascal:

program p369;

const
    MAXN = 100;

type
    TRango = 0 .. MAXN;

    TTabla_Binomial = array [TRango, TRango] of Longint;

var
    n, k : TRango;
    t : TTabla_Binomial;

begin
    for k := 0 to MAXN do t[0,k] := 0;
    for n := 1 to MAXN do t[n,0] := 1;

    t[1,1] := 1;
    for n := 2 to MAXN do
    begin
        for k := 1 to n-1 do
            t[n,k] := t[n-1,k-1] + t[n-1,k];
        t[n,n] := 1
    end;

    read (n, k);
    while (n <> 0) or (k <> 0) do
    begin
        writeln (n, ' things taken ', k, ' at a time is ', t[n,k], ' exactly.');
        read (n, k)
    end
end.

Olimpiada de programación - Facultad de Informática - Universidad de Murcia