Lektion 8 - Projekt Euler Problem 1 3

Erstellt von Frithjof Fri, 20 Apr 2007 20:21:00 GMT

In den folgenden drei Lektionen wollen wir kein konkretes Thema verfolgen, sondern die Dinge, die wir gelernt haben etwas festigen. Das soll aber nicht heißen, dass wir die Zeit verstreichen lassen, ohne etwas Neues zu lernen! Im Gegenteil.

Wie können wir unsere bisher erworbenen Kenntnisse besser anwenden und überprüfen, als wenn wir an einem Wettbewerb teilnehmen? Was meinst du? Hast du Lust, dich mit anderen zu messen? Okay, los geht’s!

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:

Problem 1

Wenn wir alle natürlichen Zahlen kleiner als 10 auflisten, die durch 3 oder 5 teilbar sind, erhalten wir die Zahlenfolge 3, 5, 6 und 9. Die Summe dieser Zahlenfolge ist 23.

Finde die Summe aller Vielfache von 3 und 5 kleiner als 1000.

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:

Zahl Teilbar durch 3? Teilbar durch 5? Summe
1 nein nein 0
2 nein nein 0
3 ja nein 0 + 3 = 3
4 nein nein 3
5 nein ja 3 + 5 = 8
6 ja nein 8 + 6 = 14
7 nein nein 14
8 nein nein 14
9 ja nein 14 + 9 = 23
10 nein ja 23 + 10 = 33
11 nein nein 33
12 ja nein 33 + 12 = 45
13 nein nein 45
14 nein nein 45
15 ja ja 45 + 15 = 60
... ...

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}." 

In der Zeile

  ...
  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:

falschorfalsch= falsch d.h. 0 + 0 = 0
falschorwahr= wahr d.h. 0 + 1 = 1
wahrorfalsch= wahr d.h. 1 + 0 = 1
wahrorwahr= wahr d.h. 1 + 1 = 1
falschandfalsch= falsch d.h. 0 * 0 = 0
falschandwahr= falsch d.h. 0 * 1 = 0
wahrandfalsch= falsch d.h. 1 * 0 = 0
wahrandwahr= wahr d.h. 1 * 1 = 1

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:

Was sich der Entwickler an Zeit spart, muss der Anwender an Zeit mitbringen.
Peter: Die Zeile

...
summe = zahl = 0
...
verstehe ich nicht. Was soll das mit den zwei Gleichheitszeichen nacheinander bedeuten?

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

Lektion 6 - Häuser und dann?

Erstellt von Frithjof Tue, 03 Apr 2007 20:48:00 GMT

In Lektion 5 haben wir es endlich geschafft, eine Reihe mit Häusern zu malen. Wir könnten nun in diese langweilige Szene noch etwas Leben bringen. Entlang der Häuser soll eine Straße verlaufen. Auf der Straße soll ein Fahrrad fahren können. Wenn du auf deiner Tastatur auf die R-Taste drückst, soll das Fahrrad nach rechts fahren, drückst du auf die L-Taste, fährt es nach links. Ganz schön viel zu tun! Das schaffen wir kaum in einer Lektion. Außerdem müssen wir noch etwas mehr von Ruby lernen, bevor wir das alles hinbekommen.

Du lernst in dieser Lektion daher einiges an Grundlagenwissen, das wir für die Vervollkommnung unserer Häuserszene benötigen.

  1. Wie bringst du Ruby bei, eine Entscheidung für zwei Möglichkeiten zu treffen? Stelle dir folgende Situation vor: Das Fahrrad kann auf einer Zeile immer nur ein Zeichen (d.h. eine Spalte) nach links oder nach rechts fahren. Es steht zum Beispiel gerade in der Spalte 5 (d.h auf dem 5-ten Zeichen vom linken Rand der DOS-Box). Nun tippst du auf die R-Taste. Das Fahrrad soll sich nach rechts, also in die Spalte 6 bewegen. Würdest du auf die L-Taste drücken, müsste es sich zurück in die Spalte 4 bewegen. Wir brauchen also eine Möglichkeit, im Rubyprogramm zur aktuellen Fahrradposition entweder 1 zu addieren, oder 1 zu subtrahieren – je nachdem welche Taste du gedrückt hast.
  2. Wie bringst du Ruby dazu, einen Codeblock mehrmals zu wiederholen, ohne dass du von vornherein weißt, wie oft genau wiederholt werden soll? Stelle dir wieder vor, du drückst fleißig auf die R- und auf die L-Taste. Das Fahrrad saust hin und her. Ruby darf in der ganzen Zeit das Programm nicht beenden, sondern muss ständig auf deine Eingaben warten – selbst wenn du zwischendurch mal zum Kühlschrank gehst! Erst dann, wenn du eine bestimmte Taste drückst, sagen wir die X-Taste, dann darf Ruby das Programm beenden, weil die X-Taste bedeutet: du hast keine Lust mehr.

