Auf der Website Projekt Euler findest du eine Sammlung von Problemen unterschiedlicher Schwierigkeitsgrade. Wir suchen uns dort einfach mal das erste Problem aus und versuchen es mit Ruby zu lösen. Auch eine gute Gelegenheit, sich etwas über den Mathematiker Leonhard Euler zu belesen.

Das erste Problem von Projekt Euler lautet:

Wenn du möchtest kannst du zunächst auf einem Schmierblatt selbst versuchen, wie sich das Problem mit Ruby lösen lässt. Ich schau mal kurz weg … hast du’s? Wir können es auch zusammen machen.

Beim Versuch, das Problem mit Blatt und Bleistift lösen zu wollen, merkst du sicher schnell, dass das ziemlich langweilig ist (immer, wenn man dieses Gefühl der Langeweile in der Mathematik bekommt, bietet sich der Einsatz eines Computers an, denn der kennt keine Langeweile).

Wir würden jede Zahl von 1 bis 999 (die 1000 sollen wir ja nicht mit berücksichtigen) zunächst testen, ob sie durch 3 oder durch 5 teilbar ist. Wenn ja, dann nehmen wir diese Zahl und addieren sie zu unserer Summe hinzu. Das würde dann etwa so aussehen:

Wir zerlegen das Problem in folgende Teilprobleme:

1. Testen auf Teilbarkeit durch 3
2. Testen auf Teilbarkeit durch 5
3. Aufaddieren von Zahlen
4. Durchlaufen aller Zahlen von 1 bis 999 in einer Schleife

Testen auf Teilbarkeit durch 3

Wie testen wir mit Ruby, ob eine Zahl durch 3 teilbar ist? Wann ist eine Zahl durch 3 teilbar?

Eine Zahl zahl ist durch 3 teilbar, wenn bei der ganzzahligen Division von zahl durch 3 der Rest 0 entsteht. Die 2 geht zum Beispiel 0 mal durch 3 zu teilen und es entsteht ein Rest von 2. Bei der 7 hingegen kommt bei der Division durch 3 das Ergebnis 2 Rest 1 heraus. Bei der 3 oder der 6 oder der 9 aber geht die Division mit dem Rest 0 auf.

Mit Ruby können wir leicht testen, ob eine Zahl bei Division durch 3 den Rest 0 hinterlässt, indem wir an die Zahl die Nachricht rest_bei_div mit der Zusatzinformation 3 schicken. Probieren wir es mal für die 7 und die 6:

# lektion_08.rb

require 'rubykids'

zahl = 7

if zahl.rest_bei_div(3) == 0
  schreibe "#{zahl} ist durch 3 teilbar!" 
else
  schreibe "#{zahl} ist nicht durch 3 teilbar!" 
end

zahl = 6

if zahl.rest_bei_div(3) == 0
  schreibe "#{zahl} ist durch 3 teilbar!" 
else
  schreibe "#{zahl} ist nicht durch 3 teilbar!" 
end

Testen auf Teilbarkeit durch 5

Das Testen der Teilbarkeit durch 5 geht genauso. Wir brauchen nur die Zusatzinformation, die wir mit der Nachricht rest_bei_div an die zahl schicken, abzuändern.

...
if zahl.rest_bei_div(5) == 0
...

Aufaddieren von Zahlen

Angenommen wir haben die Variable summe, so können wir beispielsweise die 3 hinzuaddieren, indem wir einfach summe + 3 schreiben und diesen neuen Wert wieder der Variablen summe mit dem Gleichheitszeichen zuweisen.

# lektion_08.rb

require 'rubykids'

summe = 0

summe = summe + 3
summe = summe + 5
summe = summe + 6
summe = summe + 9

# ... und immer so weiter

schreibe "Summe ist: #{summe}" 

Ruby legt viel Wert auf die Möglichkeit sehr kompakten Code zu schreiben. Beim Summieren sparen wir uns daher das Wiederholen der Variablen auf der rechten Seite vom Gleichheitszeichen. Das Plus-Zeichen würde dann aber in der Luft hängen, daher schreibt man es vor das Gleichheitszeichen. Das sieht dann so aus:

# lektion_08.rb

require 'rubykids'

summe = 0

summe += 3
summe += 5
summe += 6
summe += 9

# ... und immer so weiter

schreibe "Summe ist: #{summe}" 

Im Matheunterricht darfst du soetwas aber natürlich nicht schreiben! ;-)

Durchlaufen aller Zahlen von 1 bis 1000 in einer Schleife

Schleifen haben wir auch schon kennen gelernt. Folgender Code sollte dir keine Schwierigkeiten bereiten:

# lektion_08.rb

require 'rubykids'

zahl = 0

1000.mal do
  zahl = zahl + 1
  schreib "\r zahl=#{zahl}" 
  schlafe_kurz
end

