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

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, ...
  

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.

Sieb des Eratosthenes für die Primzahlsuche

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

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

Grüße Sylvus

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.