Benutzer-Werkzeuge
se:algorithmendatenstrukturen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:algorithmendatenstrukturen [2009-01-10 17:27] stefan |
se:algorithmendatenstrukturen [2009-01-11 17:51] stefan |
||
|---|---|---|---|
| Zeile 30: | Zeile 30: | ||
| * Heapsort, Countingsort, Radixsort | * 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 | ||
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
