|
|
9. Programmieren9.1 Unsere erste Programmieraufgabe |
Obwohl unser Programm jetzt vernünftig funktioniert, kann man die Rechnung noch etwas intelligenter gestalten! Es gibt nämlich meistens mehrere Algorithmen, mit denen man ein Problem lösen kann, und die haben unterschiedliche Vor- und Nachteile. Ein Qualitätskriterium ist dabei immer, wie schnell sich ein Problem mit einem bestimmten Algorithmus lösen lässt. Versuchen wir also unseren Algorithmus etwas schneller zu machen! Wir könnten uns zum Beispiel überlegen, ob wir wirklich jede Zahl ausprobieren müssen, ob sie ein Teiler des Dividenden ist:
Beispielsweise sind die Teiler von 36: 2, 3, 4, 6, 9, 12, 18
| 2 x 18 = 36 | 3 x 12 = 36 | 4 x 9 = 36 | 6 x 6 = 36 |
Wenn wir den kleinsten Teiler einer Zahl gefunden haben (hier: 2), dann haben wir gleichzeitig auch schon den größten gefunden! Das ist nämlich das Ergebnis der Division durch diesen kleinsten Teiler, im Beispiel 18. Alle Zahlen, die größer sind als dieser größte Teiler, brauchen wir also gar nicht mehr ausprobieren, ob sie auch noch Teiler sind! Haben wir den zweitkleinsten Teiler gefunden, haben wir gleichzeitig auch den zweitgrößten. Es ist wieder das Ergebnis der Division durch den gefundenen Teiler, in unserem Beispiel also 12. Zwischen dem größten und dem zweitgrößten Teiler kann es ebenfalls keinen weiteren Teiler geben; also brauchen wir auch diese Zahlen nicht auszuprobieren.
Um unseren Algorithmus zu verbessern, brauchen wir uns also nur den jeweiligen "Partner" eines gefundenen Teilers zu merken; weiter als bis zum jeweils letzten gefundenen Partner brauchen wir keine weiteren Teiler zu suchen!
Genau genommen können wir noch ein wenig sparen:
Die Quadratwurzel einer Zahl ist diejenige Zahl, die mit sich selbst mal genommen die ursprüngliche Zahl ergibt.
Beispiel: Die Quadratwurzel von 36 ist 6, weil 6 x 6 = 36. Man schreibt das mit einem Zeichen so:
√36 = 6
Genau bis zu dieser Zahl müssen wir Teiler suchen, weil das die größte Paarung von Teilern ist, die auftreten kann.
Eine Quadratwurzel auszurechnen, ist nicht so einfach! Bei 36 ging das ja noch, aber versuche es einmal für 10! Aber die meisten Computer können das heute.
| 1. | Dividend eingeben und speichern |
| 1a. | Wenn der Dividend kleiner ist als 3 oder wenn es sich nicht um eine ganze Zahl handelt, Fehlermeldung ausgeben und zurück zu Schritt 1. |
| 2. | Divisor auf 2 setzen |
| 3. | Rest der Division "Dividend durch Divisor" berechnen |
| 4. | Falls der Rest Null ist, Divisor als Teiler ausgeben Partner neu berechnen als Dividend : Divisor Partner als Teiler ausgeben |
| 5. | Divisor um 1 vergrößern |
| 6. | Prüfen, ob Divisor größer oder gleich der Quadratwurzel des Dividenden ist, falls ja, Programm beenden falls nein, zu Schritt 3 zurückgehen. |
Der Vorteil dieses Algorithmus ist, dass er erheblich schneller ist. Der Nachteil ist, dass die Teiler nicht mehr in aufsteigender Reihenfolge ausgegeben werden. Außerdem wird bei Quadratzahlen die Wurzel zweimal als Teiler ausgegeben. Dieses Manko lässt sich aber leicht beheben.
Führe mit diesem neuen Algorithmus den gleichen Test durch, wie wir es für den alten getan haben, um seine Funktionsweise zu verstehen!
| 9.1.1 Testen des Algorithmus | Inhaltsverzeichnis Index |
9.2 Programmelemente |