¿Existe un algoritmo generalizado para la selección de orina?

Answer 1

Esto ha sido discutido previamente por Randall Munroe [1], y de hecho es el primer éxito en Google para el “algoritmo urinario” (NB: este protocolo es más conocido por su título, la elección internacional del Protocolo de urinarios, Más recursos se pueden encontrar bajo este título). tl; dr es “el algoritmo codicioso es ineficiente para ciertos números de urinarios, pero a veces es óptimo”.

Del mismo modo, se ha investigado sobre los algoritmos óptimos de aparcamiento [2], de los cuales este es un caso especial. El estacionamiento de automóviles toma la formulación de un intervalo de espacios de estacionamiento disponibles, con los jugadores estacionando automóviles de longitud entera en posiciones reales en el intervalo. Hay parkers “buenos”, “malos” y “aleatorios” (o “neutral caótico”). El problema de selección del urinario es un caso especial, en el que los orinadores seleccionan posiciones enteras en el intervalo, pero tienen una longitud efectiva de 2 (1 orinal en uso, más la mitad de un orinal en cada lado para permitir un orinal completo entre dos orinadores).

[1]: http://blog.xkcd.com/2009/09/02/…
[2]: http://www.cs.sunysb.edu/~jgao/C…

Answer 2

Como una puñalada rápida en un refactor de pseudocódigo de la respuesta del usuario de Anon:

  Clase de orinal
 {
     Urinario anterior;
     Urinario siguiente
     se toma

     funcio urinario (int tomado)
         this.taken = tomado;

     funcion urinal izquierda
         devuelve esto.prev ||  Urinal nuevo (0)

     funcion urinal derecha
          devuelve esto. siguiente ||  Urinal nuevo (0)
  }

 func int awk (urinario u)
     devuelve u.left.taken + u.right.taken;
     
 // filtra todos los urinarios tomados, determina la puntuación de incomodidad para cada uno y luego encuentra el urinario con la puntuación más baja.
 func (position, awk) óptimo (colección  urinarios)
     volver a findMin (mapa (awk, filtro (func (tomado == 0), orinales)));

Por favor, sugiera ediciones para convertir esto en código real.

Answer 3

El código está sobre mi cabeza, pero encuentro este tutorial útil.

http://www.albinoblacksheep.com/ …