Fangen wir also damit an.

Entscheidungen mit Ruby

Entscheidungen in Ruby sind recht einfach. Du musst nur 4 englische Wörter lernen:

if bedeutet wenn
then bedeutet dann
end bedeutet ende, das kennst du schon von den Codeblöcken bei Schleifen.
else bedeutet sonst

Diese englischen Wörter haben im Programmcode von Ruby eine besondere Bedeutung. Sie heißen auch Schlüsselwörter, weil man sie nicht für andere Sachen in einem Programm verwenden darf. Du dürftest bspw. keine Variable mit dem Namen if oder else anlegen. Ruby würde das mit einer Fehlermeldung vergelten.

Wenn du die Wörter oben gelernt hast, dann fällt es dir bestimmt nicht schwer, folgendes Programm zu verstehen:


# lektion_06.rb

require 'rubykids'

richtung = "R" 

if richtung == "R" then schreibe "Ich fahre nach rechts" end
if richtung == "L":     schreibe "Ich fahre nach links" end

Probiere mal aus, den Wert der Variable richtung auf L oder irgendeinen anderen Buchstaben zu ändern. Was passiert?

Schau dir nun folgendes Programm an und spiele genauso mit der Variablen richtung herum. Es passiert nicht dasselbe. Weißt du warum?


# lektion_06.rb

require 'rubykids'

richtung = "R" 

if richtung == "R" 
  schreibe "Ich fahre nach rechts" 
else
  schreibe "Ich fahre nach links" 
end

Erklärung – Entscheidungen mit Ruby

Allgemein kannst du eine Entscheidung mit Ruby so schreiben:


if (aussage)
  # tue etwas, wenn die aussage wahr ist
else
  # tue etwas, wenn die aussage falsch ist
end

# oder

if (aussage) then ... end

# oder statt then kann man auch den Doppelpunkt nehmen

if (aussage) : ... end

Wenn die Aussage nach dem if wahr ist, dann führt Ruby den Codeblock aus, der unmittelbar danach kommt. Der auszuführende Codeblock reicht bis zum else, wenn es kein else gibt, dann reicht der Codeblock bis zum end.

Schreibst du den if-Ausdruck in eine Zeile, musst du zum Abtrennen noch das then (oder den Doppelpunkt) zwischen die zu prüfende Aussage und den Codeblock einschieben.

Man kann das if auch hinten anstellen:


# lektion_06.rb

require 'rubykids'

richtung = "R" 

schreibe "Ich fahre nach rechts" if richtung == "R" 
schreibe "Ich fahre nach links"  if richtung == "L" 

Mehr als zwei Entscheidungen mit Ruby

Mit if – then – else kannst du zwei Entscheidungen treffen. Ruby kann aber auch zwischen mehr Alternativen entscheiden. Verwende einfach zusätzlich beliebige elsif Anweisungen:


# lektion_06.rb

require 'rubykids'

richtung = "O" 

if richtung == "R" 
  schreibe "Ich fahre nach rechts" 
elsif richtung == "L" 
  schreibe "Ich fahre nach links" 
elsif richtung == "O" 
  schreibe "Ich fahre nach oben" 
elsif richtung == "U" 
  schreibe "Ich fahre nach unten" 
end

elsif ist wieder ein Schlüsselwort und darf für nichts anderes verwendet werden.

Es gibt noch einiges mehr zum Thema Entscheidungen zu sagen. Wir werden darauf zurückkommen, sobald wir es brauchen. Was du bisher hier darüber gelernt hast, reicht zunächst völlig aus. Kommen wir lieber noch zum nächsten Thema

Beliebig lange Wiederholungen mit Ruby

Schauen wir uns folgende Wiederholungsschleife in Ruby an:


# lektion_06.rb

require 'rubykids'

while zeichenkette = lies_eine_zeichenkette
  schreibe "Du hast die Zeichenkette '", zeichenkette.ohne_enter, "' eingegeben!" 
end

Starte das Programm einmal mit dem Befehl


