Dieses Mal lasse ich auch noch das Beispiel anzeigen.
Dies ist definitiv kein Level, den ich mal eben schnell vor dem Frühstück machen kann, wie ich es eigentlich geplant hatte.
Ich bin mir im Moment nicht sicher, wie ich diese Aufgabe angehen soll. Zum einen muss ich Primzahlen berechnen, zum anderen muss ich mehrfach Dividieren.
Achtung Spoiler:
Erstmal danke. Ich denke, die Spoilerfunktion können wir uns nun an dieser Stelle sparen. Primzahlen zuerst setzen kam mir auch schon durch den Sinn, das wäre in weniger Schritten umzusetzen, würde aber mehr Befehle brauchen. Allerdings brauche ich mir auch noch keine Gedanken um dei Optimierung machen, wenn ich das Programm noch nicht einmal umsetzen kann.
Den größten gemeinsamen Teiler hatte ich früher in der Grundschule.Hier wird es ja komplexer und bei deinem Link wird bereits eine Verteilung über die Primfaktorzerlegung behandelt. Das scheint schon mal die Lösung zu sein, doch wie ich das umsetze ist mir im Moment schleierhaft.
Da dies vermutlich die härteste Kopfnuss im Spiel ist, möchte ich mir doch erstmal das nächste Level anschauen und später zum jetzigen zurückkommen. Einige Optimierungsziele in früheren Level fehlen auch noch.
Bei der Umsetzung wirst du meiner Meinung nach witzigerweise durch den „beschränkten Befehlssatz“ des Spiels zum klassischen antiken Algorithmus von Euklid geführt, der ohne Divisionen auskommt
Doch wie hilft uns das nun bei der Aufgabe weiter?
Beispielsweise so:
Eingabe in m und du berechnest nacheindander t(1)=ggT(m, m-1), t(2)=ggT(m, m-2),… bis du auf einen Wert
t(i)>1 triffst. Dann wissen wir, dass m und (m-i) einen gemeinsamen Teiler besitzen und alle Zahlen größer als m-i nicht.
Wenn du nun m durch t(i) teilst, ein Divisions-Programm hast du ja schon mal geschrieben, kommt ein zweiter Faktor raus. Also m = t(i) * r.
Das r ist nun in jedem Fall eine Primzahl, denn sonst wäre bei den obigen Schritten schon früher ein ggT > 1 herausgekommen!
Es müsste außerdem sogar die kleinste Primzahl sein, die in m vorkommt
Du kannst r also auf die Ausgabe schreiben und mit t(i) von vorne beginnen.
Also, so kompliziert hab ich es nicht gemacht, aber ich hab auch keine Optimierungsziele erreicht.
Und meine Lösung ignoriert die Tatsache, dass nur Primzahlen ausgegeben werden sollen. Das erledigt sich von ganz alleine, wenn man vom kleinsten zum größten Faktor prüft. Wenn vorher schon alle Zweier-Faktoren rausgezogen wurden, kann man anschließend schlecht auf eine 4 kommen.
Stimmt, das macht Sinn. Klingt auch gleich viel leichter anzugehen.
Nach meiner kurzen Mittagspause soll es nun wieder weitergehen.
Zuerst definiere ich die ersten zehn Primzahlen durch stupides Addieren mit 1 bis zur gewünschten Zahl. In der Inbox habe ich bisher keine Zahl größer 30 gesehen, also sollte dies ausreichen. Die gewünschten Primfaktoren speichere ich zwischen (abgekürzt mit F1 is F4). So rechnet das Programm mit maximal vier Faktoren. Auch das sollte ausreichen. Jedoch würde es mich nicht wundern, wenn mir das Spiel dann doch beispielsweise eine 32 (2^5) vorsetzt.
Okay, dann werde ich das Programm doch in Abhängigkeit der Zahlen aus der Inbox rechnen lassen. Entweder berechne ich Primzahlen und speichere die in den Kacheln der oberen drei Reihen oder ich lasse diese jedes Mal neu berechnen und spare somit Kacheln. Die Faktoren würde ich dann auch nicht erstmal komplett speichern, sondern immer nur die letzte und gleich in die Outbox geben.
Morgen werde ich dies dann in Angriff nehmen.
Die Inbox speichere ich in Dings und im PF (Primfaktor) setze ich die erste Primzahl auf 2.
Das PF wird von der Inbox subtrahiert und ins Zwischending gespeichert. Im Zähler soll mitgezählt werden, wie oft PF in die Zahl aus der Inbox passt.
Und schon geht das großen Jumpen los. Wenn das Zwischending Null wird ist PF eine der gesuchten Primfaktoren und wird entsprechend in die Outbox gegeben. Dann wird erneut PF als Primfaktor geprüft, da diese mehrfach vorkommen können (vor allem bei geraden Zahlen). Sollte das Zwischending jedoch negativ werden, ist PF definitiv keiner der Primfaktoren. Nun wird PF um 1 erhöht und die Rechnung beginnt von vorn.
Jedoch hatte ich diverse Denkfehler. Ein paar Jumps waren falsch gesetzt und die Rechnung dahingehend geändert, das der Wert der Inbox auch gleich mit in das Zwischending gespeichert. Dann haben wir auch eine Endlosschleife weniger.
Jedoch gibt es nun einen Fehler in der Ausgabe.
Tja, dann fange ich wohl lieber nochmal von vorn an.
Ich fange also nochmal komplett von vorn an. In der Kachel In speichere ich die Inbox. Gleich darunter gibt es die Kachel Prim, wo der aktuelle Primfaktor gespeichert wird. Den Anfang macht eine Zwei, also setzen wir die Kachel auf diesen Wert.
Nun subtrahieren wir den Wert aus Prim von dem Wert aus In und speichern das Ergebnis in die Kachel Test. Anschließend wird die Rechnung wiederholt (mit dem Wert aus Test anstatt In).
Sollte durch Subtraktion ein negativer Wert erreicht werden, lässt sich mit dem aktuellen Primfaktor nicht der Wert aus der Inbox bilden. Also wird der Primfaktor erhöht und die Berechnung mit dem neuen Prim wiederholt.
Wie oft eine Subtraktion möglich ist, wird in der Kachel Rest gespeichert. Diese wird zu Beginn der Überprüfung auf Null gesetzt und mit jedem Durchlauf der Subtrakion ums Eins erhöht.
Jetzt kommen wir endlich aus der Endlosschleife heraus und prüfen nach jedem Durchlauf, ob das Ergebnis der Subtraktion Null beträgt. Wenn dies eintrifft, wird In mit Rest überschrieben sowie Prim ausgegeben.
Nun noch eine letzte Überprüfung. Wenn das Ergebnis einer Subtraktion zu einem gültigen Primfaktor führt, der Wert in Rest jedoch zu dieser Zeit Null beträgt, haben wir die letzte Primzahl gefunden. Diese wird ausgegeben und danach geht es mit der nächsten Inbox weiter.
Gespannt verfolge ich die Arbeit des fleißigen Angestellten. Unsicher, ob nicht doch noch ein Denkfehler besteht...
... doch das Programm läuft erfolgreich durch. Ich habe das schwerste Level im Spiel geknackt und dabei das Ziel der Größenoptimierung erreicht!
Große Freude!
Geändert von Torin (03. Juli 2017 um 19:19 Uhr)
Der letzte Level vor dem Abspann.
Berechtigungen
Zitieren
