Ihre Aufgabe ist es, eine natürliche Zahl mit der geringsten Anzahl von Einsen und nur den Operatoren +
oder zu erstellen -
. Zum Beispiel kann die Zahl Sieben geschrieben werden 1+1+1+1+1+1+1=7
, aber es kann auch als geschrieben werden 11-1-1-1-1=7
. Der erste verwendet 7
diejenigen, während der letztere nur verwendet 6
. Ihre Aufgabe ist es, die Mindestanzahl von Einsern zurückzugeben, die bei Eingabe einer natürlichen Zahl verwendet werden können n
.
Dies ist Codegolf, daher gewinnt der kürzeste gültige Code in Bytes.
Testfälle
Eingabe => Ausgabe
0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21
code-golf
number-theory
Codecomputer
quelle
quelle
VALID OUTPUTS
. Sie haben die Wahl, aber im Allgemeinen mögen die Leute Fettdruck oder Kursivdruck anstelle von GROSSBUCHSTABEN (sie lassen es so aussehen, als würden Sie schreien, anstatt es hervorzuheben). Fett**bold text**
und kursiv*italics text*
. Sie könnten auch### Text
für fetteren Text verwenden. Wie auch immer, willkommen bei PPCG!Antworten:
JavaScript (ES6),
12712687 ByteSollte bis ungefähr 10
1415 funktionieren. Ab diesem Punkt stoßen Sie auf die Ganzzahlgrenzen von JavaScript. Erläuterung:Dies nutzt die
n*9
Magie zweimal; Erstens, es gibt mir die Länge der nächsten Repunit - Zahl, zweitens, wenn die ersten beiden Ziffernn*9
sind55
oder höher, dann müssen wir subtrahierenn
von der nächsten Repunit - Zahl, sonst müssen wir die vorherige Repunit - Zahl (die durch Subtrahieren von 1 berechnet wird , subtrahieren und durch 10 teilen). Dies sollte bis zu 10 15 funktionieren .quelle
Pyth,
1916 BytesTestsuite
Brute-Force-Algorithmus. Die erforderlichen Zeichenfolgen werden generiert, indem alle Listen, deren Elemente
['+', '-', '']
gleich der Anzahl der zu testenden Einsen lang sind, mit einer 1 versehen und zu einer einzelnen Zeichenfolge verkettet werden. Diese Zeichenfolgen werden dann ausgewertet und mit der Eingabe verglichen. Dies wird wiederholt, bis eine erfolgreiche Zeichenfolge gefunden wurde.Einige Zeichenfolgen mit einem führenden
+
oder-
werden getestet, dies ist jedoch kein Problem. Es wäre allerdings, wenn die Eingabe negativ wäre.Es kann bis zu einer Länge von 9 laufen, bevor es zu langsam wird.
Erläuterung:
quelle
JavaScript (ES6), 92 Byte
Erläuterung
Rekursive Funktion. Dies erzeugt alle möglichen Permutationen von
1
s, die entweder+
durch-
oder durch nichts getrennt sind. Dazu wird eine Zahl zur Basis 3 inkrementiert, in ein Array von Ziffern umgewandelt, jede Ziffer0
in-
,1
in+
und2
in eine leere Zeichenfolge konvertiert und anschließend mit1
s verbunden. Die resultierende Zeichenfolge isteval
d als JavaScript-Anweisung, die das Ergebnis der Gleichung zurückgibt.Da die Operatoren mit
1
s in between (like+1+1+1+
) verbunden sind, gibt eslength - 1
1
s. Der erste Operator wird ignoriert (da+1
=1
,<nothing>1
=1
und es ist eine Zahl , so wird es nie ein führender sein0
für-
) und der letzte Operator wird auch ignoriert (durch Anhängen.0
der Gleichung).Höhere Ausgabeversion, 96 Bytes
Die andere Version kann aufgrund des Rekursions-Call-Stack-Limits keine höheren Ausgaben als ~ 10 zurückgeben. Diese Version verwendet eine for-Schleife anstelle einer Rekursion, sodass Ausgaben bis zu ~ 33 zurückgegeben werden können. Der Zeitaufwand steigt jedoch exponentiell an, weshalb ich das Testen nicht empfehle.
quelle