Ich habe versucht Lass uns bye-byeman zählen. Es war mein erstes Mal, dass ich Code Golf gespielt habe, aber ich bin mit 51B (eijit) in Python an die Spitze gegangen. Es hat Spaß gemacht, durch Versuch und Irrtum zu verirren, also werde ich ein Protokoll führen.
Wenn Sie sich nur schwer vorstellen können, wie Sie den Bye-byeman erhöhen können, lesen Sie auch So erhöhen Sie den Bye-byeman.
Die folgende Tabelle zeigt die Anzahl und Gesamtzahl der Bye-Byemen jeder Größe für jede Generation.
| Generation | c(1, n) | c(2, n) | c(4, n) | c(8, n) | c(6, n) | s(n) |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 0 | 1 | 2 |
| 5 | 1 | 2 | 0 | 0 | 0 | 3 |
| 6 | 0 | 1 | 2 | 0 | 0 | 3 |
| 7 | 0 | 0 | 1 | 2 | 0 | 3 |
| 8 | 2 | 0 | 0 | 1 | 2 | 5 |
| 9 | 3 | 4 | 0 | 0 | 1 | 8 |
Hier
Repräsentiert. Dann wirst du sofort verstehen
Und die Summe der Bewegung von der einen kleineren Population der vorherigen Generation (s = 6 wird als zu s = 1 verschoben angesehen) und dem "Übertrag" aus der Aufteilung der Größen 8 und 6 der vorherigen Generation Ich kann die Beziehung sehen.
Zuerst schrieb ich einen Code von weniger als 400B und reichte ihn ein, ohne zu bemerken, dass es Code Golf war, aber später bemerkte ich es und versuchte ihn zu verkürzen.
c=[1]+[0]*4
for i in range(100):
print sum(c)
c=c[4:]+c[:4]
c[1]+=c[0]
c[0]+=c[4]
Das war 85B. Ich habe ein Array verwendet, um die Elemente zu speichern. Ich habe es mir ausgedacht
war. Als ich mir die Ergebnisse ansah, war ich schockiert, dass ich meine Zähne nicht ausstehen konnte und begann, Code Golf zu studieren.
Ich habe die Artikel im Internet durchgesehen und Folgendes gelernt.
c=[1]+[0]*4;exec"print sum(c);c=c[4:]+c[:4];c[1]+=c[0];c[0]+=c[4];"*100
Dies hat 14B geschrumpft. Aber es ist immer noch nicht genug.
Ich habe festgestellt, dass die Kosten für den Zugriff auf die Elemente des Arrays hoch sind, und habe sie daher durch fünf Variablen wie a, b, c, d und e ersetzt.
a=1;b=c=d=e=0;exec"print a+b+c+d+e;f=a+d;a=d+e;c=b;d=c;e=d;b=f"*100
Dies schrumpfte 4B weiter. Es ist jedoch nutzlos, die temporäre Variable f zu verwenden.
Als ich Code Golf studierte, erinnerte ich mich an das Thema Tauschen ohne temporäre Variablen.
a=1
b=2
a,b=b,a
Die Syntax ist wie. Wenden Sie dies an
a=1;b=c=d=e=0;exec"print a+b+c+d+e;a,b,c,d,e=d+e,a+e,b,c,d;"*100
Es schrumpfte 3B weiter. Ich habe es geschafft, in den Bereich der Abzeichenerfassung zu gelangen, aber die Spitze ist immer noch ein verzweifelter Unterschied zu 50B.
Schauen Sie sich den Code hier an
print a+b+c+d+e
a=d+e
b=a+e
Mir ist aufgefallen, dass die Berechnung doppelt vorhanden ist. Ich fragte mich, ob dies verwendet werden könnte
a=1;b=c=d=e=0;exec"a,b,c,d,e=d+e,a+e,b,c,d;print b+c+d+e;"*100
Und um 2B weiter geschrumpft. Hier
Ich mache das
Bis zu diesem Punkt dachte ich, dass diese Richtlinie den Code nicht mehr schneiden könnte, also ging ich zurück zu den Grundlagen und sah mir konkrete Beispiele an, um zu sehen, ob es eine andere Regel gibt.
Dann
s(n) = s(n-1) + c(1, n)
Es schien eine Regel zu geben. In Anbetracht des Grundes war dies eine Selbstverständlichkeit. Die Bye-byeman-Populationen nehmen zu, wenn die Größen 8 und 6 in der nächsten Generation zu den Größen 16 und 12 werden und in die Größen 1, 6 und 1, 2 aufgeteilt werden. Die Personen, die zu diesem Zeitpunkt zugenommen haben, können als Personen der Größe 1 angesehen werden.
Als ich es basierend auf dem Ergebnis dieser Analyse implementierte, erhöhte es sich leider um 1B aufgrund der Variablen zum Halten der Summe.
a=1;b=c=d=e=s=0;exec"s+=a;print s;a,b,c,d,e=d+e,a+e,b,c,d;"*100
Ich habe bestätigt, dass die Ergebnisse korrekt sind, daher werde ich diese Richtlinie etwas weiter verfolgen.
Ich war mir sehr bewusst, dass es notwendig war, die verwendeten Variablen zu reduzieren, und fragte mich, ob es möglich sein würde, die Anzahl der Personen der Größe 1 bequem zu berechnen.
(Ersetzen Sie die bisher verwendeten Symbole c (1, n) usw. durch $ c_ {1, n} $)
Denken Sie daran, dass wir davon ausgehen, dass $ c_ {1, n} = c_ {6, n-1} + c_ {8, n-1} $ in 1. nur durch den Term der Größe 1 dargestellt wird.
\begin{eqnarray*}
c_{1, n} &= c_{6, n-1} + c_{8, n-1}\\
&=c_{8, n-2} + c_{4, n-2}\\
&=c_{4, n-3} + c_{2, n-3}\\
&=c_{2, n-4} + c_{1, n-4} + c_{6, n-4}\\
&=c_{1, n-5} + c_{6, n-5} + c_{1, n-4} + c_{8, n-5}\\
&=c_{1, n-5} + c_{1, n-4} + c_{6, n-5} + c_{8, n-5}\\
&=c_{1, n-5} + c_{1, n-4} + c_{1, n-4}\\
&=c_{1, n-5} + 2c_{1, n-4}\\
\end{eqnarray*}
Wann
c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
Ich fand, dass es ausgedrückt werden kann durch.
Lassen Sie uns dies nun lösen, da es sich um eine allmähliche Gleichung zwischen benachbarten sechs Termen handelt. Die charakteristische Gleichung lautet
x^5 - 2x - 1 = 0
Leider gibt es keine Lösungsformel für die Gleichung fünfter Ordnung. Aber wie Sie sehen können, ist $ x = -1 $ eine der Lösungen für diese Gleichung. Daher, wenn faktorisiert
x^5 - 2x - 1 = (x + 1)(x^4 - x^3 + x^2 - x -1)
Ich konnte es in Polynome erster und vierter Ordnung zerlegen. Die letztere Lösung des Polynoms vierter Ordnung = 0 enthält leider komplexe Zahlen und scheint keine einfachen rationalen Zahlen oder ganzen Zahlen zu sein. Vielleicht ist es unwahrscheinlich, dass das Lösen dieses allmählichen Ausdrucks dazu beiträgt, den Code zu verkürzen. Dieses Mal habe ich die Berechnung aufgegeben, weil ich die Mühe verloren habe, aber es kann interessant sein, die allmähliche Gleichung zu lösen und den allgemeinen Term zu finden.
Seit ich entgleist bin, habe ich eine Pause vom Reden gemacht, und die schrittweise Formel für die Anzahl der Elemente der Größe 1 lautet
c_{1, n} = c_{1, n-5} + 2c_{1, n-4}
Also habe ich das gehorsam umgesetzt
a=e=1;b=c=d=s=0;exec"s+=a;print s;a,b,c,d,e=b,c,d,e,a+2*b;"*100
Leider ist es das gleiche wie 63B.
Bei der Berechnung der Graduierungsformel ist mir aufgefallen, dass die Anzahl der Elemente anderer Größen auch durch dieselbe Graduierungsformel ausgedrückt werden kann.
c_{s, n} = c_{s, n-5} + 2c_{s, n-4}
Hält für alle $ s = 1, 2, 4, 8, 6 $. Nehmen Sie die Summe davon
\sum_{s} c_{s, n} = \sum_{s} c_{s, n-5} + \sum_{s} 2c_{s, n-4}
Denken Sie daran, dass die Summe die Gesamtzahl der Bye-Byemen ist
s_{n} = s_{n-5} + 2s_{n-4}
Ich konnte die Summe von bye-byeman direkt berechnen. Bei Implementierung zusammen mit der Tatsache, dass der erste Term für den allmählichen Ausdruck der Gesamtzahl von Bye-by-Man 1, 1, 1, 1, 2 ist.
a=b=c=d=1;e=2;exec"print a;a,b,c,d,e=b,c,d,e,a+2*b;"*100
Es ist endlich auf 56B geschrumpft.
Wir brauchen noch eine Wendung, also werden wir das Array wieder verwenden. Da es höchstens 100 Generationen zu berechnen gibt, habe ich außerdem aufgehört, die Schicht zu drehen und so weiter. Dies ist nicht der Fall, wenn Sie so tun, als ob Sie es wären.
a=[1]*4+[2];exec"print a[-5];a+=[a[-5]+2*a[-4]];"*100
Sie haben jetzt 53B erreicht. das ist
1, 1, 1, 1, 2, 3, 3, 3, 5, 8, ...
In einem Array, das unbegrenzt wächst, indem die Gesamtzahl der nächsten Generation gemäß der Graduierungsformel addiert wird, wird die Position -5 vom Ende als Gesamtzahl der aktuellen Generation ausgegeben.
Der 53B-Code verwendet einen negativen Wert für den Index des Arrays und verliert nur ein '-'. Sie können die Reihenfolge dieses Arrays umkehren, die '-' drei kürzen und stattdessen + = durch = und + a ersetzen, was einer Reduzierung von 2B entspricht.
a=[2]+[1]*4;exec"print a[4];a=[a[4]+2*a[3]]+a;"*100
Dies war diesmal meine Antwort.
Ich frage mich, ob ich noch ein Byte schneiden kann
Ich habe darüber nachgedacht, aber keiner von ihnen hat funktioniert. Ich freue mich auf die veröffentlichten Python-Antworten und Antworten in anderen Sprachen.
Abschließend möchten wir uns bei Ozy für die Bereitstellung eines so interessanten Themas und bei CodeIQ für die Bereitstellung des Veranstaltungsortes bedanken.