dandole al interruptor

El fin de semana pasado prometi a varios amigos que de esta semana no pasaba que publicara un nuevo problemilla de programancia101, porque ya veo que a la que uno se descuida, le sale competencia! Mirad si no a mi camarada Kartones, que se esta animando a publicar problemas en su blog.


Como me ha gustado la idea, se me ha ocurrido dejar otro problema que podeis resolver con un algoritmo sencillito, o bien usando “trucos”:



Imaginemos que tenemos una fila con 64 interruptores, cada uno de los cuales conectamos a una bombilla. Supongamos que partimos de una posicion en la que todas las bombillas estan apagadas y procedemos a pasar por todas ellas y cambiar el estado del interruptor. Una vez hecho esto, volvemos al principio y volvemos a cambiar la posicion del interruptor pero solo para las bombillas en posiciones que sean multiplos de 2 (la segunda, la cuarta, la sexta, …) De nuevo volvemos al principio y volvemos a cambiar la posicion del interruptor pero solo para posiciones multiplos de 3 (la tercera, la sexta, la novena, …) Y seguimos repitiendo el procedimiento para posiciones multiplos de 4, de 5, de 6… asi hasta los multiplos de 64.


Que algoritmo usarias para saber cuales de las bombillas permaneceran encendidas al terminar? Y, si te apetece complicarte un poco mas: Como podriamos hacerlo utilizando la menor cantidad de memoria posible? 

11 comentarios en “dandole al interruptor”

  1. Hola Richal!

    En principio, si he entendido bien el problema, permanecerán encendidas aquellas bombillas que tengan un número PAR de divisores, sin contar el 1.

    En una primera criba, las bombillas correspondientes a interruptores “primos”, sabemos que estarán apagadas al terminar el proceso (excepto la del 1, que estará encendida ya que según comentas la segunda pasada comienza en la nº2).

    Una posible estrategia para el resto de valores sería calcular el número de divisores para cada número mediante un método de factorización como podría ser la “división por tentativa”, la cual por lo general tiene una complejidad de (raíz de N)/2 para cada uno de los 64-1 elementos que estamos evaluando.

    Otra solución algo más refinada consistiría en elegir “representantes” canónicos para cada número, comenzando por calcular los divisores de 64, y los divisores de los divisores de 64… acotando cada vez más el valor de N y, mediante programación dinámica, almacenando las soluciones de estos cálculos para reutilizarlos con los cálculos para el 63, 62…

    Seguiré “ellaborating on this idea”

    Un saludo!

  2. Juraría que este mismo problema lo he hecho en una competición de la ACM… Se te están notando los orígenes!!!

    Lástima que tenga tanta mala memoria, lo tendré que volver a pensar 😀

  3. buenas, crases!

    Miguel: vas bien, vas bien. La apreciacion de los factores (los divisores, excepto el 1) es buena idea. A ver como se te ocurre plantearlo al final (por cierto, si quieres poner tu respuesta en tu blog y enlazarlo desde aqui, tambien sirve }:D)

    Augusto: hay tres o cuatro variantes de este problema que he visto en concursos de programacion… asi que si, seguro que ha salido en el de la ACM alguna vez. Otro dia tendremos que hablar de concursos y lo bien que vienen para “entrenar” }:)

  4. Es que en las clases de Algorítmica en la Uni, con Miguel Revilla, los exámenes eran problemas de los concursos de la ACM. Como teníamos el juez online… 😉

    Por cierto, aprovecho para recomendar a todo el mundo el participar, a modo de ejercicio, en uno de estos concursos 🙂 Yo hace tiempo que no lo hago, pero era malísimo. Y era alucinante ver a la gente resolver esos problemas “imposibles” 😀

    http://acm.uva.es/problemset/

  5. Así a bote pronto, con el algoritmo para menor consumo de memoria sería tener un long long e ir recorriend mediante shifts de n bits y apagando o enciendiendo con máscaras los valores para al final contar los unos…

  6. hallo again!

    Augusto: Lo de que tuvieras a Miguel Revilla de profe de algoritmica explica muchas cosas }:)

    Yo siempre he pensado que si las clases de algoritmia y estructuras de datos incorporaran mas problemas “interesantes” la gente saldria mucho mejor preparada a la hora de desarrollar… pero bueno, a ver si poco a poco la cosa va a mejor

    Rafael: Efectivamente! (sea long long, Double, Int64 o lo que a cada uno le venga mejor, claro) Ya sabes que eso implica ser mas eficiente en calculo y memoria, pero mas enrevesado en codigo… que es de lo que se trataba, no? }:)

  7. La verdad, después de mucho reflexionarlo, es que el problema no necesita ningún cálculo de tipo complejo (o eso creo).

    La cosa se trata de saber qué numeros menores o iguales que el 64 tienen un número impar de divisores. Dichas bombillas son las que permanecerán encendidas al final, ya que si partimos de que están apagadas, realizaremos un número impar de pulsaciones, con lo que acabarán encendidas.

    Cuales son dichos números? Bien, si nos fijamos, los divisores de un número siempre se asocian por parejas.

    Por ejemplo, el 28 tiene como divisores:
    28×1
    14×2
    7×4

    De modo que tiene un número par de divisores.

    Qué números son aquellos que tienen un número impar de divisores? Los CUADRADOS PERFECTOS. Es decir, los números cuya raíz cuadrada es entera (siendo dicha raíz el divisor en cuestión).

    Por ejemplo, el 36:
    36×1 (2 pulsaciones)
    18×2 (2 pulsaciones)
    12×3 (2 pulsaciones)
    9×4 (2 pulsaciones)
    6×6 (1 pulsación)

    Para el 36, pulsaremos 9 veces el interruptor en total. Por tanto, permanecerá encendida al final.

    Resumiendo, sin necesidad de cálculos de ningún tipo (salvo un cálculo de raíces cuadradas, o en su caso, un bucle que partiendo de 2 calcule los cuadrados menores o iguales q 64… es decir, 8 productos, 8 if’s y poco más) tendremos resuelto el problema.

    Bombillas encendidas: 4, 9, 16, 25, 36, 49 y 64.

    Un saludo Ricardo, espero nuevos retos 😉

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *