Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puestas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

  • Inicialmente todas las puertas están cerradas.
  • El primer camarero cambia de estado las puertas de todas las habitaciones.
  • El segundo cambia de estado de las puertas de las habitaciones pares.
  • El tercero cambia de estado todas las puertas que son múltiplos de 3.
  • El cuarto cambia de estado todas las puertas que son múltiplos de 4
  • Así, hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

Los estados de las puertas se representan por el siguiente tipo de datos

Definir la función

tal que (final n) es la lista de los estados de las n puertas después
de que hayan pasado los n camareros. Por
ejemplo,

Soluciones

11 Comentarios

    1. Mejora de la eficiencia en el conteo de los numeros que dividen a uno dado

  1. Creo que revisando los primos podría reducirse a O(n^2 log(log(n)) / log(n)) aunque no parece merecer la pena el esfuerzo xD. La función solicitada y los infinitos finales para n=1,2,3,…

    1. Pues sorprendentemente (para mi) se pueden calcular todos los números de divisores de cada número entre 1 y n en tan sólo O(n log^3 n), por tanto, igual para las puertas:

Escribe tu solución