The Chinese-Box oder the Chinese Postmen-Problem

Letztmalig dran rumgefummelt: 06.09.26 22:17:57

	Finde alle natürlichen Zahlen mit der Eigenschaft, dass sie auf ihre Quadratwurzel enden. Beispiel: Wegen Quadratwurzel 5776 = 76 ist 5776 eine der gesuchten Zahlen. Wir verschaffen uns - mittels Papier und Bleistift, Taschenrechner usw. - einige einfache Spezialfälle (Beispiele): Für die Zahlen n von 0 bis 9 lauten die Paare (n, n²) wie folgt: (0, 0), (1, 1). (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81). Die Zahlen 0, 1, 5 und 6 sind also Autoquadzahlen. Damit haben wir bereits vier Lösungen gefunden. lm Bereich 10 <= n < 99 erhalten wir die Paare (25, 625) und (76, 5776).
	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 das hat auch viel mit Problemlösungsstrategien zu tun Logo für das Chinesische Kisten-Problem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 48 ff.

The Chinese-Box

1. Problembeschreibung

	Das Briefträgerproblem ist ein Modell aus der Graphentheorie und kombinatorischen Optimierung, bei welchem man sich des übertragenen Bildes eines Postboten, der auf dem kürzesten Weg Briefe austrägt, bedient: Ein Postbote soll die Briefe (auf beiden Seiten der Straße gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen. Seinen englischen Namen (Chinese postman problem) erhielt das Briefträgerproblem durch Alan Goldman nach dem chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte. Eine Lösung wurde 1973 durch Jack Edmonds und Ellis L. Johnson angegeben. Modelliert wird das Problem mittels Graphen. Dabei werden Straßen als Kanten und Kreuzungen als Knoten modelliert. Den Kanten wird die Länge der entsprechenden Straße zugeordnet. Gefragt ist nun nach einem kürzesten Zyklus, der alle Straßen mindestens einmal durchläuft.
	... das Chinesische Kisten-Problem bei WIKIPEDIA (english Version)  ... das Chinesische Kisten-Problem bei WIKIPEDIA (deutsche Version)  ... das Chinesische Kisten-Problem  ... das Chinesische Kisten-Problem bei (.... auch als SVG-Datei)
	n n2 1 1 5 25 6 36 25 625 76 5776 376 141376 625 390625 9376 87909376 90625 8212890625 109376 11963109376 890625 793212890625 2890625 8355712890625 7109376 50543227109376 12890625 166168212890625 87109376 7588043387109376 212890625 45322418212890625 die ersten 16 Autoquadzahlen
	n n2 5 25 25 625 625 390625 90625 8212890625 890625 793212890625 2890625 8355712890625 12890625 166168212890625 212890625 45322418212890625 die ersten 10 Fünfer-Autoquadzahlen

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.
	Programm für weitere Spezialfälle Wir wollen nun ein Programm schreiben, das alle dreistelligen Autoquadzahlen ermittelt. Hier stellt sich die Frage, wie man die letzten drei Ziffern einer Zahl herausgreift. Aus dem Mathematikunterricht wissen wir. dass sich die letzten n Ziffern als Rest bei Division durch 10° gewinnen lassen. Damit können wir ein erstes JAVA-Programm aufschreiben: public class Autoquad public static void main (String[] xy) for (long n = 100; n < 1000; n++) long q = n * n; if (q % 1000 == n) System.out.println(" " + n + , " + q); } // Ende for Ende main Ende Autoquad Es liefert uns die Zahlenpaare (376, 141376) und (625, 390625), also die Autoquadzahlen 376 und 625.
	Programm-Modifikation für noch mehr einfache Fälle Um auch die ein- und die zweistelligen Zahlen zu untersuchen, ändern wir in obigem Programm die Zählschleife zum einen so, dass sie von 1 bis 9, und zum anderen so, dass sie von 10 bis 99 läuft. Im ersten Fall rechnen wir modulo 10, im zweiten modulo 100. Damit erhalten wir die Zahlenpaare (1, 1), (5, 25), (6, 36). (25. 625) und (76, 5776). Nun kennen wir also - außer dem trivialen Fall 0 - die ersten sieben Autoquadzahlen, nämlich 1, 5, 6, 25, 76, 376 und 625.
	Verallgemeinerung zum Erfassen aller bisherigen Lösungen Wir entwickeln nun ein Programm, das die verschiedenen Bereiche 1..9, 10..99, 100..999 usw. der Reihe nach durchläuft. Diesem Zweck dient eine äußere Schleife, welche die genannten Potenzen von 10 erzeugt. Das folgende Programm liefert Bild 4, also zusätzlich die B. bis 16. Autoquadzahl. public class Autoquad public static void main (String[] xy) long potenz = 1; while (potenz < 10000000) long modul = 10 * potenz; for (long n = potenz; n < modul ; n++) long q = n * n; if (q % modul == n) System.out.println(" " + n + , " + q); } // Ende for potenz = modul; } // Ende while Ende main Ende Autoquad
	Hier stoßen wir nun an die Grenze des Rechnens mit „langen" ganzen Zahlen (Datentyp long). Sie lässt sich durch Übergang zu Zahlen vom Typ Biglnter überwinden. Doch wird nun die (Länge der) Rechenzeit zum Problem. Damit ist der Augenblick gekommen, unser Denkvermögen einzusetzen, d. h. die Aufmerksamkeit weg vom Programmieren auf die Entwicklung eines etwas intelligenteren Algorithmus zu richten. Bisher sind wir ja mit „Brachialgewalt" vorgegangen, indem wir jede einzelne Zahl darauf prüften, ob sie autoquadratisch sei: Die Anzahl der zu prüfenden Zahlen und damit auch die Rechenzeit stieg mit jeder zusätzlichen Stelle auf das Zehnfache. Wir halten fest: Ein Programm, bei dem die Rechenzeit mit der Problemgröße exponentiell wächst, ist für die Praxis wertlos. 6. Verbesserung des Algorithmus durch mathematische Analyse Schauen wir uns die bisher ermittelten Autoquadzahlen etwas genauer an! Es fällt auf, dass aus einer bereits ermittelten Autoquadzahl einfach durch Erweiterung eine weitere gewonnen werden kann, d. h. dadurch, dass wir vorne eine Ziffer X oder XO anfügen. Beispielsweise wird aus 76 die neue Autoquadzahl 376 oder aus 625 wird 90625. Entscheidend dabei ist: Auf diese Weise gewinnen wir alle Autoquadzahlen. Denn es gilt der Satz 1: Zu jeder Autoquadzahl > 10 gibt es eine (kleinere) Autoquadzahl, deren Erweiterung sie ist. Wir verwenden ihn zunächst in folgender Form: Lässt man in einer Autoquadzahl die erste Ziffer weg, so erhält man wieder eine. Satz 1 zeigt, dass eine Autoquadzahl stets auf eine kleinere reduziert werden kann. Da 5 und 6 die einzigen (nichttrivialen) einstelligen Autoquadzahlen sind, müssen alle anderen auf eine dieser beiden Ziffern enden. Der Satz besagt weiter, dass alle größeren Autoquadzahlen durch Erweiterung aus kleineren gebildet werden können, d. h. durch Voranstellen neuer Ziffern. Dass eine solche Erweiterung immer möglich ist, geht aus folgendem Satz hervor: Satz 2: Jede Autoquadzahl kann durch Voranstellen einer eindeutig bestimmten Ziffer zu einer größeren Autoquadzahl erweitert werden. Der Beweis (siehe Scheuch, 2003, S. 40) liefert einen Algorithmus zur Bestimmung der Erweiterungsziffer. Ist z„ die Anzahl der Ziffern der natürlichen Zahl n, so gilt für die auf 5 endenden Autoquadzahlen: Wenn die (z„ + 1)-te Ziffer von n2 ungleich null ist, so wird die neue Autoquadzahl durch die ersten z„ + 1 Ziffern von n2 gebildet, andernfalls durch die ersten zn + 2 Ziffern - und zwar jeweils von rechts her gezählt. Sei beispielsweise n = 90625, dann ist zn = 5 und n2 = 8212890625; die sechste Ziffer von rechts ist 8, also ungleich null. Somit ist die nächste Fünfer-Autoquadzahl 890625 (siehe Bild 4, vorige Seite). Für die Sechserzahlen gilt: Die neue Autoquadzahl wird durch die ersten zn + 1 Ziffern von n2 gebildet, wobei die (Zn + 1)-te Ziffer durch ihr Zehnerkomplement zu ersetzen ist - und zwar jeweils von rechts her gezählt. Sei beispielsweise n = 9376, dann ist z„ = 4 und n2 = 879_09376; das Zehnerkomplement der fünften Ziffer von rechts ist 10 - 0 = 10, also ist die nächste Sechser-Autoquadzahl 109376 (siehe Bild 4, vorige Seite). Das folgende Programm liefert die Folge der auf 5 endenden Autoquadzahlen beliebiger Länge (Bild 5), d. h. soweit der Speicherplatz reicht: import java.math.*; public class Autoquad { public static void main (String[] xy) String a = "5", for (int i = 0; i < 10; i++) BigInteger n = new BigInteger(a); String q = n.multiply(n).toString(); System.out.println(" " + a + q); int zn = a.length(); int zq = q.length(); char ziffer = q.charAt(zq - zn - 1); a = ziffer + a; if (ziffer == '0') a = q.charAt(zq - zn - 2) + a; // Ende for // Ende main // Ende Autoquad Wir ziehen folgendes Fazit: Wenn du ein Programm geschrieben, getestet, von Fehlern befreit und zum Laufen gebracht hast, so denke noch einmal über das Problem nach. Häufig wirst du eine bessere Lösungsstrategie entdecken. Das meinte Pölya, wenn er davon sprach, dass sich auf diese Weise das Wissen und die Fähigkeit zum Problemlösen erweitern lassen.

3. Lösungsalgorithmus

Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

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.

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-Damen-Problem das Cliquenproblem das Dominoproblem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Wortproblem das Hamiltonproblem das K-Farben-Problem das Flaggenproblem das Halteproblem das Königsberger Brückenproblem das Philosophenproblem das Teilsummensummenproblem das Post'sche Korrespondenz-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Springerproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Knotenüberdeckungsproblem The Busy Beaver-Problem das Spannbaumproblem der Maze-Running-Algorithmus das Schachspiel Greedy Algorithm das Maximalflussproblem das Syntheseproblem   das k-Next-Neighbor-Problem   Schwarmintelligenz ... fehlererkennende Algorithmen -  ISBN-Nummer das Binärbaumproblem geometrischen Probleme Dijkstra-Algorithmus Fermat'sches Problem FERMAT's letzter Satz   ZIP-Algorithmus   Bresenham-Algorithmus   der Huffman-Code LZW-Kompression   Quadratsummen-Problem   die glücklichen & traurigen Zahlen   Smarandache-Wellin-Zahlen der austarierte Baum   Trunkierbare Primzahlen   FERMAT'scher Großer Satz   Eulerkreis   Lauflängen-Codierung   Zeichenkettenabgleich
	die Primzahlsuche die Primzahl-Faktorierung Miller-Rabin-Test   der Fluch des Pharao-Algorithmus die Chiffrierung ohne Schlüssel das Teilerproblem Die Sache mit dem Wüstenfit (gefällt mir zu gut) Die Magischen Quadrate - hier beschrieben von Stefan Hecker in einer Belegarbeit aus dem Schuljahr 2001/02 das Chinesische Kisten- oder chinas Postmen-Problem das Labyrinth das PASCAL'sche Dreieck SUDOKU
	einfache aber rechenintensive Spielereien mit Zahlen all den folgenden Problemstellungen ist gemein, dass sie extrem einfach zu beschreiben sind - einzelne Lösungen oder gar alle bzw. mindestens viele zu finden, ist jedoch u. U. extrem zeitkomplex - auch schnelle Computer können daran sehr lange tüffteln. - wer's nicht glaubt, probiert's aus, aber vorab die Randbedingungen gut durchlesen - teilweise gibt's extrem lange Wartezeiten und die Lösung erscheint evtl. in einer Woche, wenn überhaupt Selbst, wenn wir die mitunter große Laufzeit akzeptieren können, stoßen wir teilweise recht schnell an die Realisierbarkeit durch die verfügbaren Datentypen - eine Million ist hier ein eher kleiner Wert - dies zeigen uns sehr deutlich die Perfect Numbers die Primzahl-Zwillingssuche die Primzahl-Palindrome der Kaprekar Algorithmus die befreundeten Zahlen Pythagoräische Tripel die Schmidtzahlen das Autoquadratzahlenproblem Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das 153-Problem - Narziß-Zahlen   die Pólya-Vermutung Zahlensystem-Umechner ...als Startbare Datei Software zur Veranschaulichung der Zahlenumrechung das Palindrom-Spiegelsummen-Problem die Perfect Numbers die ABC-Vermutung

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Ros am 24. Dezember 2007