Wir definieren eine Collatz- ähnliche Sequenz smit 4 positiven ganzen Zahlen:

• n Startwert
• d > 1 Divisor
• m > 1 Multiplikator
• i Zuwachs

(In der Original-Collatz-Sequenz d = 2 m = 3und i = 1.)

Ausgehend von diesen ganzen Zahlen swird auf folgende Weise erstellt:

• s(0) = n
• wenn k > 0und s(k-1) mod d = 0danns(k) = s(k-1) / d
• wenn k > 0und s(k-1) mod d != 0danns(k) = s(k-1) * m + i

Eine Beispielsequenz mit d = 2, m = 3, i = 5und n = 80wird sein s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Jede Sequenz erreicht entweder höhere Werte als eine bestimmte Grenze (dh die Sequenz ist divergent) oder gerät in eine Endlosschleife, wenn für einige tund u( t!=u) die s(t) = s(u)Gleichheit wahr ist.

In unserem Problem gilt die Sequenz als divergent, wenn der Wert eines Sequenzelements größer ist als 10^9oder es keine Elementwiederholung vor dem 1000dritten Element gibt.

Die Aufgabe

Sie sollten ein Programm oder eine Funktion schreiben, die die positiven ganzen Zahlen verwendet d mund ialle Endtypen der Folgen (Endlosschleifen und Divergenz), die die Startwerte erzeugen n = 1, 2, 3, ... 999, 1000können, als Ein- und Ausgänge verwendet.

Eingabedetails

• Die Eingabe ist eine Zeichenfolge oder Liste (oder Äquivalente in Ihrer Sprache) , die (in gewohnter Weise) drei positive ganze Zahlen sind d, mund iin dieser Reihenfolge. dund msind zumindest 2. Weder Nummer ist größer als 100.

Ausgabedetails

Die Ausgabespezifikation ist etwas wortreich. Vielleicht lohnt es sich, zuerst die Beispiele zu lesen.

• Sie sollten auf die Standardausgabe (oder die nächstgelegene Alternative) ausgeben oder eine Zeichenfolge zurückgeben.
• Wenn eine abweichende Reihenfolge möglich ist, sollte die erste Zeile sein DIVERGENT.
• Eine eindeutige Darstellung der Schleife einer Sequenz ist die Drehung, bei der die kleinste Zahl durch Leerzeichen getrennt ist. ZB wenn s = 2 1 4 2 1 4 2 1die Schleife ist 4 2 1.
• In jeder folgenden Zeile sollten Sie jede einzelne Schleife genau einmal vor dem Wort ausgeben LOOP. Z.BLOOP 4 2 1
• Die Schleifen sollten in Bezug auf ihr letztes Element in aufsteigender Reihenfolge sein.
• Der Zeilenumbruch ist optional.

Beispiele:

Die ersten Zeilen sind die Eingänge und die folgenden, bis eine leere Zeile die Ausgänge sind.

2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46

Referenzimplementierung in Python 3 auf Ideone.

Dies ist Code-Golf, also gewinnt der kürzeste Einstieg.

Python 3, 269 254 252 246 Bytes

d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3<1e9>=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d>0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1])

(Jetzt 10-mal langsamer, um ein paar Bytes zu sparen. Typischer Code Golf.)

Geben Sie eine Liste über STDIN ein (zB [2, 3, 1]). Ich denke, es muss einen besseren Weg geben, die Zyklen zu standardisieren ...

Der Ansatz ist recht einfach: Testen Sie alle 1000 Zahlen und nehmen Sie nur die eindeutigen Ausgaben. Es gibt jedoch zwei kleine Tricks:

• Schleifen werden durch nicht leere Tupel dargestellt, aber was noch wichtiger ist, Divergenz wird durch ein leeres Tupel dargestellt. Das ist gut, weil:

  • Es wird nicht unterbrochen sortedund sogar vor allen Loop-Tupeln angezeigt
  • Es ermöglicht uns, eine Zeichenfolge über auszuwählen x and"LOOP"or"DIVERGENT"
  • *()[::-1] wirkt sich nicht aus print
• Die Schleifen sind rückwärts aufgebaut, um "Aufsteigend nach letztem Element sortieren" in "Aufsteigend nach erstem Element sortieren" umzuwandeln, sodass kein Lambda übergeben werden muss sorted.

Vorherige Einreichung, 252 Bytes

d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d>0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x>1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1])

Das ist viel schneller.