So überprüfen Sie, ob eine Dezimalzahl durch 7 teilbar ist:
Löschen Sie die letzte Ziffer. Multipliziere es mit 2 und subtrahiere von dem, was übrig ist. Wenn das Ergebnis durch 7 teilbar ist, ist die ursprüngliche Zahl durch 7 teilbar.
(auch zB hier beschrieben )
Diese Regel eignet sich für die manuelle Teilbarkeitsprüfung. Beispielsweise:
Ist 2016 durch 7 teilbar?
Subtrahieren
6*2
von 201; wir bekommen 189. Ist das durch 7 teilbar? Um dies zu überprüfen, wenden wir die Regel erneut an.Subtrahieren
9*2
von 18; wir bekommen 0. Deshalb ist 2016 durch 7 teilbar.
Bei dieser Herausforderung sollten Sie diese Regel anwenden, bis der Teilbarkeitsstatus offensichtlich ist , d. H., Die Anzahl ist nicht größer als 70 (Einzelheiten siehe unten). Machen Sie eine Funktion oder ein volles Programm.
Eingabe : eine positive ganze Zahl; Ihr Code sollte Eingaben bis zu 32767 unterstützen (die Unterstützung von Ganzzahlen mit beliebiger Genauigkeit ist ein Bonus; siehe unten).
Ausgabe : eine ganze Zahl (möglicherweise negativ), nicht größer als 70, die das Ergebnis der null- oder mehrmaligen Anwendung der Teilbarkeitsregel durch 7 ist.
Testfälle:
Input Output Alternative output
1 1
10 10 1
100 10 1
13 13 -5
42 42 0
2016 0
9 9
99 -9
9999 -3
12345 3
32767 28 -14
---------- Values below are only relevant for the bonus
700168844221 70 7
36893488147419103232 32 -1
231584178474632390847141970017375815706539969331281128078915168015826259279872 8
Wenn zwei mögliche Ausgaben angegeben sind, ist jedes Ergebnis korrekt: Die zweite entspricht der erneuten Anwendung der Regel. Es ist verboten, die Regel auf eine einstellige Zahl anzuwenden: Wenn Sie die Ziffer löschen, bleibt nichts (nicht 0) übrig.
Bonus : Wenn Ihr Algorithmus
- Unterstützt Ganzzahlen mit beliebiger Genauigkeit
- Führt nur einen Durchgang für die Eingabe aus
- Hat Raumkomplexität
o(n)
(dh weniger alsO(n)
); und - Hat zeitliche Komplexität
O(n)
,
wo n
ist die Anzahl der Nachkommastellen:
Subtrahieren Sie 50% von der Byteanzahl Ihres Codes.
Echter Bonus :
Wenn Ihr Algorithmus die Eingabe ausgehend von der höchstwertigen Ziffer in normaler Richtung liest, subtrahieren Sie 50% erneut - Ihre Punktzahl beträgt 25% Ihrer Byteanzahl (es scheint möglich, aber ich bin mir nicht ganz sicher).
quelle
1000000000000000000001
.long long
s oder ein gleichwertiger Typ integriert ist?Antworten:
Golfscript,
2722 BytesSie können es folgendermaßen verwenden:
Erläuterung
5 Bytes gespart dank Dennis!
quelle
@wizzwizz4
(@
dann meinen Benutzernamen) am Anfang (oder an einer beliebigen Stelle in) eines Kommentars ein.{...}{}if
Teil wie{...}*
folgt umschreiben: Dabei wird der Codeblock je nach dem von gedrückten Wert nur einmal auf Null gesetzt>
. Außerdem sind wir eine weitere Iteration (so ersetzt ausführen darf70
mit9
speichert ein Byte), und ich glaube nicht , dass Sie den Block mit Pop benötigen;
.Haskell, 35 Bytes
Anwendungsbeispiel:
until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232
->32
.Es gibt nicht viel zu erklären, es ist eine direkte Implementierung des Algorithmus.
quelle
Jelly, 11 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Python 2, 38 Bytes
Probieren Sie es hier aus !
Einfacher rekursiver Ansatz. Gibt x aus, wenn <70 andernfalls die Teilungsregel anwendet, und ruft sich selbst mit dem Ergebnis auf.
quelle
)
f=lambda x:x*(x<70)or f(x/10-x%10*2)
x*(x<70) != 0
als Endbedingung. Wenn x - wie bei 2016 - den Wert 0 annimmt, tritt die Endebedingung niemals ein.Pyth, 13 Bytes
Probieren Sie es online aus: Demo oder Test Suite
Dadurch werden alle alternativen Antworten gedruckt.
Erläuterung:
quelle
Julia,
2726 BytesDies ist eine rekursive Funktion, die eine Ganzzahl akzeptiert und a zurückgibt
BigInt
. Wenn die Eingabe wie im letzten Beispiel eine große Zahl ist, analysiert Julia sie als aBigInt
, sodass keine manuelle Konvertierung erforderlich ist.Der Ansatz ist nur eine einfache Implementierung des Algorithmus. Es werden die alternativen Ausgänge erzeugt. Wenn Sie den Modul durch 10 dividieren, erhalten Sie die letzte Ziffer, und der Quotient aus der Ganzzahldivision durch 10 ergibt alles außer der letzten Ziffer.
Dank Dennis ein Byte gespart!
quelle
70
durch9
ein Byte.Pyth, 17 Bytes
Probieren Sie es hier aus!
Gleicher rekursiver Ansatz wie in meiner Python-Antwort . Definiert eine Lambda ,
y
die wie folgt aufgerufen:y12345
.Der Bytezähler im Online-Interpreter zeigt 19 Bytes an, weil ich den Lambda-Aufruf hinzugefügt habe. Sie können ihn also einfach ausprobieren, indem Sie auf die Schaltfläche "Ausführen" klicken.
Erläuterung
quelle
CJam - 19 Bytes
Do-While-Version:
Probieren Sie es online oder während Version 1:
Probieren Sie es online oder während Version 2:
Probieren Sie es online aus .
quelle
Oracle SQL 11.2, 116 Bytes
Nicht golfen
quelle
Haskell,
157192184167159147138 + 5 Bytes - 50% = 71,5 BytesO (1) Raum, O (n) Zeit, Single-Pass!
Verwenden Sie diese Option
0![6,1,0,2]
, um die Regel auf 2016 anzuwenden, dh übergeben Sie eine Zahl in Stream-Form mit der niedrigsten Ziffer zuerst. Auf diese Weise wird die Zahl Ziffer für Ziffer weitergereicht, wobei die Regel mit der Komplexität von O (1) Leerzeichen angewendet wird.Der ungolfed Code ist hier:
Der Kern der Funktionsweise besteht darin, dass ein ziffernweiser Subtraktionsalgorithmus implementiert wird , wobei jedoch die Tatsache ausgenutzt wird, dass jede zu subtrahierende Zahl höchstens 2-stellig ist. Daher können wir eine beliebige Menge dieser 1 -stelligen Zahlen subtrahieren. oder-2 Ziffern von der Hauptziffer (sowie die niedrigstwertigen Ziffern).
Der Subtraktionsalgorithmus ist O (1) und speichert nur den aktuellen Ausleihwert. Ich habe dies geändert, um die zusätzliche Ziffer (entweder 0 oder 1) hinzuzufügen, und wir stellen fest, dass dieser Ausleihwert begrenzt ist (innerhalb des Bereichs [-2,2], sodass wir nur 3 Bits benötigen, um dies zu speichern).
Die anderen im Speicher abgelegten Werte sind temporäre Variablen, die die aktuell zu addierende zweistellige Zahl, eine einzelne Vorausschau im Datenstrom und einen Schritt des Subtraktionsalgorithmus darstellen (dh es werden zwei Ziffern und ein Ausleihwert verwendet und zurückgegeben) eine Ziffer und ein neuer Ausleihwert).
Am Ende werden die letzten beiden Ziffern des Streams gleichzeitig verarbeitet, um eine einstellige Zahl anstelle einer Ziffernliste zurückzugeben.
NB Die
sev
Funktion in der ungolfed Version wird auf einem funktionierenInteger
und es in die umgekehrte Stromform umwandeln.quelle
Mod[18 - Quotient[n, 10] - 2*n, 21] - 18 + Quotient[n, 10]
arbeitet empirisch für n zwischen 10 und 99, wird aber mehr die mehr Stellen komplizieren n ...0
beim Aufruf die Bytes der Initialen zählen!
, z. B. als Abschnitt(0!)
(+ eine neue Zeile), dh +5 Bytes. Auf der anderen Seite können Sie die ersten zu Musterübereinstimmungen von!
bisp![d]=
und kürzenp![d,e]=
. Außerdem schützt Verwendungsmuster statt derlet
:p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
.(0!)
auf einer eigenen Linie.(0!)
ist die Funktion, die Sie als Antwort geben. Das0
ist erforderlich, hat aber nichts mit der Eingabe zu tun, sodass Sie es nicht an den Aufrufer auslagern können. Das könnte man natürlich auch gebrauchenf x=0!x
, aber das ist länger.GNU dc,
2015 BytesDies definiert meine erste (überhaupt) Gleichstromfunktion
F
. Es nimmt die Eingabe oben auf dem Stapel entgegen und belässt die Ausgabe oben auf dem Stapel. Anwendungsbeispiel:quelle
Mathematica,
4744 BytesEinfacher rekursiver Ansatz. Könnte wahrscheinlich weiter golfen werden.
quelle
#0[{1,-2}.QuotientRemainder[#,10]]
Speichert ein Byte.R, 43 Bytes
Erläuterung:
Probeläufe:
quelle
JavaScript ES6, 38 ByteFehler mit
36893488147419103232
und mit~~(1/10)
schlagen ebenfalls fehl700168844221
Prüfung:
quelle
Fail
... 70 und 32f=n=>n>70?f((n-n%10*21)/10):n
ist eine kürzere Version, funktioniert aber immer noch nur für bis zu2**56
.Mathematica, 33 Bytes
Testfall
quelle
Perl 5,
4746 BytesMusste
bigint
für den letzten Testfall verwenden. (Es gibt 20 ohne)Ich bin mir nicht sicher, ob es ein Kandidat für den Bonus ist, deshalb habe ich ihn nicht berücksichtigt. (Ich glaube schon, aber ich bin nicht wirklich an die Konzepte gewöhnt)
Probieren Sie es hier aus!
quelle
ES6, 108 Bytes
Funktioniert für 2²⁵⁷ und 1000000000000000000001, könnte aber weiteres Golfen gebrauchen.
quelle
JavaScript ES6,
140142 BytesDies ist eine echte Mathematik mit willkürlicher Genauigkeit, die sogar für den größten Testfall geeignet ist.
Diese Funktion entfernt rekursiv die letzte Ziffer aus der Zeichenfolge und subtrahiert dann 2 * die letzte Ziffer von der verbleibenden numerischen Zeichenfolge, indem die Anzahl der Stellen, die auf das Minuend angewendet werden sollen, iterativ erhöht wird, bis die Differenz positiv ist. Dann hängt er diese Differenz mit entsprechend aufgefüllten
0
s an das Ende der Zeichenfolge an und ruft sich rekursiv auf, bis sein numerischer Wert kleiner oder gleich ist9
.quelle
1000000000000000000001
.s.replace(/.$/,'-$&*2')
. Ich habe keine offensichtlichen Ideen für den Rest, aber es tut mir leid.C #,
111104 Bytesquelle
Brain-Flak ,
368360 BytesProbieren Sie es online!
Erläuterung
Zu Beginn befindet sich der gesamte Code in einer Schleife, die so lange ausgeführt wird, bis der obere Rand des Stapels kleiner als Null ist:
Innerhalb der Schleife führen wir den durch sieben teilbaren Algorithmus aus:
Duplizieren Sie die Oberseite des Stapels
Nimm den Mod 10 von oben (letzte Ziffer)
Das ist ein bisschen chaotisch, aber es erledigt den Rest des Algorithmus. Vielleicht erkläre ich es später, aber ich erinnere mich nicht ganz, wie es funktioniert:
quelle
C, 56 Bytes - 75% = 14
Dies gibt zwar nicht genau die gleichen Zahlen wie die Testfälle, erfüllt jedoch den Grundgedanken der Frage (und möglicherweise mehr). Es identifiziert die exakten Vielfachen von 7 korrekt und gibt den exakten Rest für andere Zahlen an (da keine negativen Zahlen verwendet werden).
Es gibt keine Multiplikation oder Division im Algorithmus, nur Addition und Subtraktion, und Ziffern werden in einem einzigen Durchgang von links nach rechts verarbeitet. Es funktioniert wie folgt, beginnend mit 0 im Akkumulator:
Der Schritt "Multiplizieren mit drei" wird als geschrieben
n-=-n-n
, um ein Byte zu sparen und den Multiplikationsoperator zu vermeiden.Wenn wir das Ende erreichen, subtrahieren wir keine sieben, sodass das Ergebnis im Bereich von 0 bis 24 liegt. Wenn Sie einen Strengemodul (0-7) wünschen, ersetzen Sie ihn
*c
durch*c||n>6
infor
Schleifenbedingung.Es qualifiziert sich für den erhöhten Bonus, weil es
Testprogramm und Ergebnisse
Alternative Version
Hier ist eine, die wiederkehrt (Sie möchten Compiler-Optimierungen für die Tail-Call-Transformation aktivieren, oder Sie könnten Ihren Stack überlaufen lassen; ich habe sie verwendet
gcc -std=c89 -O3
):Nennen Sie es mit '0' als zweites Argument.
Beide Versionen berechnen den Rest-Modulo-Sieben einer 60.000-stelligen Zahl in weniger als 50 Millisekunden auf meinem Computer.
quelle
PHP, 50 Bytes
verwendet alternative Ausgabe; funktioniert bis zu
PHP_INT_MAX
String-Version, funktioniert für jede (positive) Zahl (64 Bytes):
quelle
Java, 133 Bytes
Ich hasse es, wie wortreich es
Integer.parseInt
ist. Ungolfed:quelle