Kleinstes gemeinsamer Vielfaches

Letztmalig dran rumgefummelt: 29.05.08 07:09:47

	Die Suche nach dem kleinsten gemeinsamen Vielfachen sowie auch die, nach dem größten gemeinsame Teiler sind zwei eng benachbarte Verfahren. In der englischsprachigen internationalen Literatur wird der mit gcd (greatest common divisor) und das mit lcm (least common multiple) bezeichnet.
	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
	Praktische Elementaralgorithmen Logo für das kleinste gemeinsame Vielfache begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.

1. Problembeschreibung

	Gegeben sei eine endliche Mengen ganzer Zahlen im Bereich von - ∞ bis + ∞, wobei die Frage lautet, ob sich die Gasamtmenge in jeweils wertmäßig gleiche Teile zerlegen lässt, wobei die gegebenen Zahlen immer den jeweiligen Teilen zugeordnet werden müssen?
	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich - Beispiel: M = {-11, -9, -5, -3, 2, 4, 13,21, 23} Antwort: JA - nämlich für die Teilmenge m = {-11, -9, -5, 2, 23}

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

	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.

3. Lösungsalgorithmus

	Das KGV ist genau die Zahl, welche von den kleinsten beginnend zuerst durch alle gegebenen Zahlen Teilbar ist - denn wer sagt denn, dass dies immer zwei sein müssen?

4. Programmvorschläge

	Dies ist ein relativ einfacher Versuch, vorerst einmal für kleine Faktoren in akzeptabler Geschwindigkeit kleinste gemeinsame Vielfache zu finden. Logistisch ist es nicht gerade der Hammer, laufzeittechnisch lässt sich der Algorithmus sicherlich optimieren - aber wir haben erst einmal einen Lösungsvorschlag.
	Finden des kleinsten gemeinsamen Vielfachen Anwendung als Delphi 6.0-Archiv hier als startbares Programm

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 am 8. Januar 2008