Die Herausforderung
Für diese Herausforderung müssen Sie feststellen, ob eine bestimmte Nummer im Cantor-Set enthalten ist. Definieren wir zunächst die Cantor-Menge.
Beginnen Sie zunächst mit den Zahlen zwischen 0 und 1. Zahlen außerhalb dieses Bereichs sind nicht im Cantor-Set enthalten. Teilen wir nun die Zahlen in drei gleiche Teile: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Alle Zahlen, die nicht in den Bereichen des ersten und des letzten Parts liegen, sind nicht im Cantor-Set enthalten. Jetzt wiederholen Sie diesen Vorgang für die Segmente [0,1 / 3] und [2/3, 1]. Dann wiederholen Sie, was übrig bleibt. Du machst das immer weiter. Am Ende befinden sich alle verbleibenden Nummern im Cantor-Set. Hier ist ein Diagramm der ersten sechs Iterationen:
Eingang
Zwei Integer x
und y
.
0 < y < 2^15
0 <= x <= y
Der größte gemeinsame Nenner von x
und y
ist 1, es sei denn x == 0
.
Ausgabe
Die Wahrheit ist, wenn sie x/y
im Cantor-Set enthalten ist.
Falsch, wenn x/y
nicht im Cantor-Set.
Beispiele
Sehen wir uns nun einige Beispiele für Zahlen im Cantor-Set an.
1/3 -> true
Es befindet sich an einer Grenze, und Grenzen werden niemals aufgehoben.
1/4 -> true
1/4
befindet sich nie im mittleren Drittel eines Segments, obwohl es sich auch nie an der Grenze befindet. Wenn Sie diesem Pfad folgen, werden Sie feststellen, dass er sich abwechselnd im ersten und letzten Drittel eines Abschnitts befindet.
1/13 -> true
1/13
wechselt zwischen dem ersten, ersten und letzten Abschnitt.
1/5 -> false
1/5
fällt in den ersten leeren Block der dritten Zeile im obigen Diagramm zwischen 1/9 und 2/9.
Andere Testfälle:
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false
Sie können mit diesem Snippet auch andere Nummern ausprobieren:
Zielsetzung
Die Person mit den wenigsten Bytes gewinnt.
quelle
x == 0
Antworten:
Mathematica, 54 Bytes
Unbenannte Funktion, die einen Bruch
x/y
als Eingabe verwendet, woy > 0
und0 ≤ x ≤ y
und zurückTrue
oderFalse
.Eine reelle Zahl zwischen 0 und 1 wird im Cantor genau dann festgelegt, wenn keine der Ziffern in der Erweiterung zur Basis 3 gleich 1 ist. Die Ausnahme ist, dass ein Bruch, dessen Nenner eine Potenz von 3 ist (dessen Basis-3-Erweiterung daher endet), mit einer 1 enden darf.
RealDigits[#,3][[1]]
Gibt alle Ziffern in der Basis-3-Erweiterung der gebrochenen Eingabe#
in einer Form wie{1, 0, 2, {0, 1, 0, 2}}
folgt an: Die letzte Liste ist der periodische Teil der Erweiterung, während die Ganzzahlen zuvor die Ziffern sind, bevor die Periodizität beginnt. Wenn die Basis-3-Erweiterung sofort periodisch ist, ist die Ausgabe ähnlich{{0, 1, 0, 2}}
; Wenn die Base-3-Erweiterung beendet wird, ist die Form ähnlich{1, 0, 2}
.Wir wollen also überprüfen,
~FreeQ~1
ob die Liste frei von1
s ist oder nicht. Aufgrund der abschließenden Erweiterung möchten wir jedoch das letzte Element der Liste löschen, wenn es gleich ist1
. das ist es, wasIf[Last@#===1,Most@#,#]
erreicht. (Das===
wird benötigt, um eine potenzielle Liste zu vergleichen mit1
:==
allein bleibt in dieser Situation unbewertet.)quelle
IsCantorNumber
Funktion hat, um festzustellen, ob es sich bei etwas um eine Ziege handelt .FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
1
s im periodischen Teil entfernen, was zu falschen Antworten führt. Beispielsweise ist die Basis-3-Erweiterung von 7/8 .21212121 .... oder{{2,1}}
; aber die vorgeschlagene Regel würde das ändern{{2}}
, was frei von1
s ist, aber nicht sein sollte.#==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&
? Wenn es beendet wird und nicht Null ist,RealDigits[#,3]
wird es von der Form sein{{__Integer},-1}
und wenn es wiederholt wird, wird es von der Form sein{{___Integer,{__Integer}},-1}
, richtig? Ich bin auf dem Handy, daher ist es schwer, es gerade zu testen. Wenn dies funktioniert, funktioniertRealDigits
möglicherweise auch die Verwendung der Infix-Notation für .C (GCC) ,
615958 ByteNutzt die Symmetrie des Cantor-Sets. Unterbricht nach
y
Iterationen, um eine Endlosschleife zu vermeiden.Probieren Sie es online!
quelle
Jelly ,
22171615 BytesDruckt 3 für wahr, nichts für falsch.
Probieren Sie es online!
Hintergrund
Eine bekannte Eigenschaft der Cantor-Menge ist, dass sie genau die Zahlen zwischen 0 und 1 enthält , die ohne 1 geschrieben werden können ‚s in ihrer ternären Expansion.
Beachten Sie, dass einige Zahlen - genau die rechten Kanten der geschlossenen Intervalle, die an der Konstruktion der Menge beteiligt sind - entweder mit einer einzelnen (nachgestellten) 1 oder mit einer unendlichen Anzahl von nachgestellten 2 geschrieben werden können . Zum Beispiel ist 1 = 1 3 = 0,22222… 3 und 1/3 = 0,1 3 = 0,022222… 3 , genauso wie 0,5 10 = 0,499999… 10 .
Um zu vermeiden, dass die rechten Kanten speziell umschlossen werden, können wir prüfen, ob 1 die kürzeste Dezimalexpansion in x / y und 1 - x / y = (y - x) / y ist , wobei x / y eine rechte Kante ist, wennf (y - x) / y ist eine linke Kante. Wenn mindestens eine von ihnen keine 1 enthält , gehört x / y zum Cantor-Set.
Wie es funktioniert
quelle
3
ist die wahretrue
+1.JavaScript (ES6), 65
67Bearbeite 2 Bytes gespeichert dank @Luke
Weniger golfen
Prüfung
quelle
n=n%d*3
durchq=n/d|0
und dann ersetzenz[n]
durchz[n=n%d*3]
JavaScript (ES6), 55 Byte
Verwenden Sie, indem Sie zuerst den Nenner und dann den Zähler eingeben. Die Standardform ist ein Byte länger:
Erläuterung
Wenn ein Bruch nicht im Cantor-Satz enthalten ist, muss er irgendwann in einen der mittleren Abschnitte fallen. Daher muss seine Darstellung in Basis 3 eine 1 enthalten, auf die irgendwann eine Ziffer ungleich Null folgt. So funktioniert das:
z
Verfolgt, ob wir eine 1 gefunden haben.q
ist die aktuelle Ziffer in Basis 3.!z|!q
ist wahr, wennz
falsch (wir haben keine 1 gefunden) oderq
falsch (die aktuelle Ziffer ist 0).Wenn
n
der Wert auf Null abfällt, bevor wir irgendwo nach einer 1 eine Ziffer ungleich Null finden, befindet sich der Bruch in der Cantor-Menge und wir kehren zurück1
.quelle
Bash + GNU-Dienstprogramme, 62 Bytes
Probieren Sie es online!
Übergeben Sie zwei ganzzahlige Argumente mit arg1 <= arg2 und 0 <arg2.
Die Ausgabe wird im Exit-Code (0 für falsch, 1 für wahr) zurückgegeben, wie dies in PPCG-E / A-Methoden zulässig ist .
Ich vermute, dass die Regex weiter verbessert werden kann, vielleicht sogar, indem der Befehl tr zugunsten der Verwendung von grep -z gestrichen wird, aber dies ist der kürzeste, den ich mir einfallen lassen konnte. (Leider ist grep -z nicht mit grep -P kompatibel, und die Option -P zum Abrufen von regulären Ausdrücken im Perl-Stil ist für die?! -Syntax erforderlich.)
Testprogramm und Ausgabe:
Erläuterung
dc part (die Argumente sind x und y):
tr und grep Teil:
Ein kleines Problem ist, dass dc zwar willkürlich große Ganzzahlen verarbeitet, diese aber beim Drucken einer großen Zahl in 69-stellige Zeilen aufteilt, wobei jede Zeile mit Ausnahme der letzten mit einem Backslash endet und nach jeder Zeile eine neue Zeile.
Der Befehl tr löscht alle Backslashes und Newlines. Dies lässt nur eine einzige Zeile.
Der Befehl grep verwendet dann einen regulären Ausdruck im Perl-Stil (-P-Option, eine GNU-Erweiterung). Der reguläre Ausdruck stimmt überein, wenn die Zeile eine 1 enthält, nicht gefolgt von mindestens y 0 oder mindestens y 2, die dann die Zeichenfolge beenden.
Genau dies ist erforderlich, um x / y als nicht in der Cantor-Menge enthalten zu kennzeichnen, da der sich wiederholende Teil der Basis-3-Darstellung der rationalen Zahl x / y so angesehen werden kann, dass er bei Ziffer # y + 1 nach dem ternären Punkt beginnt und ist höchstens y Ziffern lang.
quelle
CJam (19 Bytes)
Online-Testsuite
Dies ist ein anonymer Block (eine Funktion), der zwei Argumente auf den Stapel nimmt und
0
oder1
auf den Stapel verlässt . Es funktioniert durch die Basis , um die Fraktion Umwandlungx/y
iny
Basis3
Ziffern und gibt true zurück , genau dann , wenn sie nicht enthalten1
oder nur einen1
Teil eines Suffix ist1 0 0 0 ...
.quelle
Pyth , 14 Bytes
Basierend auf meiner C-Lösung.
y
in der ersten Eingabezeile,x
in der zweiten.Ob
x/y
innerhalb des Cantor-Satzes,x
bleibt zwischen0
undy
. Sonstx
wird größer alsy
an einem Punkt und weicht in den verbleibenden Iterationen nach negativ unendlich ab.Probieren Sie es online!
quelle
Batch, 91 Bytes
Testet die ersten
y-1
3 Stellen der Basis vonx/y
.i
ist die Anzahl der getesteten Ziffern.n
ist der nächste Wert vonx
.j
ist wahr, wennn
Null erreicht wird (weil die Erweiterung beendet ist) oder wiry-1
Ziffern getestet haben, ohne a zu finden1
.f
ist wahr, wennj
wahr ist oder wenn die nächste Ziffer a ist1
, an welchem Punkt wir aufhören, eine Schleife zu bilden und auszugebenj
.quelle