Sylvus - Di 24.11.09 21:09
Titel: Algorithmen

---

Hay Leute,
muss was über Algorithmen machen und kenn mich da eigentlich ziemlich gut aus :)
Hab nur die Frage, ob ihr "coole" (geniale) Algorithmen kennt, die ich verwenden kann.

Also es sollen kleine Aufgaben wie z.B. KGV-Berechnung, oder Primzahlen... sein, aber ich will elegante Lösungen.
Gerne auch was rekursives, wo man nicht sofort durchsteigt.

Brauche aber keine 500 Zeilen Algos. Eher kurze, einfach nette Optimierungen, oder andere Sachen!

Vielleicht hat ja jemand von euch ne Idee....
DANKE

Grüße Sylvus

Gausi - Di 24.11.09 21:15

---

Zum Beispiel:

• Bubblesort (kleiner Scherz ;-))
  
• Quicksort, Heapsort, Mergesort zum Sortieren
  
• Boyer-Moore oder Knuth-Morris-Pratt zur Substring-Suche
  
• Berechnung der "Levenshtein-Distanz" zweier Strings mit dynamischer Programmierung
  
• Kürzeste-Wege in Graphen, minimale Spannbäume, ...
  

Boldar - Di 24.11.09 22:49

---

Solovay-Strassen-Test oder
Miller-Rabin-Test
sind auch interessant, allerdings (auch mathemathisch) schwer zu verstehen und lohnen sich nur bei sehr großen Zahlen, also muss man ne Bigint-Unit benutzen.

F34r0fTh3D4rk - Di 24.11.09 23:02

---

T?RME VON HANOI

Nersgatt - Mi 25.11.09 08:29

---

Sieb des Eratosthenes [http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes] für die Primzahlsuche

danielf - Mi 25.11.09 09:41

---

Ich hatte auch mal eine interessante Aufgabe in Algodat (Algorithmen und Datenstrukturen). Dort ging es um Wechselgeldberechnung. Alle Möglichkeiten sollen dabei berechnet/angezeigt werden. Der Trick war, dass die Währungen nicht wie üblich waren, sondern die Größen beliebig.

Z.B. 1 Cent, 7 Cent, 12 Cent

Soll man nun 14 Cent wechseln, ist die Kombination mit dem wenigsten Münzen nicht 2 * 12 + 2 * 1 (4Münzen), sondern eben 2 * 7 Cent (2 Münzen). Man benötigt einen anderen Algorithmus wie wenn man bei "normalen"/realen Geldeinheiten.

Eine schöne Backtracking-Aufgabe :)

Gruß Daniel

Sylvus - Mi 25.11.09 20:43

---

Hay, schonmal sehr cool :)
Gerne mehr, bringt mir auch selbst noch viel! Werd die durcharbeiten - bis dann!

Grüße Sylvus

Delphi-Laie - Sa 12.12.09 12:26

---

Sylvus hat folgendes geschrieben :

Hab nur die Frage, ob ihr "coole" (geniale) Algorithmen kennt, die ich verwenden kann. Also es sollen kleine Aufgaben wie z.B. KGV-Berechnung, oder Primzahlen... sein, aber ich will elegante Lösungen.

Nehmen wir den Gegensatz von KGV: GGT! Und da fällt mir sofort der Euklidische Algorithmus ein: Einer der ältesten Algorithmen überhaupt und auch für antike Verhältnisse wahrhaft genial. Eleganz ist ohnehin subjektiv, aber elegant er ist es m.E. auch, denn er kommt ohne Primzahlfaktor(en)zerlegung (letzteres wäre übrigens auch ein Kandidat für einen Algorithmus) aus.

Sylvus hat folgendes geschrieben :

Gerne auch was rekursives, wo man nicht sofort durchsteigt.

Die Rekursion bietet sich bei der Determinantenberechnung an, ja, sie drängt sich dabei geradezu auf.