Greedy Algorithm - die gierigen Algorithmen

Letztmalig dran rumgefummelt: 01.02.26 10:09:33

	... oder auch: Kaprekar-Algorithmus. Beschrieben wird ein Zahlenphänomen, nach welchem von einer beliebigen vierstelligen Zahl nach mehreren (maximal sieben!) Wiederholungen sich immer die Zahl 6174 ergibt. Dazu ist von der vierstelligen Zahl (nicht vierstellige Werte sind durch Anfügen von Vornullen vierstellig zu machen) immer die jeweils größtmögliche  sowie die kleinstmögliche zu bilden und als Absolutwert im Ergebnis voneinander zu substrahieren.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für die Greedy Algorithm begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Problembeschreibung

	Man möge sich bitte ein paar Gedanken um die Arbeitsweise von Suchnaschinen wie Google machen. Theoretisch müssten für eine vollständige sowie umfängliche Analyse einer Anfrage ständig und für jeden alle verfügbaren Websites vollständig durchsucht werden. Das wäre definitiv unmöglich, da allein die Beantwortung EINER Anfrage vollumfänglich eine Anwortzeit von mehreren Jahren hätte. Das hat zur Konsequenz, dass wir mit einer bestimmten verfahrensweise einen Teil der Gesamtmenge durchsuchen und davon das optimale Ergebnis - also nicht das maximale) nutzen.
	... neue Websites 2025 ...tägliche  neue Websites 2025
	nimm eine beliebige vierstellige Zahl, deren einzelne Stellen nicht alle gleich sein dürfen (1111, 2222, ... , 9999 entfallen also)

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Ein Wanderer möchte möglichst hoch hinaus. Es ist jedoch so neblig, dass er nur 5 Meter weit sehen kann. Er verfolgt eine einfache Strategie: Er sieht sich in seiner Umgebung um, welcher Punkt der höchste ist und geht dann dorthin. Dort schaut er sich wieder um, welcher Punkt der höchste ist, geht dorthin, und so weiter, bis er keinen höheren Punkt mehr findet. Er kehrt niemals um, um evtl. durch einen anderen Weg einen noch höheren Berg zu finden.
	Greedy Algotihmus mit frei wählbarem Startpunkt Greedy Algotihmus mit festem Startpunkt     ... Greedy Algorithm ... Greedy Algorithm - Download im CorelDraw-Format ... Greedy Algorithm ... Greedy Algorithm - Download im CorelDraw-Format
	Um das große Ziel zu erreichen, sind kleine Einzelschritte nötig. Der Wanderer geht in jedem Schritt maximal 5 Meter weit. In jedem der Einzelschritte sind nur begrenzt Informationen verfügbar.
	Nachdem ein Einzelschritt ausgeführt wurde, wird dieser Schritt nicht mehr zurückgenommen. Der Wanderer denkt nicht darüber nach, 3 Schritte zurückzugehen, um an einem anderen Ort einen besseren Weg zu finden.
	Die gefundene Lösung ist nicht notwendigerweise die global optimale. Der Wanderer erreicht wahrscheinlich den Gipfel eines kleinen Hügels statt den eines großen Berges.
	Je nach Ausgangssituation kann sich die gefundene Lösung stark unterscheiden.

3. Lösungsalgorithmus

	Ein einfaches Beispiel für einen Greedy Algorithmus ist das Problem des Wechselgeldes. Angenommen, du musst 36 Cent Wechselgeld geben und hast Münzen zu 1 Cent, 2 Cent, 5 Cent, 10 Cent, 20 Cent und 50 Cent zur Verfügung. Der Greedy Algorithmus würde zunächst die 20-Cent-Münze nehmen, dann die 10-Cent-Münze, dann die 5-Cent-Münze und schließlich die 1-Cent-Münze.
	... was ist ein Greedy-Algorithmus? ... Greedy-Algorithmus in der BWL ... Greedy-Algorithmus in der Schule

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.
	Verworfene Variante I Verworfene Variante II       ... Greedy Software - Arbeitsstand Dezember 2025 Download als ZIP-Archiv arbeitet mit einem Arry of Button als Akti-Komponenten Shapes als Hintergrund Button Arry schalten falschen Index

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Dezember 2007