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 7 - Häuser, Straße und Fahrrad 2

Erstellt von Frithjof Tue, 10 Apr 2007 19:35:00 GMT

Diese Lektion schließt den ersten Satz der Lektionen (1, 2, 3, 4, 5, 6, 7) auf rubykids.de ab. Wir wollen hier unsere Häuserszene, wie bereits schon angedeutet, abrunden mit einer Straße, auf der du ein Fahrrad durch die L- bzw. R-Taste nach links bzw. rechts bewegen kannst. Wir werden dazu alles verwenden, was wir bisher über Ruby kennengelernt haben.

Zunächst das fertige Programm. Schaue es dir in Ruhe an und notiere dir vielleicht die Stellen, die du nicht verstehst. Wenn du alle Lektionen bisher durchgearbeitet hast, sollte nicht allzu viel unklar sein.

Denke bitte daran: ich gehe davon aus, dass du als Betriebssystem Windows XP verwendest. Mit einer anderen Windowsversion wird sicher auch alles funktionieren. Aber mit Linux oder Mac OS X wird es Fehler geben. Grund ist das Einlesen von der Tastatur. Das funktioniert bei jedem Betriebssystem etwas anders. Hier biete ich nur eine Lösung für Windows an.


# lektion_07.rb

require 'rubykids'

# Variable für das Fahrzeug, hier ein Fahrrad (etwas Phantasie bitte!)
fahrzeug       = "o^o" 

# Variable für die Länge der Straße
strassen_laenge = 60

# Variable für die rechte Stelle, bis zu der das Fahrzeug nur fahren darf.
# Wir wollen es nämlich nicht über den Rand herausfahren lassen.
fahrzeug_ende_rechts = strassen_laenge - fahrzeug.laenge + 1

# *** 1. Häuserreihe malen
dach         = "/^\\" 
erste_etage  = "|.|" 
erdgeschoss  = "|_|" 

anzahl_haeuser = 10
platz_zwischen_haus = "   " 
zaun                = ":::" 

schreibe_leer
# Alle Dächer in einer Zeile ausgeben
anzahl_haeuser.mal do
  schreib dach, platz_zwischen_haus
end

# wir springen erst jetzt in die zweite Zeile!
schreibe_leer 
# Alle ersten Etagen in der nächsten Zeile
anzahl_haeuser.mal do
  schreib erste_etage, platz_zwischen_haus
end

# und noch die dritte Zeile!
schreibe_leer
# Nun noch alle Erdgeschosse mit Zaun
anzahl_haeuser.mal do
  schreib erdgeschoss, zaun
end

schreibe_leer

# *** 2. Strasse von links nach rechts malen
# Oberer Rand:
strassen_laenge.mal { schreib "_" }
schreibe_leer
# Der Mittelstreifen:
strassen_laenge.mal { schreib "." }
schreibe_leer
# Und noch den unteren Rand, hier fährt dann das Fahrzeug
strassen_laenge.mal { schreib "_" }

# Variable für die aktuelle Stelle des Fahrzeuges
stelle = 0

# Variable für den Wert der Taste, die gedrückt wird
taste  = "" 

# *** 3. In einer Schleife wiederholt das Zeichen von der Tastatur
# lesen und nur die Zeile mit dem Fahrzeug neu malen. Der Rest 
# darüber bleibt wie er war.
while taste = lies_ein_zeichen
  # Wenn L-Taste gedrückt, dann das Fahrzeug nach links bewegen
  stelle = stelle - 1 if taste == "l" 

  # Wenn R-Taste gedrückt, dann das Fahrzeug nach rechts bewegen
  stelle = stelle + 1 if taste == "r" 

  # While-Schleife verlassen, wenn X-Taste gedrückt
  exit if taste.buchstaben_klein == "x" 

  # Falls das Fahrzeug nach links aus dem Fenster herausfahren will,
  # wieder auf die Anfangsstelle ganz links stellen
  if stelle < 1 then stelle = 1 end

  # Falls das Fahrzeug nach rechts weiter fahren will, als die Strasse
  # lang ist, auf die rechteste Endestelle stellen
  if stelle > fahrzeug_ende_rechts then stelle = fahrzeug_ende_rechts end

  # Zeile löschen, d.h. wieder vorne mit der Ausgabe anfangen 
  schreib "\r" 

  # Den Teil der Strasse vor dem Fahrzeug ausgeben
  (stelle-1).mal { schreib "_" }

  # Das Fahrzeug selbst ausgeben
  schreib fahrzeug

  # Den Teil der Strasse nach dem Fahrzeug ausgeben
  (fahrzeug_ende_rechts-stelle).mal { schreib "_" }
end

Speichere das Programm in der Datei lektion_07.rb und führe es wie üblich aus:


C:\entwicklung>ruby lektion_07.rb

Unmittelbar nach dem Programmstart sollte das Programm etwa so aussehen:

