Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
se:algorithmendatenstrukturen [2008-12-21 14:58] stefan angelegt |
se:algorithmendatenstrukturen [2009-01-11 17:51] stefan |
||
---|---|---|---|
Zeile 28: | Zeile 28: | ||
* Codeoptimierung | * Codeoptimierung | ||
* Arrays mit Quicksort sortieren (C: qsort) | * Arrays mit Quicksort sortieren (C: qsort) | ||
- | * Heapsort, Countingsort | + | * Heapsort, Countingsort, Radixsort |
- | * Backtracking (Was gibt vorgegebenes Programm aus?) | + | * Backtracking (Was gibt vorgegebenes Programm aus?) |
+ | ===== Postfix / Infix ===== | ||
+ | * mathematische Ausdrücke werden ublicherweise in der so genannten Infix-Schreibweise geschrieben: <code>(4 + 5) * (3 - 1) / 9</code> | ||
+ | * man kann solche Ausdrücke aber auch in der so genannten umgekehrten polnischen Notation angeben: <code>4 5 + 3 1 - * 9 /</code> | ||
+ | * Vorteile | ||
+ | * keine Berücksichtigung von Prioritäten der Operatoren nötig, es werden keine Klammern benötigt | ||
+ | * kann leicht mit Hilfe eines Stacks implementiert werden | ||
+ | * Umwandlung Infix -> Postfix (alle Ausdrücke müssen geklammert sein) | ||
+ | * Ausdruck von links nach rechts durchgehen | ||
+ | * Zahlen direkt ausgeben | ||
+ | * Operatoren auf den Stack legen | ||
+ | * bei schließender Klammer den obersten Operator ausgeben | ||
+ | |||
+ | ===== Lineare Rekursion ===== | ||
+ | * eine Funktion heißt rekursiv, wenn sie sich selbst oder ein von ihr aufgerufenes Programm sie selbst wieder aufruft | ||
+ | * jede Rekursion kann durch entsprechende Wiederholungen ausgedrückt werden und umgekehrt | ||
+ | * Beispiele für Anwendung von Rekursion | ||
+ | * Quadratzahlen: ''n<sup>2</sup> = (n - 1)<sup>2</sup> + 2n - 1'' | ||
+ | * größter gemeinsamer Teiler: ''ggT(n, m) = 0, wenn m = 0, sonst ggT(m, n mod m)'' | ||
+ | * Dreieckszahlen: ''(k * (k + 1)) / 2'' | ||
+ | * Umwandlung von Dezimal- in Dualzahl: ''bis zahl = 0: rest = zahl % 2, zahl = zahl / 2; Reste umgekehrt ausgeben''' | ||
+ | * wenn eine Funktion sich mehrmals aufruft erhält man eine nicht-lineare Rekursion in Baumstruktur | ||
+ | * Fibonacci-Zahlen: ''F(0) = 1; F(1) = 1; F(n) = F(n - 2) + F(n - 1)'' | ||
+ | * Binomialkoeffizient: ''n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)'' | ||
+ | * Pascal'sches Dreieck |