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

jueves, 11 de abril de 2013

VB6: Cómo saber si existe una webcam conectada a la PC

Primero declaramos las funciones SendMessage y capCreateCaptureWindow (si se declaran en un módulo .bas las declaraciones deben ser públicas, para este ejemplo asumiremos que todo el código está dentro de un Form):

Private Declare Function capCreateCaptureWindow Lib "avicap32.dll" _
    Alias "capCreateCaptureWindowA" ( _
    ByVal lpszWindowName As String, _
    ByVal dwStyle As Long, _
    ByVal x As Long, _
    ByVal y As Long, _
    ByVal nWidth As Long, _
    ByVal nHeight As Long, _
    ByVal hwndParent As Long, _
    ByVal nID As Long) As Long

Private Declare Function SendMessage Lib "user32" Alias "SendMessageA" ( _
    ByVal hwnd As Long, _
    ByVal wMsg As Long, _
    ByVal wParam As Long, _
    lParam As Any) As Long


Private Const CONNECT As Long = 1034


El código que nos dice si hay una webcam conectada es:

Dim mCapHwnd as Long

mCapHwnd = capCreateCaptureWindowA("WebCap", 0, 0, 0, 320, 240, Me.hwnd, 0)
DoEvents

If SendMessage(mCapHwnd, CONNECT, 0, 0) <> 0 Then
     
MsgBox "Se ha detectado una webcam conectada y lista para usarse"
Else
      MsgBox "No se ha detectado una webcam"
End If



Basado en este código de Recursos Visual Basic