Wie du siehst, verwenden wir hier wieder den Trick mit dem Wagenrücklauf (carriage return), den wir bereits in Lektion 7 kennen gelernt haben, um immer auf derselben Zeile die Zahlen auszugeben. Außerdem ist hier der Befehl schlafe_kurz neu. Der zwingt Ruby dazu, kurz zu warten. Würden wir diesen Befehl weglassen (probiere es!), dann würden wir nicht sehen, wie Ruby von 1 bis 1000 hochzählt, weil Ruby das so unheimlich schnell tut, dass wir sofort die 1000 sehen würden. Das schlafe_kurz lassen wir nachher, wenn wir unser fertiges Programm zur Lösung des Problems zusammenbauen natürlich weg.

Lösung für Problem 1 projecteuler.net mit Ruby

Okay, nun haben wir alles, was wir für die Lösung des Problems brauchen. Hier ist sie:

# lektion_08.rb

require 'rubykids'

maximum = 1000
summe = zahl = 0

maximum.mal do
  zahl = zahl + 1
  summe += zahl if (zahl.rest_bei_div(3) == 0 or zahl.rest_bei_div(5) == 0 and zahl < maximum)
end
schreibe "Die Summe aller Vielfache von 3 und 5 kleiner #{maximum} ist #{summe}." 

  ...
  summe += zahl if (zahl.rest_bei_div(3) == 0 or zahl.rest_bei_div(5) == 0 and zahl < maximum)
  ...

passiert ziemlich viel auf einmal. In einer einzigen Zeile testen wir hier, ob die aktuelle Zahl, die wir in der Schleife gerade bearbeiten durch 3 oder durch 5 teilbar ist und ob sie noch kleiner als 1000 ist. Gleichzeitig addieren wir die zahl auch zur Summe hinzu, wenn die Bedingungen erfüllt sind.

Wir reihen hier die Tests auf Teilbarkeit durch 3 und 5 aneinander. Da nur eine von beiden Bedingungen erfüllt sein muss, verbinden wir beide Bedingungen mit dem Operator or, das ist englisch und bedeutet zu deutsch oder. Egal, ob die zahl nun durch 3 oder 5 teilbar ist, sie muss auf jeden Fall kleiner als 1000 sein. Daher verbinden wir den Test darauf nicht mit or, sondern mit and, was wieder englisch ist und zu deutsch und bedeutet.

Boolesche Algebra

Diese Bedingungen, die wahr oder falsch sein können, nennt man auch Boolesche Ausdrücke. Und das Verbinden dieser Ausdrücke mit Operatoren or und and nennt man Boolesche Algebra.

Wenn wir dafür, dass eine Bedingung wahr ist eine 1 schreiben würden und dafür, dass eine Bedingung falsch ist eine 0, dann kannst du dir das or wie ein Plus + und das and wie ein Mal * in der normalen Mathematik vorstellen. Dann gilt in der boolschen Algebra folgendes:

Du siehst, eine aus zwei mit or verknüpften Bedingungen bestehende Bedingung ist immer dann wahr, wenn eine von beiden Bedingungen (egal welche) wahr ist. Aber, eine aus zwei mit and verknüpften Bedingungen bestehende Bedingung ist nur dann wahr, wenn beide Bedingungen zugleich wahr sind.

Mehr zu Boolescher Algebra findest du bei Wikipedia.

Peter und Livia

Peter: Wieso durchlaufen wir denn alle Zahlen von 1 bis 1000? Wir könnten doch zumindest die 1 und 2 schon mal auslassen und gleich bei der 3 starten, oder?

Livia: Ja das stimmt.

Peter: Ich habe die Variable maximum statt auf 1000 auf 1000000 (eine Million) gesetzt und das Programm dauert ganz schön lange. Warum?

Livia: Je größer die maximale Zahl, um so mehr Vergleiche müssen doch gemacht werden. Und das dauert Zeit. Wir konnten ja das Problem nur mit den Mitteln lösen, die wir bisher von Ruby kennen gelernt haben. Das Programm lässt sich aber auf jeden Fall noch verbessern, so dass es mindestens doppelt so schnell läuft. Dazu musst du aber noch erst etwas mehr von Ruby lernen. Ich kann’s schon (sie lächelt verschmitzt)! Oder du versuchst, mit mehr Mathematik die Laufzeit des Programms zu verringern. Du siehst: damit dein Programm weniger Zeit für die Ausführung benötigt, musst du mehr Zeit in seine Entwicklung investieren. Das ist so ähnlich wie bei der Goldenen Regel der Mechanik Was man an Kraft spart, muss man an Weg zulegen, nur dass man hier sagen müsste:

...
summe = zahl = 0
...

Livia: Du must das von rechts nach links lesen: Die Null wird der Variablen zahl zugewiesen (du erinnerst dich an die Schublade). Das Ergebnis dieser Zuweisung ist nun der Inhalt der Schublade, eh Variable zahl, der wiederum der Variablen summe zugewiesen wird. Nach dieser Doppelzuweisung haben beide Variablen (zahl und summe) denselben Wert, nämlich 0.

- Änderungen
17.07.2007, Im Abschnitt Boolesche Algebra die Übersicht beim and korrigiert.
22.09.2007, Unicodeproblem mit Umlauten