n
Entwerfen Sie bei einer positiven Ganzzahl einen Winkelmesser mit der geringsten Anzahl von Markierungen, mit dem Sie alle Winkel messen können, die ein ganzzahliges Vielfaches von 2π/n
(jeweils in einer Messung) sind.
Einzelheiten
Als Ausgabe können Sie eine Liste von Ganzzahlen im Bereich 0
bis n-1
(oder 1
bis n
) ausgeben , die die Position jeder Marke darstellen. Alternativ können Sie eine Zeichenfolge / Liste n
mit einer Länge #
an der Position jeder Marke und einem _
(Unterstrich) ausgeben, wenn keine vorhanden ist. (Oder zwei verschiedene Zeichen , wenn bequemer.)
Beispiel: Für n = 5
Sie müssen genau drei Marken der Lage sein , alle Winkel zu messen , 2π/5, 4π/5, 6π/5, 8π/5, 2π
indem (zum Beispiel) eine Markierung an 0
, eine Markierung an 2π/5
und eine Markierung an 6π/5
. Wir können dies als Liste [0,1,3]
oder als Zeichenfolge codieren ##_#_
.
Beispiele
Beachten Sie, dass die Ausgaben nicht unbedingt eindeutig sind.
n: output:
1 [0]
2 [0,1]
3 [0,1]
4 [0,1,2]
5 [0,1,2]
6 [0,1,3]
7 [0,1,3]
8 [0,1,2,4]
9 [0,1,3,4]
10 [0,1,3,6]
11 [0,1,3,8]
20 [0,1,2,3,6,10]
PS: Dies ähnelt dem Problem mit dem spärlichen Lineal , aber anstelle einer linearen Skala (mit zwei Enden) wird eine kreisförmige (eckige) Skala betrachtet.
PPS: Dieses Skript sollte jeweils ein Beispiel für eine Reihe von Markierungen berechnen n
. Probieren Sie es online!
PPPS: Wie @ngn hervorhob, entspricht dieses Problem dem Auffinden einer minimalen Differenzbasis einer zyklischen Ordnungsgruppe n
. Die Mindestbestellmengen sind unter http://oeis.org/A283297 aufgeführt, und einige theoretische Grenzen finden Sie unter https://arxiv.org/pdf/1702.02631.pdf
n = q^2 + q + 1
um Primärenergie gehtq
.Antworten:
Gelee , 13 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
MATL , 20 Bytes
Dies führt zu einem Speichermangel bei TIO für darüber hinausgehende Eingaben
8
.Probieren Sie es online!
Wie es funktioniert
Dies erzeugt die kartesische Potenz von
[0 1 ... n-1]
mit Exponentn
und verwendet eine Schleife, um jedes kartesische Tupel zu testen. Der Test besteht in der Berechnung alle paarweise Unterschiede des Elements , wenn das Tupel, und zu sehen , ob diese Unterschiede Modulon
umfassen alle Zahlen0
,1
, ...,n-1
.Sobald ein kartesisches Tupel gefunden wird, das die Bedingung erfüllt, wird die Schleife verlassen und die eindeutigen Einträge in diesem Tupel werden als Lösung gedruckt.
Dies funktioniert , weil gegeben u > v , einen ausreichenden Satz von Tupeln mit u eindeutigen Einträgen sind garantiert wird getestet früher als jedes Tupel mit v eindeutigen Einträgen. Eine "ausreichende Menge" bedeutet, dass, wenn keines der Tupel in dieser Menge eine Lösung ist, kein anderes Tupel mit der gleichen Anzahl eindeutiger Einträge eine Lösung ist.
Für
n = 3
die kartesischen Tupel gilt beispielsweise Folgendes:0 0 0
ist das einzige relevante Tupel mit einem1
eindeutigen Wert. Auch wenn1 1 1
und2 2 2
wird viel später erscheinen,0 0 0
ist eine Lösung, wenn und nur wenn diese sind. Die vom Tupel gebildete Singletonmenge0 0 0
ist also eine ausreichende Menge für u =1
.0 0 1
und0 0 2
, bilden eine ausreichende Menge für u =2
; Das heißt, sie decken alle Fälle mit2
eindeutigen Werten ab. Das vierte Tupel0 1 0
wird niemals als Lösung ausgewählt, da0 0 1
es zuerst getestet wurde. Ebenso wird das Tupel0 2 0
nie ausgewählt, da es später als angezeigt wird0 0 2
. Tupel wie2 2 1
werden niemals als Lösung ausgewählt, da sie0 0 1
äquivalent sind (Modulon
und bis zu duplizierten Werten) und zuerst erscheinen.Kommentierter Code:
quelle
Stax ,
2621 BytesOnline ausführen und debuggen!
Momentan schlägt die Online-Version für Eingaben fehl,Deployed20
aber dieser Fehler wurde behoben und muss noch für den Online-Interpreterbereitgestellt werden. Beachten Sie, dass das Ausführen des20
Falls einige Zeit dauert .Erläuterung
Es stellt sich heraus, dass aufgrund der Art und Weise, wie die paarweise Differenz berechnet wird, ich mich nicht um die Äquivalenz von
k
undx-k
hier kümmern muss . 5 Bytes sparen.Verwendet die entpackte Version, um zu erklären.
Durch die Durchsetzung der Forderung , dass
0
und1
beide Mitglieder der Antwort sein, können wir die Powerset mit erzeugen[2..x]
statt[0..x]
und fügen Sie dann das0
und1
manuell auf jedes Element in der Powerset. Es ist effizienter, muss aber1
speziell mit der Eingabe umgehen und kostet mehr Bytes.quelle
Gelee , 17 Bytes
Probieren Sie es online!
-1 Byte danke an Herrn Xcoder
quelle
R
.Python 2 , 148 Bytes
Probieren Sie es online!
quelle