3 Erste Miniprogramme

3.1 Was sollte man zum Programmieren können?

Denken in Algorithmen:
Welche Schritte sind zur Lösung des Problems nötig? Welche Daten müssen gespeichert, welche Datenstrukturen angelegt werden? Welche Fälle können auftreten und müssen erkannt und behandelt werden?
Umsetzung des Algorithmus in ein Programm:
Welche Datenstrukturen, Konstrukte, Funktionen… stellt die Programmiersprache bereit?
Formale Syntax:
Menschen verstehen ‘broken English’; Computer verstehen kein ‘broken C++’ oder ‘broken Julia’. Die Syntax muss beherrscht werden.
„Ökosystem“ der Sprache:
Wie führe ich meinen Code aus? Wie funktionieren die Entwicklungsumgebungen? Welche Optionen versteht der Compiler? Wie installiere ich Zusatzbibliotheken? Wie lese ich Fehlermeldungen? Wo kann ich mich informieren?
die Kunst des Debugging:
Programmieranfänger sind oft glücklich, wenn sie alle Syntaxfehler eliminiert haben und das Programm endlich ‘durchläuft’. Bei komplexeren Programmen fängt die Arbeit jetzt erst an, denn nun muss getestet und die Fehler im Algorithmus gefunden und behoben werden.
Gefühl für die Effizienz und Komplexität von Algorithmen
Besonderheiten der Computerarithmetik, insbesondere der Gleitkommazahlen

Das erschließt sich nicht alles auf einmal. Haben Sie Geduld mit sich und ‘spielen’ Sie mit der Sprache.

Das Folgende soll eine kleine Anregung dazu sein.

3.2 Project Euler

Eine hübsche Quelle für Programmieraufgaben mit mathematischem Charakter und sehr unterschiedlichen Schwierigkeitsgraden ist Project Euler. Die Aufgaben sind so gestaltet, dass keinerlei Eingaben notwendig und das gesuchte Ergebnis eine einzige Zahl ist. So kann man sich voll auf das Programmieren des Algorithmus konzentrieren.

3.2.1 Beispiel 1

Project Euler Problem No 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Algorithmus:
- Teste alle natürlichen Zahlen <1000 auf Teilbarkeit durch 3 oder durch 5 und
- summiere die teilbaren Zahlen auf.
Umsetzung:

Wie liefert Julia den Rest der Ganzzahldivision? Solche Funktionen heißen typischerweise rem() (für remainder) oder mod(). Nachlesen in der Doku oder ausprobieren von ?rem und ?mod in der Julia-REPL zeigt, dass es beides gibt. Der Unterschied liegt in der Behandlung negativer ganzer Zahlen. Für natürliche Zahlen n,m liefern mod(n,m) und rem(n,m) dasselbe und letzteres hat auch noch die Infix-Form n % m.

Wie testet man eine Reihe von Werten durch und summiert auf? Da gibt es ein Standardmuster: for-Schleife und Akkumulatorvariable:

Eine Lösungsvariante:

s = 0                               # Akkumulatorvariable initialisieren
for i in 1:999                      # Schleife   
    if i % 3 == 0 || i % 5 == 0     # Test
        s += i                      # Zu Akkumulator addieren 
    end                             # Ende Test
end                                 # Ende Schleife
println(" Die Antwort ist: $s")                          # Ausgabe des Ergebnisses

 Die Antwort ist: 233168

Natürlich geht das auch etwas kürzer:

Noch eine Lösungsvariante:

sum([i for i in 1:999 if i%3==0||i%5==0])

3.2.2 Beispiel 2

Project Euler Problem No 92

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Programme kann man top-down und bottom-up entwickeln. Top-down würde hier wohl bedeuten: „Wir fangen mit einer Schleife for i = 1:9999999 an.“ Der andere Weg führt über einzeln testbare Komponenten und ist oft zielführender. (Und ab einer gewissen Projektgröße nähert man sich sowieso von ‘top’ und ‘bottom’ gleichzeitig dem Ziel.)

Funktion Nr. 1

Es soll untersucht werden, wie sich die Zahlen unter dem wiederholten Berechnen der ‘Quadratquersumme’ (Summe der Quadrate der Ziffern) verhalten. Also sollte man eine Funktion schreiben und testen, die diese ‘Quadratquersumme’ berechnet.

q2sum(n) berechnet die Summe der Quadrate der Ziffern von n im Dezimalsystem:

function q2sum(n)
    s = 0                         # Akkumulator für die Summe
    while n > 9                   # solange noch mehrstellig...
       q, r = divrem(n, 10)       # berechne Ganzzahlquotient und Rest bei Division durch 10
       s += r^2                   # addiere quadrierte Ziffer zum Akkumulator
       n = q                      # mache weiter mit der durch 10 geteilten Zahl
    end
    s += n^2                      # addiere das Quadrat der letzten Ziffer
    return s
end

… und das testen wir jetzt natürlich:

for i in [1, 7, 33, 111, 321, 1000, 73201]
   j = q2sum(i)
   println("Quadratquersumme von $i = $j")
end

Quadratquersumme von 1 = 1
Quadratquersumme von 7 = 49
Quadratquersumme von 33 = 18
Quadratquersumme von 111 = 3
Quadratquersumme von 321 = 14
Quadratquersumme von 1000 = 1
Quadratquersumme von 73201 = 63

Im Sinne der Aufgabe wenden wir die Funktion wiederholt an:

n = 129956799
for i in 1:14
    n = q2sum(n)
    println(n)
end

… und haben hier einen der ‘89er Zyklen’ getroffen.

Funktion Nr. 2

Wir müssen testen, ob die wiederholte Anwendung der Funktion q2sum() schließlich zu 1 führt oder in diesem 89er-Zyklus endet.

q2test(n) ermittelt, ob wiederholte Quadratquersummenbildung in den 89er-Zyklus führt:

function q2test(n)
    while n !=1 && n != 89       # solange wir nicht bei 1 oder 89 angekommen sind....
        n = q2sum(n)             # wiederholen 
    end
    if n==1 return false end     # keine 89er-Zahl
    return true                  # 89er-Zahl gefunden
end

… und damit können wir die Aufgabe lösen:

c = 0                        # mal wieder ein Akkumulator
for i = 1 : 10_000_000 - 1   # so kann man in Julia Tausenderblöcke zur besseren Lesbarkeit abtrennen
    if q2test(i)             # q2test() gibt einen Boolean zurück, kein weiterer Test nötig 
        c += 1               #    'if x == true' ist redundant, 'if x' reicht völlig 
    end     
end
println("$c numbers below ten million arrive at 89.")

8581146 numbers below ten million arrive at 89.

Zahlen, bei denen die iterierte Quadratquersummenbildung bei 1 endet, heißen übrigens fröhliche Zahlen und wir haben gerade die Anzahl der traurigen Zahlen kleiner als 10.000.000 berechnet.

Hier nochmal das vollständige Programm:

unsere Lösung von Project Euler No 92:

function q2sum(n)
    s = 0                      
    while n > 9                 
       q, r = divrem(n, 10)
       s += r^2                 
       n = q                    
    end
    s += n^2                    
    return s
end

function q2test(n)
    while n !=1 && n != 89      
        n = q2sum(n)           
    end
    if n==1 return false end   
    return true                 
end

c = 0
for i = 1 : 10_000_000 - 1   
    if q2test(i)
        c += 1
    end     
end
println("$c numbers below ten million arrive at 89.")

8581146 numbers below ten million arrive at 89.