C:\entwicklung>ruby lektion_06.rb

und gib irgendetwas über die Tastatur ein und drücke anschließend die Entertaste. Was passiert? Ruby liest, was du eingegeben hast und gibt es wie ein Echo nochmal aus. Du gibst wieder etwas ein und Ruby gibt es wieder aus und immer so weiter. Wann hält das Programm denn endlich mal an? Nie! Solange dein PC Strom hat, wird Ruby das Programm für immer ausführen. Wir haben soeben eine sogenannte Endlosschleife programmiert. Die einzige Möglichkeit das Programm zu beenden ist, Ruby selbst zu beenden. Das kannst du über die Tastatur mit der Tastenkombination Strg-C erreichen. Drücke die Strg-Taste (ganz unten links auf deiner Tastatur), halte sie fest und drücke noch auf die C-Taste. Dann wird Ruby sich eingeschnappt mit einer Fehlermeldung verabschieden.

Die Endlosschleife ist eine sogenannte while-Schleife. While bedeutet soviel wie solange bis. Allgemein kannst du eine while-Schleife so verwenden:


while (aussage)
  # tue etwas, wenn die aussage wahr ist
end

Solange der Wert von aussage wahr ist, führt Ruby den Codeblock bis zum zugehörigen end aus und kehrt wieder nach oben zur erneuten Prüfung der aussage zurück. Sobald die aussage falsch wird, springt Ruby zum nächsten Code nach dem end. Falls dort nichts mehr kommt, ist das Programm zu Ende.

In unserem obigen Beispiel bestand die aussage darin, etwas von der Tastatur einzulesen und in der Variablen zeichenkette abzuspeichern. Ruby wartet auf deine Tastatureingabe und macht erst weiter, wenn du mit Enter deine Eingabe abgeschlossen hast. Somit ist eine Eingabe immer möglich, und die aussage (zeichenkette = lies_eine_zeichenkette) ist immer wahr.

Wollen wir das Programm auf normalem Wege beenden, müssen wir eine Bedingung innerhalb des Codeblocks der While-Schleife einbauen. Wenn wir keine Lust mehr haben, irgendetwas an der Tastatur einzugeben, teilen wir das Ruby mit, indem wir das Wort ende eingeben. Unser Programm sieht dann so aus:


# lektion_06.rb

require 'rubykids'

while zeichenkette = lies_eine_zeichenkette
  if zeichenkette.ohne_enter == "ende" 
    schreibe "Bis bald! " 
    exit
  end
  schreibe "Du hast die Zeichenkette '", zeichenkette.ohne_enter, "' eingegeben!" 
end

Mit der Anweisung exit springt Ruby aus dem Codeblock der while-Schleife, auch wenn die aussage wahr gewesen ist. Alles was noch in der Schleife zu tun wäre, wird nicht mehr ausgeführt. Das Programm arbeitet erst nach dem end wieder weiter. while und exit sind ebenfalls Schlüsselwörter.

Peter und Livia

Peter: Ist ja alles ziemlich pipi einfach. Was ich nur nicht verstehe: warum muss ich in dem Ausdruck manchmal ein doppeltes Gleichheitszeichen schreiben? Kann ich statt richtung == “R” nicht auch richtung = “R” verwenden?

Livia: Das kommt darauf an, was gemeint ist. In diesem Fall möchtest du doch den Wert der Variable richtung mit einer Zeichenkette “R” vergleichen. Zum Prüfen auf Gleichheit verwendest du in Ruby das doppelte Gleichheitszeichen. Würdest du richtung = “R” schreiben, so würdest du ja der Variablen richtung den Wert “R” zuweisen und der vorherige Wert der Variablen würde verloren gehen. Da die Zuweisung von “R” zur Variablen richtung immer funktioniert, wäre die aussage auch immer wahr, auch wenn richtung vorher bspw. den Wert “L” hatte. Eine prima Fehlerquelle.

Etwas anders sieht es mit der aussage bei der while-Schleife aus. Dort haben wir bewusst das einfache Gleichheitszeichen verwendet: zeichenkette = lies_eine_zeichenkette. Hier möchten wir ja gerade der Variablen zeichenkette den neuen Wert zuweisen, den uns der Befehl lies_eine_zeichenkette von der Tastatur liefert. Da diese Zuweisung immer funktioniert, ist auch die aussage immer wahr, daher wird die Schleife ja auch endlos ausgeführt.

- Änderungen
22.09.2007, Unicodeproblem mit Umlauten