Acerca de:

Este blog contiene los códigos, ejemplos y bases de datos que he usado cuando aprendía acerca de algún tema específico. En lugar de borrarlos (una vez dominado ya el tema), he decidido publicarlos :)

jueves, 18 de abril de 2013

Calcular los n primeros elementos del Conjunto de Wirth

Me encontré con este problema revisando la página de PuntoPeek. Aquí copio la definición del Conjunto de Wirth:
"El conjunto de Wirth es un subconjunto de los enteros positivos que cumple con la siguiente regla: el 1 pertenece al conjunto y si un numero k pertenece al conjunto entonces los numeros 2*k+1 y 3*k+1 pertenecen al conjunto."

En un primer vistazo parecía un problema que podría resolverse con un bucle, pero en realidad es bastante más complicado:
Empiezo con 1 y calculo los siguientes dos números: 2*1+1=3 y 3*1+1=4.
Mi conjunto por ahora es: [1, 3, 4]
Los siguientes dos números son: 3*2+1=7 y 3*3+1=10
Los otros dos siguientes son: 4*2+1=9 y 4*3+1=13
Mi conjunto ahora es: [1, 3, 4, 7, 10, 9, 13]
Calculo los dos siguientes: 7*2+1=15 y 7*3+1=22
Mi conjunto ahora es: [1, 3, 4, 7, 10, 9, 13, 15, 22]
Calculo los dos siguientes: 10*2+1=21 y 10*3+1=31
Mi conjunto ahora es: [1, 3, 4, 7, 10, 9, 13, 15, 22, 21, 31]
Calculo los dos siguientes: 9*2+1=19 y 9*3+1=28
Mi conjunto ahora es: [1, 3, 4, 7, 10, 9, 13, 15, 22, 21, 31, 19, 28]

Se puede notar que los números del conjunto de Wirth no se generan de modo ascendente, si no que el conjunto se va "rellenando" a medida que se hacen más y más cálculos. Un simple bucle que calcule los 5 primeros números del conjunto de Wirth nos dará [1, 3, 4, 7, 10] cuando la respuesta correcta es [1, 3, 4, 7, 9]. El error se hace más grande con cantidades mayores.
Otro problema es que se generan números repetidos, por ejemplo en el caso de 10*3+1 y 15*2+1.
Considerando esto, se puede comprobar que varias de la respuestas dadas en esta web son erróneas.

Para evitar el caso de números faltantes, mi algoritmo calcula el doble de los números requeridos, además de comprobar que no estén repetidos, ordena el array resultante y sólo muestra la cantidad de números solicitada.

Este es el código en Python:

def Wirth(i, n, w, k):
    if n == 1:
        return 0
    else:       
        k = w[i]
        t = 2*k + 1

        if t not in w:
            w.append(t)

        t = 3*k + 1

        if t not in w:
            w.append(t)

        return Wirth(i+1, n-1, w, k)

w=[1]
n=50

Wirth(0, n*2, w, 1)
w.sort()
w = w[0 : n]
print w




Y en C# usando Linq:

 class Program
    {
        static int Wirth(int i, int n, ref int[] w, int k, int count)
        {
            if (n == 0 || count >= w.Length)
                return 0;
            else
            {
                k = w[i];
                int t = 2 * k + 1;

                if (!w.Any(c => c == t))
                {
                    count++;
                    w[count] = t;
                }

                t = 3 * k + 1;

                if (!w.Any(c => c == t))
                {
                    count++;
                    w[count] = t;
                }
              
                return Wirth(i + 1, n - 1, ref w, k, count);
            }
        }

        static void Main(string[] args)
        {         
            int n = 50;

            int[] w = Enumerable.Repeat(0, n * 2).ToArray();
            w[0] = 1;

            Wirth(0, n, ref w, 1, 0);

            w = w.Where(c => c != 0).OrderBy(c => c).ToArray();

            for (int i = 0; i < n; i++)
                Console.WriteLine(w[i]);

            Console.Read();
        }
    }


Y obtengo la misma respuesta que PuntoPeek, cuya solución me ha gustado, es bastante elegante :D

1 comentario:

Alayn Lado Chaviano "cubano UCI" dijo...

public static void main(String[] args) {
Scanner ve = new Scanner(System.in);
double n = ve.nextDouble();

System.out.println(Wirth(n, n));
}

public static boolean Wirth(double n, double a) {
if (n == 1.0 || a == 1.0) {
return true;
} else if (n < 1.0 && a < 1.0) {
return false;
}
else
return Wirth((a - 1) / 2, (1 - a)/ 3)|| Wirth((n - 1) / 2, (n - 1 )/ 3);
}

}