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 4 - Von Variablen und anderen Schubladen

Erstellt von Frithjof Mon, 26 Mar 2007 20:19:00 GMT

In Lektion 3 haben wir zwei Häuser untereinander (also vertikal) in die DOS-Box gemalt. Wir möchte aber eine ganze Häuserreihe nebeneinander malen (also horizontal). Bevor wir das aber mit Ruby hinbekommen, müssen wir uns über Variablen unterhalten. Variable bedeutet zu deutsch etwa die Veränderliche. In Variablen können wir Dinge speichern und sie später so oft wir wollen wiederverwenden. Am Anfang hilft es, sich eine Variable als eine Art Schublade vorzustellen. Was macht man mit einer Schublade? Man zieht sie auf, schmeißt was rein, und knallt sie wieder zu (wenn Mama in der Nähe ist, schiebt man sie natürlich sanft zu!). Irgendwann, wenn man die Dinge in der Schublade wieder braucht, sucht man die gewünschte Schublade aus – vielleicht ist vorn ein Aufkleber drauf – zieht sie auf und holt sich was passendes raus.

So ähnlich funktionieren auch Variablen in Ruby. Variablen in Ruby haben einen Namen (der Aufkleber an der Schublade) und einen Wert (das was in der Schublade drinnen ist). Stell dir vor, wir geben einer Variablen in Ruby einfach mal den Namen schublade. Wir möchten in dieser Variablen den Wert “alte Socken” speichern (d.h. in die Schublade reinschmeißen). Dann sieht das in Ruby so aus:


  schublade = "alte Socken" 

Immer, wenn wir in einer Ruby-Variablen einen Wert ablegen wollen, steht der Name der Variablen auf der linken Seite! Das ist immer so. Zusätzlich müssen wir Ruby noch ein Zeichen mitgeben, das angibt, wie wir den Wert in die Variable ablegen möchten. Daher nennt man dieses Zeichen auch Operator (zu deutsch etwa der, der das Zeug in die Schublade schmeißt). Oben haben wir das Gleichheitszeichen = verwendet. Es bedeutet hier etwas anderes als in der Mathematik. Das Gleichheitszeichen sagt: Ruby, bitte ersetze den aktuellen Wert der Variablen schublade auf der linken Seite durch den Wert rechts von mir! Rechts von diesem Gleichheitszeichen folgt dann der eigentliche Wert, den wir in der Variablen schublade speichern wollen. Der Wert, der in die Variable rein soll, muss immer auf der rechten Seite des Operators = stehen.

Nun kannst du dir bestimmt schon denken, wie es aussieht, wenn wir den Inhalt einer Variablen wieder herauslesen möchten. Genau, der Name der Variablen muss nun nicht auf der linken, sondern auf der rechten Seite stehen. So können wir den Wert der Variablen schublade wieder ausgeben:


  require 'rubykids'

  schublade = "alte Socken" 
  schreibe schublade

Hier noch ein etwas längeres Beispiel zum Umgang mit Variablen:


  # lektion_04.rb

  require 'rubykids'

  schublade1           = "Hemden" 
  anzahl_in_schublade1 = 5

  schublade2           = "Hosen" 
  anzahl_in_schublade2 = 7

  die_kleine_schublade = "Socken" 
  anzahl_in_kleinen    = 10

  RIESEN_SCHUBLADE     = "Mein Schrank" 

  rot                  = "rot" 
  text                 = " ist voll mit " 

  # Einen Satz während der Ausgabe bilden

  schreib  RIESEN_SCHUBLADE, text
  schreib           anzahl_in_schublade1, " ", schublade1
  schreib  " und ", anzahl_in_schublade2, " ", schublade2
  schreibe " und #{anzahl_in_kleinen} ", rot, "en ", die_kleine_schublade

  # Denselben Satz zunächst in einer Variablen speichern 
  # und erst danach ausgeben, diesmal noch einen Punkt anhängen.

  satz =  "#{RIESEN_SCHUBLADE}#{text}" 
  satz << "#{anzahl_in_schublade1} #{schublade1}" 
  satz << " und #{anzahl_in_schublade2} #{schublade2}" 
  satz << " und #{anzahl_in_kleinen} #{rot}en #{die_kleine_schublade}" 
  satz << "." 

  schreibe satz

Was ist neu?

  1. Der Unterschied zwischen den Befehlen schreib und schreibe ist, dass bei schreib der Cursor in derselben Zeile stehen bleibt und dort weitergeschrieben wird, während bei schreibe am Ende immer in die nächste Zeile gesprungen wird. Probier es aus!
  2. Wir können mehrere Variablen und Zeichenketten mit einem einzigen schreib oder schreibe Befehl ausgeben, wenn wir sie durch je ein Komma voneinander trennen. Vor der ersten und nach der letzten Variablen darf natürlich kein Komma stehen. Wenn du es nicht glaubst, probier es aus! Ruby wird’s dir schon zeigen!
  3. In der letzten Zeile ist etwas ganz neues. Wir geben hier den Wert der Variablen anzahl_in_kleinen innerhalb einer Zeichenkette aus! Das geht normalerweise gar nicht. Denn würden wir einfach schreiben schreibe ” und anzahl_in_kleinen “ dannn würde der Name der Variablen ausgegeben werden und nicht ihr Inhalt. Wir müssen daher den Namen der Variablen gut verpacken und zwar in geschweifte Klammern mit einem # Zeichen davor. Dieses Zeichen kennst du schon von Kommentaren, die Ruby überlesen soll. Hier hat das Zeichen zusammen mit den geschweiften Klammern aber die andere Bedeutung: _Ruby, gib den Wert der Variablen aus, deren Name in den geschweiften Klammern steht!_
  4. Wie du siehst, können wir in einer Variablen nicht nur Zeichenketten speichern, sondern auch Zahlen. Es gibt aber noch mehr Dinge, die wir in einer Variablen speichern können. In den nächsten Lektionen werden wir dazu noch einiges lernen.
  5. Im letzten Abschnitts des Programms verwenden wir einen neuen Operator! Zuerst verwenden wir den = Operator, um in der Variablen satz ein Anfangsstück des Satzes zu speichern. Danach verwenden wir aber den << Operator um die restlichen Stücke des Satzes an die Variable satz anzuhängen. Während der = Operator also den vorherigen Wert der Variablen immer löscht, behält der << Operator den Wert bei und fügt hinten den neuen Wert an. Der Inhalt der Variablen wird also immer größer. Wenn wir wieder an die Schublade denken: der = Operator zieht sie auf wirft das was drin ist weg und legt den neuen Inhalt in der Schublade ab. Der << Operator hingegen zieht die Schublade auch auf, schmeißt aber nur noch etwas dazu, lässt also alles was schon drin war auch drinnen.

- Änderungen
20.07.2007, Codelistings
22.09.2007, Unicodeproblem mit Umlauten