235 lines
8.3 KiB
Plaintext
235 lines
8.3 KiB
Plaintext
---
|
|
engine: julia
|
|
---
|
|
|
|
```{julia}
|
|
#| error: false
|
|
#| echo: false
|
|
#| output: false
|
|
using InteractiveUtils
|
|
```
|
|
|
|
# Erste Miniprogramme
|
|
|
|
|
|
## 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.
|
|
|
|
## Project Euler
|
|
|
|
Eine hübsche Quelle für Programmieraufgaben mit mathematischem Charakter und sehr unterschiedlichen Schwierigkeitsgraden ist [Project Euler](https://projecteuler.net/).
|
|
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.
|
|
|
|
---------
|
|
|
|
### Beispiel 1
|
|
|
|
::::::{.content-hidden unless-format="xxx"}
|
|
|
|
https://github.com/luckytoilet/projecteuler-solutions/blob/master/Solutions.md
|
|
https://math.stackexchange.com/questions/3370978/iterating-sum-of-squares-of-decimal-digits-of-an-integer-how-big-can-it-grow
|
|
aufg. 92
|
|
|
|
:::
|
|
|
|
::: {.callout-note icon=false .titlenormal}
|
|
## 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.
|
|
|
|
:::
|
|
|
|
1. Algorithmus:
|
|
- Teste alle natürlichen Zahlen <1000 auf Teilbarkeit durch 3 oder durch 5 und
|
|
- summiere die teilbaren Zahlen auf.
|
|
|
|
2. Umsetzung:
|
|
|
|
Wie liefert Julia den Rest der Ganzzahldivision? Solche Funktionen heißen typischerweise `rem()` (für *remainder*) oder `mod()`. [Nachlesen in der Doku](https://docs.julialang.org/en/v1/base/math/#Base.rem) 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:
|
|
|
|
:::{.callout-caution icon="false" collapse="true" .titlenormal}
|
|
|
|
## Eine Lösungsvariante:
|
|
|
|
```{julia}
|
|
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
|
|
```
|
|
:::
|
|
|
|
Natürlich geht das auch etwas kürzer:
|
|
|
|
:::{.callout-caution icon="false" collapse="true" .titlenormal}
|
|
|
|
## Noch eine Lösungsvariante:
|
|
|
|
```{julia}
|
|
sum([i for i in 1:999 if i%3==0||i%5==0])
|
|
```
|
|
|
|
:::
|
|
|
|
|
|
-----------
|
|
|
|
### Beispiel 2
|
|
|
|
|
|
::: {.callout-note icon=false .titlenormal}
|
|
## 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*](https://de.wikipedia.org/wiki/Top-Down-_und_Bottom-Up-Design) 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.
|
|
|
|
|
|
:::{.callout-caution icon="false" collapse="true" .titlenormal}
|
|
|
|
## `q2sum(n)` berechnet die Summe der Quadrate der Ziffern von n im Dezimalsystem:
|
|
|
|
```{julia}
|
|
#| output: false
|
|
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:
|
|
```{julia}
|
|
for i in [1, 7, 33, 111, 321, 1000, 73201]
|
|
j = q2sum(i)
|
|
println("Quadratquersumme von $i = $j")
|
|
end
|
|
```
|
|
|
|
Im Sinne der Aufgabe wenden wir die Funktion wiederholt an:
|
|
|
|
```{julia}
|
|
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.
|
|
|
|
:::{.callout-caution icon="false" collapse="true" .titlenormal}
|
|
|
|
## `q2test(n)` ermittelt, ob wiederholte Quadratquersummenbildung in den 89er-Zyklus führt:
|
|
|
|
```{julia}
|
|
#| output: false
|
|
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:
|
|
|
|
```{julia}
|
|
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.")
|
|
```
|
|
|
|
Zahlen, bei denen die iterierte Quadratquersummenbildung bei 1 endet, heißen übrigens [fröhliche Zahlen](https://de.wikipedia.org/wiki/Fr%C3%B6hliche_Zahl) und wir haben gerade die Anzahl der traurigen Zahlen kleiner als 10.000.000 berechnet.
|
|
|
|
Hier nochmal das vollständige Programm:
|
|
|
|
:::{.callout-caution icon="false" collapse="true" .titlenormal}
|
|
## unsere Lösung von Project Euler No 92:
|
|
|
|
```{julia}
|
|
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.")
|
|
|
|
```
|
|
|
|
:::
|