Drücke ein paar mal die R-Taste, so als ob du ein kleines R tippen möchtest. Das Fahrrad fährt nun mit jedem Tastendruck ein Zeichen weiter nach rechts. Du kannst bis zum rechten Ende der Straße fahren, dann kannst du drücken sooft du willst, es fährt nicht mehr weiter.

Drücke nun ein paar mal die L-Taste, so als ob du ein kleines L tippen möchtest. Das Fahrad fährt wieder zurück und stoppt, wenn es wieder am Ausgangspunkt angekommen ist. Du kannst die Tasten auch drücken und festhalten – so fährt es schneller.

Wenn du keine Lust mehr hast, drücke die X-Taste, so als ob du ein kleines X tippen möchtest.

Probiere andere Fahrzeuge aus! Nimm dazu einfach ein paar andere Zeichen, die sich über die Tastatur eingeben lassen und irgendwie wie ein Fahrzeug aussehen. Zum Beispiel könnte das hier: .[__].h. ein LKW sein, der gerade nichts geladen hat. Das Fahrzeug sollte nur nicht länger sein, als die Straße.

Wie es funktioniert

Der Clou mit dem Fahrzeug ist, dass wir es geschafft haben, die letzte Zeile immer wieder an derselben Stelle auszugeben. Bei jeder Ausgabe wird die vorherige Ausgabe überschrieben. Dadurch entsteht der Eindruck, dass sich das Fahrzeug bewegt. Der Trick ist die Zeile


  ...
  # Zeile löschen, d.h. wieder vorne mit der Ausgabe anfangen 
  schreib "\r" 
  ...

in der wir eine komische Zeichenkette ausgeben. Sie besteht aus einem Backslash und einem kleinen R. Wie du gelernt hast (ich glaube es war in Lektion 2), bedeutet der Backslash, dass das Zeichen danach eine besondere Bedeutung hat. Daher wird mit dem Befehl schreib "\r" nicht ein kleines r auf der Kommandozeile der DOS-Box ausgeben, sondern es passiert folgendes: die DOS-Box setzt den Cursor in derselben Zeile auf den Anfang zurück, ohne die bisherige Ausgabe in dieser Zeile zu löschen! Das kleine r steht nämlich für carriage return, zu Deutsch: Wagenrücklauf. Der Begriff stammt noch aus Zeiten der mechanischen Schreibmaschinen. Mama hat bestimmt noch eine auf dem Dachboden versteckt und kann sie dir irgendwann mal vorführen. Dort gibt es einen Hebel, mit dem man den Wagen (die Rolle wo das Papier eingespannt ist) nach rechts zurück schiebt, sodass man links weiterschreiben kann. Es lässt sich einstellen, ob beim Wagenrücklauf die Rolle auch gleich in die nächste Zeile gedreht wird, oder ob sie in derselben Zeile stehen bleiben soll. Für den Computer hat man einfach dieses Bild des Wagenrücklaufs übernommen. Das Zeichen dafür ist eben \r. Das Zeichen für das Drehen der Rolle in die neue Zeile ist \n, vom englischen newline (neue Zeile) abgeleitet.

Würden wird also schreib "\r\n" verwenden, würde der Wagen – ach Quatsch - der Cursor an den Anfang zurück und in die nächste Zeile springen. Das wollen wir aber nicht, daher lassen wir einfach das \n weg.

Peter und Livia

Peter: Bei mir sieht es irgendwie komisch aus. Die Straße passt gar nicht in die DOS-Box.

Livia: Dann versuche weniger Häuser (Variable anzahl_haeuser) und eine kürzere Straße (Variable strassen_laenge) zu verwenden. Du kannst aber auch deine DOS-Box vergrößern. Klicke dazu auf das Symbol in der linken oberen Ecke der DOS-Box und wähle aus dem Menü Eigenschaften, dann die Reiterkarte Layout. Im Bereich Fensterpuffergröße und Fenstergröße setzt du den Wert für die Breite beispielsweise auf den Wert 120 und klickst dann auf OK.

Peter: Das Programm ist ziemlich lang. Soll ich das etwa alles abtippen?

Livia: Wenn du Ruby wirklich erlernen möchtest – klar! Wenn du aber ein echtes Rubykid werden möchtest, schreibst du den Code der Lektion 7 zunächst sogar von Hand auf ein Schmierblatt! Es ist nämlich so: nur was uns durch das Schreiben durch die Hand geht, geht auch wirklich durch den Kopf. Du kannst den Code natürlich auch mit der Maus markieren, mit Strg-C kopieren und dann mit Strg-V in die Datei einfügen. Aber wundere dich nicht, wenn du das Programm genauso schnell wieder vergißt, sobald du deinen Computer ausschaltest.

Peter: Ich habe zu den Lektionen noch Fragen, wie kann ich die auf rubykids.de loswerden?

Livia: Hänge einfach an den Artikel der Lektion einen Kommentar an. Dazu klickst du zuerst auf die große Überschrift der Lektion und gehst dann ganz ans Ende der Seite und gibst deine Frage ein.

- Änderungen
22.09.2007, Unicodeproblem mit Umlauten