Es gibt N Türen und K Affen. Zunächst sind alle Türen geschlossen.
Runde 1: Der 1. Affe besucht jede Tür und schaltet die Tür um (wenn die Tür geschlossen ist, wird sie geöffnet; wenn sie offen ist, wird sie geschlossen).
Runde 2 : Der 1. Affe besucht jede Tür und schaltet die Tür um. Dann besucht der 2. Affe jede 2. Tür und schaltet die Tür um.
. . .
. . .
Runde k: Der 1. Affe besucht jede Tür und schaltet die Tür um. . . . . . . . . . Der k-te Affe besucht jede k-te Tür und schaltet die Tür um.
Eingabe: NK (durch ein Leerzeichen getrennt)
Ausgang: Offene Türnummern, jeweils durch ein Leerzeichen getrennt.
Beispiel :
Eingabe: 3 3
Ausgabe: 1 2
Einschränkungen :
0 <N <101
0 <= K <= N
Hinweis :
Angenommen, N Türen sind von 1 bis N nummeriert, und K Affen sind von 1 bis K nummeriert
Der mit dem kürzesten Code gewinnt. Auch Ausgabe für N = 23, K = 21 anzeigen
quelle
n=k=3
würde1 2
so ur falsch ausgeben ... und 5 Ausgänge1 2 4
gibt es ein Muster, aber es ist viel weniger offensichtlich als das.Antworten:
APL,
322826Erklärung
{+/0=⍺|⍨⍳⍵}
ist eine Funktion, die zurückgibt, wie oft door⍺
(linkes Argument) auf round⍵
(rechtes Argument) umgeschaltet wird , was der Anzahl der Faktoren von⍺
≤ entspricht⍵
:⍳⍵
Generieren Sie ein numerisches Array von 1 bis⍵
⍺|⍨
Berechnen Sie den⍺
Modul für jedes Element dieses Arrays0=
Ändern Sie in eine 1, wo es eine 0 gab, und eine 0 für alles andere+/
Summiere das resultierende ArrayDie äußere Funktion:
(⍳⍺)
,⍳⍵
Generiere Arrays von 1 bis N und 1 bis K∘.{...}
Wenden Sie für jedes Elementpaar der beiden Arrays die Funktion an. Dies ergibt eine Matrix, die angibt, wie oft umgeschaltet wurde, wobei jede Reihe eine Tür und jede Spalte eine Runde darstellt.+/
Summiere die Spalten. Dies gibt eine Reihe der Häufigkeit an, mit der jede Tür über alle Runden hinweg umgeschaltet wird.2|
Modul 2, also wenn eine Tür offen ist, ist es eine 1; Wenn es geschlossen ist, ist es eine 0.(...)/⍳⍺
Generieren Sie abschließend ein Array von 1 bis N und wählen Sie nur diejenigen aus, bei denen das Array im vorherigen Schritt eine 1 enthält./⎕
Fügen Sie abschließend die Funktion zwischen die eingegebenen Zahlen ein.BEARBEITEN
,↑⍳¨⍳⍵
Generiere alle "Affen" (Wenn K = 4, dann ist dies1 0 0 0 1 2 0 0 1 2 3 0 1 2 3 4
)⍳⍵
Array von 1 bis⍵
(K)⍳¨
Generieren Sie für jede davon ein Array von 1 bis zu dieser Zahl,↑
Konvertiere das verschachtelte Array in eine Matrix (↑
) und entwirre es dann in ein einfaches Array (,
)(,↑⍳¨⍳⍵)∘.|⍳⍺
⍺
Modifiziere sie für jede Zahl von 1 bis (N) mit jedem Affen.0=
Ändern Sie in eine 1, wo es eine 0 gab, und eine 0 für alles andere. Dies ergibt eine Matrix von Umschaltern: Reihen sind jeder Affe in jeder Runde, Spalten sind Türen; 1 bedeutet ein Umschalten, 0 bedeutet kein Umschalten.+⌿
Summieren Sie die Zeilen, um zu ermitteln, wie oft jede Tür umgeschaltet wirdAndere Teile werden nicht verändert
BEARBEITEN
Verwende XOR reduce (
≠⌿
) anstelle von sum und mod 2 (2|+⌿
)quelle
{}/
anstatt nur N und K als Argumente für die DFN zu verwenden?i←⍳⍺
GolfScript, 33 Zeichen
Wenn Türen beginnend mit Null nummeriert würden, würden 3 Zeichen gespeichert.
Beispiele ( online ):
quelle
Mathematica, 104 Zeichen
Beispiel:
quelle
{n,k}=%~Read~{Number,Number}
.Rubin, 88
Basierend auf der Antwort von @ manatwork.
Diese zwielichtigen Globals brechen immer die Syntaxhervorhebung!
quelle
count
etwas weiter verbessert werden könnte. Ich wünschte Ruby hätte eine eingebaute#sum
Methode fürPython 3,
9784Wenn ein Affe in einer geraden Anzahl von Runden auftaucht, ändert sich nichts daran. Wenn ein Affe mehrmals auftaucht, ist das dasselbe wie in genau einer Runde.
So können einige Affen weggelassen werden und die anderen müssen nur einmal die Türen wechseln.
Ausgabe für
23 21
:quelle
range(2-K%2,K+1,2)
zurange(K,0,-2)
.for
Schleife durch einewhile
Schleife:while K>0:r^=set(range(K,N+1,K));K-=2
R - 74
Simulation:
quelle
Javascript
148127Hier ist eine (winzig kleine) lesbare Version:
DEMO Geige
Ich sollte beachten, dass es beginnt von 0 zu zählen (technisch ein Fehler von eins zu eins)
quelle
b=Array(n);
Dies initialisiert Ihr Array als n Länge, die mit undefined gefüllt ist. ! undefined ist wahr, so dass der erste Affenpass alles in Wahrheiten verwandelt.+1
JavaScript, 153
Ausgabe für N = 23, K = 21:
Getestet in Chrome, verwendet aber keine ausgefallenen neuen ECMAScript-Funktionen und sollte daher in jedem Browser funktionieren!
Ich weiß, dass ich niemals gegen die anderen Einträge gewinnen werde und dass @tryingToGetProgrammingStrainght bereits einen Eintrag in JavaScript eingereicht hat, aber ich habe nicht die gleichen Ergebnisse für N = 23, K = 21 erhalten, wie alle anderen, also dachte ich, ich würde mal meine eigene version ausprobieren.
Edit : Quelle mit Anmerkungen (beim erneuten Hinsehen habe ich Orte gefunden, an denen 3 weitere Zeichen gespeichert werden können, sodass es wahrscheinlich noch verbessert werden kann ...)
quelle
+1
Ruby - 65 Zeichen
Hier ist die Berechnung in Pseudocode:
Wenn Sie nicht davon überzeugt sind, dass der Ausdruck für s (d) korrekt ist, sehen Sie ihn folgendermaßen an:
quelle
n
und woherk
? Und die Ausgabe scheint eher durch Zeilenumbrüche als durch Leerzeichen getrennt zu sein.PowerShell: 132
Golf Code:
Nicht Golf spielender, kommentierter Code:
quelle
Powershell, 66 Bytes
Testskript:
Ausgabe:
quelle