Ein Standardlineal der Länge n hat Abstandsmarkierungen an den Positionen 0, 1, ..., n (in welchen Einheiten auch immer). Ein dünn besetztes Lineal hat eine Teilmenge dieser Marken. Ein Lineal kann den Abstand k messen, wenn es Markierungen an den Positionen p und q mit p - q = k hat .
Die Herausforderung
Geben Sie bei einer positiven Ganzzahl n die Mindestanzahl von Markierungen aus, die in einem dünnen Lineal der Länge n erforderlich sind , damit alle Abstände 1, 2, ..., n gemessen werden können .
Dies ist OEIS A046693 .
Als Beispiel für die Eingabe 6 ist die Ausgabe 4. Ein Lineal mit den Markierungen 0, 1, 4, 6 funktioniert also wie folgt: 1−0 = 1, 6−4 = 2, 4−1 = 3, 4−0 = 4, 6-1 = 5 und 6-0 = 6.
Zusätzliche Regeln
- Der Algorithmus sollte für beliebig große n gültig sein . Es ist jedoch akzeptabel, wenn das Programm durch Speicher-, Zeit- oder Datentypbeschränkungen eingeschränkt ist.
- Input / Output kann auf jede vernünftige Weise genommen / produziert werden .
- Programme oder Funktionen sind in jeder Programmiersprache zulässig . Standardlücken sind verboten.
- Kürzester Code in Bytes gewinnt.
Testfälle
1 -> 2
2 -> 3
3 -> 3
4 -> 4
5 -> 4
6 -> 4
7 -> 5
8 -> 5
9 -> 5
10 -> 6
11 -> 6
12 -> 6
13 -> 6
14 -> 7
15 -> 7
16 -> 7
17 -> 7
18 -> 8
19 -> 8
20 -> 8
21 -> 8
22 -> 8
23 -> 8
24 -> 9
25 -> 9
26 -> 9
27 -> 9
28 -> 9
29 -> 9
30 -> 10
31 -> 10
32 -> 10
Antworten:
Jelly , 14 Bytes
Eine monadische Verknüpfung, die nicht negative ganze Zahlen aufnimmt und zurückgibt.
Probieren Sie es online! (erste 15 Werte hier - nicht effizient)
Wie?
Findet alle Lineale, die man mit den Markierungen 1 bis n + 1 (Potenzmenge von [1, n + 1]) machen kann, geordnet nach der Anzahl der Markierungen, und behält nur die bei, die maximal messbare Abstände schaffen (die Länge der Differenzmenge zwischen allen geordneten Markenpaaren), gibt dann die Länge der ersten zurück (dh [eine der] kürzesten [s]).
quelle
Wolfram Language (Mathematica) , 65 Byte
Probieren Sie es online!
quelle
Mathematica, 84 Bytes
Probieren Sie es online!
quelle
Pyth , 14 Bytes
Probieren Sie es hier aus!
Pyth ,
21 bis19 BytesProbieren Sie es hier aus!
Wie es funktioniert
Ich werde dies nach dem Golfen aktualisieren.
Vielen Dank an Isaacg , der ein Byte für meinen zweiten Ansatz gespeichert und mich dazu inspiriert hat, 3 Byte von meinem aktuellen Ansatz abzuweichen !
quelle
S
nicht erforderlich .Python 2 ,
129128126 Bytesdanke an totalhuman für -1 byte
Probieren Sie es online!
Die Ausgabe erfolgt über den Exit-Code
quelle
Schale ,
20 bis18 BytesDanke @ H.PWiz für -2 Bytes!
Probieren Sie es online!
Erläuterung
quelle
oa-
ist das gleiche wie≠
≈
.Gelee , 17 Bytes
Probieren Sie es online!
Dank Jonathan Allan 1 Byte gespart !
quelle
ḢL
Pyth, 15 Bytes
Testsuite
Wie es funktioniert
quelle
Gelee , 17 Bytes
Probieren Sie es online!
Aus Mr. Xcoders Antwort für -1 einen Trick entlehnt .
-1 Danke an Jonathan Allan .
quelle
ḢL
Ruby , 98 Bytes
Probieren Sie es online!
quelle