Petando la pila. Problemas y retos usando recursividad.

[Pantaláimon]

Buenas!

Voy dejando mis soluciones:

La primera usa la siguiente regla recurrente:

Código :

comb(n, k) = n * comb(n-1, k) * (n - k) para n > k
 

Y se aprovecha de lo que observó leosansan. Es decir, que no hace falta hacer más de n/2 llamadas recurrentes. Aunque yo he usado una función auxiliar para así no comprobar una condición que será verdadera desde la segunda vez que se llama la función recursiva:

Código C:

unsigned icomb (unsigned n, unsigned k) {
    if      (n < k) // fuera de la definición, comportamiento definido por mi arbitrariamente 
        return 0;
    else if (n > k) 
        return n * icomb(n - 1, k) / (n - k);
    else 
        return 1;
}
 
unsigned comb (unsigned n, unsigned k) {
    if (2 * k < n)
        return icomb(n, n - k);
    else
        return icomb(n, k);
}
 

Por lo que he visto las otras soluciones sobre comb se han basado en otra recurrencia parecida:

Código :

comb(n, k) = n * comb(n-1, k-1) / k
 

Pero mirando esto me he fijado en el caso de eferion y, a parte de algo extraño como multiplicar y luego dividir por el mismo número (n - k) / (n - k), no funciona tal como debería para n == k.
Hay que considerar que según la definición comb(n, n) == 1. En la solución de eferion devuelve 0.

Vamos al segundo problema. En dicho caso he aplicado el patrón mayoritario con una función collatz auxiliar. Sin embargo, en mi caso he añadido algo de "memoria" a la función auxiliar collatz con ayuda de una variable estática. De esta manera no hace cálculos repetidos:

Código C:

#include <stdio.h>
#define N 100000
 
unsigned collatz (unsigned num)
{
    static int tabla[N] = {0};
    if ( num <= 1 ) {
        return 0;
    } else if(num < N) {
        if(tabla[num] != 0) {
            return tabla[num];
        } else {
          return tabla[num] = 1 + collatz(num % 2 ? num * 3 + 1 : num / 2);
        }
    } else {
        return 1 + collatz( num % 2 ? num * 3 + 1 : num / 2);
    }
}
 
double promedioCollatz (unsigned num)
{
  if (num > 0)
    return (collatz(num) + (num - 1) * promedioCollatz(num - 1)) / num;
  else
    return 0;
}
 
int main (void) {
  unsigned i;
  for (i = 1; i < 10000; ++i) {
      printf("%6u %lf ", i, promedioCollatz(i));
      puts("");
  }
  return 0;
}
 

Iniciado por Hackman

Para esta use un concepto un poco diferente, los programadores que tiene tiempo en esto seguramente van a observar un patrón bastante antiguo basado en los segmentos de la memoria, antiguamente no existía la memoria flat como ahora, así que había que trabajar con segmentos y offsets. Es solamente otro punto de vista el problema.

Me ha sorprendido tu versión. Buena aportación. Te animo a que sigas por aquí.

Un saludo! ... y mañana más