El reto
Escriba una función que tome dos enteros positivos n y k como argumentos y devuelva el número de la última persona que queda fuera de n después de contar cada k -ésima persona.
Este es un desafío de código de golf, por lo que gana el código más corto.
El problema
n personas (numeradas del 1 al n ) están paradas en un círculo y cada k -ésima se cuenta hasta que quede una sola persona (consulte el artículo correspondiente de wikipedia ). Determine el número de esta última persona.
Por ejemplo, para k = 3 dos personas serán omitidas y la tercera será descontada. Es decir, para n = 7, los números se contarán en el orden 3 6 2 7 5 1 (en detalle 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 ) y, por lo tanto, la respuesta es 4 .
Ejemplos
J(7,1) = 7 // people are counted out in order 1 2 3 4 5 6 [7]
J(7,2) = 7 // people are counted out in order 2 4 6 1 5 3 [7]
J(7,3) = 4 // see above
J(7,11) = 1
J(77,8) = 1
J(123,12) = 21
{k block}
sobre[0..n-1]
conseguir queg(0,k) 0 k
para empezar? Lo siento, si estoy publicando estas preguntas en el lugar equivocado.0 1 block
. Muy convenientemente, eso pasa a serg(1, k) (2-1) block
. Entonces comienza eng(1,k) 1
lugar de hacerlog(0,k) 0
. Luego, después de ejecutar el bloque, empuja el siguiente elemento de la matriz (2
) y ejecuta el bloque nuevamente, etc.Máquina de registro Minsky (25 estados sin interrupción)
Técnicamente no es una función, pero está en un paradigma informático que no tiene funciones per se ...
Esta es una ligera variación en el caso de prueba principal de mi primer desafío de interpretación MRM :
Entrada en registros
n
yk
; salida en el registror
; se supone quer=i=t=0
a la entrada. Las dos primeras instrucciones de detención son casos de error.fuente
k=1
entoncesr=0
. Hmm, tengo que pensar en esto otra vez ...i
simplemente está contando de2
an
mientras quer
es el registro que acumula el resultado.Python, 36
También usé la fórmula de wikipedia:
Ejemplos:
fuente
Mathematica,
3836 bytesLa misma fórmula de Wikipedia:
fuente
If[#<2,1,Mod[#0[#-1,#2]+#2,#,1]]&
C, 40 caracteres
Esta es prácticamente la fórmula que ofrece el artículo de Wikipedia vinculado anteriormente:
Para variar, aquí hay una implementación que realmente ejecuta la simulación (99 caracteres):
fuente
j(n,k){return--n?(j(n,k)+k-1)%-~n+1:1;}
.dc, 27 bytes
Utiliza la recurrencia del artículo de Wikipedia. Explicación:
fuente
J, 45 caracteres
Ejecuta la simulación.
Alternativamente, usando la fórmula (31 caracteres):
Espero que a Howard no le importe que haya ajustado ligeramente el formato de entrada para adaptarlo a un verbo diádico en J.
Uso:
fuente
GolfScript,
3224 bytesUso: espera que los dos parámetros n y k estén en la pila y deja el valor de salida.
(gracias a Peter Taylor por sugerir un enfoque iterativo y muchos otros consejos)
El viejo enfoque (recursivo) de 32 caracteres:
Este es mi primer GolfScript, así que háganme saber sus críticas.
fuente
1-
tiene un código de operación especial(
. Del mismo modo1+
es)
. No tiene que usar caracteres alfabéticos para el almacenamiento, por lo que podría usar, por ejemplo, en^
lugar deJ
y no necesitar un espacio después. Tiene mucho más tiempo$
de lo habitual en un programa bien desarrollado: considere si puede reducirlos usando alguna combinación de\@.
.$
referencias.g
del artículo de Wikipedia, y use,
y/
.{,{\2$+\)%}*)\;}:f;
Asegúrese de entender por qué funciona;)k
dentro del bucle y luego 2 más para descartarlo al final, podemos tirar hacia adentro usando+
hasta 17 caracteres:{{@+\)%}+\,*)}:f;
dudo que eso pueda mejorarse.R, 48
Versión en ejecución con ejemplos: http://ideone.com/i7wae
fuente
Groovy, 36 bytes
fuente
Haskell, 68
Hace la simulación real. Demostración:
fuente
Scala, 53 bytes
fuente
C, 88 caracteres
Hace la simulación, no calcula la fórmula.
Mucho más largo que la fórmula, pero más corto que la otra simulación C.
Notas:
1. Asigna memoria y nunca libera.
2. Asigna en
n*8
lugar den*4
, porque yo usop[n]
. Podría asignar(n+1)*4
, pero son más personajes.fuente
C ++, 166 bytes
Golfizado:
Sin golf:
fuente
J
función, utilizando el operador ternario.intn
en tu versión de golf no compilará#include <list>
J, 8 bytes
fuente
Ruby, 39 bytes
Versión en ejecución con casos de prueba: http://ideone.com/pXOUc
fuente
Q, 34 bytes
Uso:
fuente
Ruby, 34 bytes
fuente
Haskell, 29
Usando la fórmula de wikipedia.
fuente
JavaScript (ECMAScript 5), 48 bytes
Usando ECMAScript 5 ya que esa era la última versión de JavaScript en el momento en que se hizo esta pregunta.
Versión ES6 (no competitiva), 33 bytes
Explicación
No hay mucho que decir aquí. Solo estoy implementando la función que me da el artículo de Wikipedia.
fuente
05AB1E , 11 bytes
Pruébalo en línea!
fuente
8vo , 82 bytes
Código
SED (diagrama de efecto de pila) es:
n k -- m
Uso y explicación
El algoritmo usa una matriz de enteros como este: si el valor de las personas es 5, entonces la matriz será [1,2,3,4,5]
fuente
J , 24 bytes
Pruébalo en línea!
Un enfoque iterativo basado en la solución de programación dinámica.
Explicación
fuente
J , 19 bytes
Pruébalo en línea!
Cómo funciona
fuente
Dart , 33 bytes
Pruébalo en línea!
fuente
Japt , 15 bytes
Pruébalo en línea!
Un byte podría salvarse mediante la indexación 0 k , pero en realidad no es un índice, así que decidí no hacerlo.
Explicación:
fuente
Japt
-h
, 10 bytesIntentalo
fuente
Powershell, 56 bytes
¡Importante! El guión se llama a sí mismo de forma recursiva. Así que guarda el guión como
f.ps1
archivo en el directorio actual. También puede llamar a una variable de bloque de script en lugar de un archivo de script (consulte el script de prueba a continuación). Eso llama tiene la misma longitud.Script de prueba:
Salida:
fuente