Eine Funktion wird gesagt , ein haben Zyklus der Länge n , wenn es eine gibt x in seiner Domäne , so dass f n (x) = x und f m (x) ≠ x für 0 <m <n , wobei der Exponent n Bezeichnet n - Falte Anwendung von f . Beachten Sie, dass ein Zyklus der Länge 1 ein fester Punkt f (x) = x ist .
Ihre Aufgabe ist es, eine bijektive Funktion von den ganzen Zahlen zu sich selbst zu implementieren , die genau einen Zyklus jeder positiven Länge n hat . Eine bijektive Funktion ist eine Eins-zu-Eins-Entsprechung, dh jede Ganzzahl, die genau einmal zugeordnet ist. Genau einen Zyklus der Länge n zu haben bedeutet, dass es genau n verschiedene Zahlen x gibt, für die f n (x) = x und f m (x) ≠ x für 0 <m <n ist .
Hier ist ein Beispiel, wie eine solche Funktion um x = 0 aussehen könnte :
x ... -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
f(x) ... 2 4 6 -3 -1 1 -4 0 -2 5 7 -7 -6 3 -5 ...
Dieser Auszug enthält Zyklen der Länge 1 bis 5 :
n cycle
1 0
2 -2 1
3 -4 -3 -1
4 -5 6 3 7
5 -7 2 5 -6 4
...
Beachten Sie, dass ich oben "Funktion" nur im mathematischen Sinne verwende. Sie können entweder eine Funktion oder ein vollständiges Programm in der Sprache Ihrer Wahl schreiben, sofern eine einzelne (vorzeichenbehaftete) Ganzzahl als Eingabe verwendet und eine einzelne (vorzeichenbehaftete) Ganzzahl zurückgegeben wird. Wie üblich können Sie Eingaben über STDIN, Befehlszeilenargument, Funktionsargument usw. und Ausgaben über STDOUT, Funktionsrückgabewert oder Funktionsargument (out) usw. vornehmen.
Natürlich unterstützen viele Sprachen (leicht) keine Ganzzahlen mit beliebiger Genauigkeit. Es ist in Ordnung, wenn Ihre Implementierung nur für den Bereich des nativen Integer-Typs Ihrer Sprache funktioniert, sofern dieser mindestens den Bereich [-127, 127] abdeckt und für beliebige Ganzzahlen funktioniert, wenn der Integer-Typ der Sprache durch einen beliebigen Integer-Typ ersetzt wird. Präzisions-Ganzzahlen.
Es gelten die Standardregeln für Code-Golf .
quelle
Antworten:
Pyth,
2718 BytesErläuterung (Pyth wird
Q
mit der Eingabe-Ganzzahl initialisiert ):Dies hat Zyklen
(–1)
(0, –2)
(1, –3, –4)
(2, –5, –7, –6)
(3, –9, –13, –11, –8)
(4, - 17, -25, -21, -15, -10)
(5, -33, -49, -41, -29, -19, -12)
(6, -65, -97, -81, -57, -37, -23, -14)
(7, -129, -193, -161, -113, -73, -45, -27, -16)
(8, -257, -385, -321, -225 , –145, –89, –53, –31, –18)
(9, –513, –769, –641, –449, –289, –177, –105, –61, –35, –20)
⋮
Der Zyklus der Länge n ist gegeben durch
( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1,
−2 ^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
−2 ^ 1⋅ (2 · n - 5) - 1,
−2 ^ 0⋅ (2 · n - 3) - 1).
Jede ganze Zahl k ≥ −1 erscheint als erstes Element des ( k + 2) -Zyklus. Für jede ganze Zahl k <−1 können wir 1 - k = 2 ^ i ⋅ (2⋅ j + 1) für einige i , j ≥ 0 eindeutig schreiben ; dann erscheint k als das ( j + 2) -te Element des ( i + j + 2) -Zyklus.
quelle
MATL , 47 Bytes
Probieren Sie es online aus!
Allgemeine Erklärung
Die folgende Funktion 2 entspricht der Antwort von @ Sp3000 auf die entsprechende Herausforderung. Vielen Dank an @ Agawa001 für das Bemerken.
Die Funktion ist die Zusammensetzung von drei:
Die Funktionen 1 und 3 werden verwendet, weil es (glaube ich) einfacher ist, das gewünschte Verhalten in N als in Z zu erreichen .
Funktion 2 lautet wie folgt: Die obere Zeile ist die Domäne, die untere Zeile ist die Codomäne. Kommas werden aus Gründen der Übersichtlichkeit verwendet:
Der erste Block (von oben
1
nach unten1
) ist ein Zyklus der Länge 1. Der zweite (von2 3
bis3 2
) ist ein Zyklus der Länge 2 usw. In jedem Block ist der untere Teil (Bild der Funktion) der obere Teil kreisförmig verschoben einen Schritt nach rechts.Funktion 1 ist wie folgt:
Funktion 3 ist dieselbe wie 1, wobei die beiden Zeilen vertauscht sind.
Beispiele
Das Bild von
3
ist-5
. Zuerst3
wird7
durch Funktion 1 abgebildet ; wird dann durch Funktion 27
abgebildet10
; wird dann10
durch Funktion 3 auf -5` abgebildet.Der Zyklus der Länge 1 ist
0
. Der Zyklus der Länge 2 ist-1 1
. Der Zyklus der Länge 3 ist-3 2 -2
usw.Code erklärt
Die Funktionen 1 und 3 sind unkompliziert.
Funktion 2 ermittelt den unteren Endpunkt des entsprechenden Eingabeblocks. Wenn zum Beispiel der Eingabe dieser Funktion ist
9
es findet7
(siehe Blöcke oben). Anschließend wird der obere Endpunkt ausgewählt, der sich10
im Beispiel befindet. Die kreisförmige Verschiebung des Blocks wird dank der 1-basierten, modularen Indizierung von MATL erreicht.quelle
Python 2, 55 Bytes
59 Bytes:
Erstellt die Zyklen
Geändert von meiner Lösung auf der früheren Herausforderung , die von der Sp3000-Konstruktion modifiziert wurde .
Die Funktion
macht ungerade Zyklen von nicht negativen Zahlen
Um die richtige Zyklusgröße zu finden
k
, verschieben Sie die Eingaben
um,k=1,3,5,7,...
bis das Ergebnis im Intervall liegt[0,k)
. Durchlaufen Sie dieses Intervall mit der Operationn->(n+1)%k
und machen Sie dann alle an der Eingabe vorgenommenen Subtraktionen rückgängig. Dies wird rekursiv von implementiertk+g(n-k,k+2)
.Jetzt brauchen wir das Negative, um die geraden Zyklen zu machen. Beachten Sie, dass wir Zyklen mit gerader Größe erhalten , wenn wir
g
zunächst mitk=2
in änderng
Diese werden über das Bit-Komplement negativ
~
. Wennn
also negativ ist, bewerten wir einfachg(n)
als~g(~n,2)
.quelle
k
scheint zu seinMath.floor(Math.sqrt(n))*2+1
.Python 3, 110 Bytes
Ich habe immer noch nicht herausgefunden, wie ich dort ein Lambda bekommen kann
Wenn n eine Dreieckszahl ist [1,3,6,10,15,21,28 usw.], dann ist f (n) die Reihenfolge in der Liste multipliziert mit der negativen. Wenn die Zahl negativ ist, geben Sie 1 + die nächstkleinere Dreieckszahl. sonst inkrementieren.
Beispiel: 5 ist keine Dreieckszahl, also addiere 1.
Bei der nächsten Iteration haben wir 6. 6 ist eine Dreieckszahl und es ist die 3. in der Liste, also kommt -3 heraus.
Das Programm gibt diese Listen
Länge 1: [0]
Länge 2: [1, -1]
Länge 3: [2,3, -2]
Länge 4: [4,5,6, -3]
Länge 5: [7,8,9,10, -4]
Bearbeiten: Nochmals vielen Dank an @TuukkaX für das Entfernen überschüssiger Zeichen.
quelle
0.5
zu.5
undinput('')
zu wechselninput()
.Python 3, 146 Bytes
Für jede Zahl größer als 0 gibt es gerade Schleifen (len 2,4,6,8 ...) und ungerade Schleifen kleiner als 0 (1,3,5,7). 0 ist 0 zugeordnet.
(-3, -2, -1), (0), (1,2), (3,4,5,6)
Karten zu
(-2, -1, -3), (0), (2,1), (6,3,4,5)
Bearbeiten: @TuukkaX hat 8 Bytes von der vorherigen Lösung entfernt. Und noch 3.
quelle
mi
könnte in etwas kleineres geändert werden, wie zb
.f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
input('')
zuinput()
. Die Anführungszeichen sind nutzlos, da wir nichts auf die Konsole drucken müssen, wenn wir nur die Eingabe erhalten möchten.f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Matlab (423)
Nicht konkurrierend, weil es einen guten Rekord bricht, für das letzte Ranking kondidiert zu sein, während ich mich bemühe, es so kurz wie möglich zu halten.
Einige nicht-sensorische Fehler in Bezug auf die Genauigkeit in Matlab, die ich nur herausfinden konnte, wenn ich meinen Code sarkatistisch groß machte. Andererseits war die Zuordnung, für die ich mich entschied, in Bezug auf Hauptfaktoren und n-ary Logarithmus.
Ausführung
Erläuterung
Zunächst wusste ich, dass jede Zahl als Produkt von Exponenten von Primzahlen
N=e1^x1*e2^x2...
aus dieser Basis geschrieben werden kann. Ich entschied mich, Bilder von Zyklen abzubilden,C
die aus dem größten Exponenten des kleinsten Faktors (nicht unbedingt der Primzahl) extrahiert werden, dessen perfekte Potenz N ist .in einfacheren Worten,
N=P^x
wenn P die kleinste perfekte Wurzel ist,x
bezeichnet genau zwei wesentliche Terme für den Zyklus:x=Ʃ(r*P^i)
Ein TermP
ist die Basis des Zyklus sowie eine perfekte Wurzel für die Hauptzahl N undk
ist der Grad des ZyklusC=p^k
, wobeii
variiert zwischen 1 und k, wird der Koeffizientr
für jedes folgende Vorbild um 1 erhöht und durch P-1 begrenzt, bis alle Koeffizienten auf r = 1 gesetzt sind, also bewegen wir uns zum Beginn dieses Zyklus.Um Kollisionen zwischen Zyklen zu vermeiden, ist die Wahl der Exponentiation von Primzahlen anstelle ihrer Produkte genau, da als Beispiel für zwei Zyklen von Basen
3
und2
einem Treffpunkt zwischen ihnen3*2
dies vermieden werden kann, da ein Zyklus durch seinen Grad mehr als seinen definiert wird Basis, und für den Treffpunkt gibt es einen weiteren Zyklus von Basis6
und Grad 1.Negative Zahlen stellen eine Ausnahme dar, da ich ungerade Grade für negative Zahlen und gerade Grade für den Rest reserviert habe. Wie ?
Für jede in einen Zyklus eingebettete Zahl N
P^k
wird geschriebenP^(a0*P^i0+a1*P^i1+...)
, dass die Menge(a0*P^i0+a1*P^i1+...)
in P-ary-Basis als transaltierta0,a1,....
wird, um diesen Punkt zu verdeutlichen, wenn (p = 2) die Sequenz in binärer Basis sein muss. Wie vorab bekannt ist, ohne die Bedingung für positive / negative Grade und die Ausnahme (+/- 1) festzulegen, befindet sich eine Zahl Nk
genau dann an den Rändern eines Gradzyklus, wenn die SequenzA
als1111..{k+1}..10
oder111..{k}..1
für alle Basen geschrieben ist, andernfalls Es ist keine Drehung erforderlich, so dass durch Zuweisen einer negativen / positiven Bedingung für einen jeweiligen ungeraden / geraden Gradk/k'
für beide eine ungerade Sequenz in der Form geschrieben wird101..{k}..100
, eine gerade Sequenz in der Form101..{k'}..10
für eine Anfangskante eines jeweils negativen / positiven Zahlenzyklus geschrieben wird .Beispiel:
Wenn man eine Zahl
N=2^10
nimmtx=10=2^1+2^3
, die Sequenz A geschrieben istA=1010
, symptomatisiert diese Art von Sequenz eine endliche Flanke des positiven Zahlenzyklus, das heißtC=2^3
, das nächste Bild ist das der Anfangskante,A=011
das heißt8
, aber indem man dieses Ergebnis auf (+ / standardisiert) -) 1 Ausnahme2^10/2
wird zugeordnet8/2
und das vorherige Bild darf nicht gedreht werden.Wenn man eine Zahl
N=-3^9
nimmtx=9=3^2
, wird die Folge A geschriebenA=100
, diese Art von Folge symptomatisiert eine endliche Flanke des negativen Zahlenzyklus, das heißtC=3^1
, das nächste Bild ist das der Anfangskante,A=01
das heißt3
, aber durch Anpassen dieses Ergebnisses an negativ / positiv Zustandskarten-3^9
zu-3
.Für das Paar
(-/+)1
hatte ich vor, es innerhalb einer Anzahl von Zyklusbasen einzudringen2
, in dem Deckmantel, dass eine gewöhnliche Folge von zyklischen Gruppen{2,4}{8,16,32,64}..
in einer anderen Form gebildet wird{1,2}{4,8,16,32}..
, dies verhindert den Verlust vorheriger Elemente, und die durchgeführte Opeation verschiebt sich nur mit dem Knallen ein neues Element in.Ergebnisse:
Führen Sie dieses kleine Codeblatt aus, um die ersten vernünftigen Bereiche zyklischer Zahlen zu überprüfen:
Dies führt zu diesen Ergebnissen
Der letzte ist ein Segmentierungsfehler, der jedoch in den Standardbereich für vorzeichenbehaftete Ganzzahlen [-127,127] passt.
quelle
JavaScript (ES6), 73 Byte
Zählt die Sequenz (0, -1, 1, -2, 2, -3, 3, ...) auf, bis sie gefunden wird
n
, und zählt dabei die Zyklen.i
enthält den aktuellen Eintrag;j
enthält den Beginn des aktuellen Zyklus,k
den Index innerhalb des Zyklus,l
die Länge des aktuellen Zyklus undm
den nächsten Eintrag in der Sequenz. Sobald wir gefundenn
haben, nehmen wir,j
ob wir am Ende eines Zyklus sind oderm
nicht.quelle