Pythagoräische Tripel und anderes

Letztmalig dran rumgefummelt: 12.06.08 13:23:08

	Seit uralten Zeiten ist bekannt, dass die Summe zweier Quadratzahlen wieder eine Quadratzahl sein kann. Das klassische Beispiel ist 32 + 42 = 52; aber es gibt unendlich viele weitere Beispiele, die als pythagoräische Tripel bezeichnet werden. Von der pythagoräischen Beziehung leiten sich viele andere interessante Probleme her.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Informationen 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für die pythagoräischen Tripel begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 2/98 Seite 70

1. Problembeschreibung

	Auf der Suche nach perfekten Schachteln Das 3-4-5Dreieck kann als Hälfte eines Rechtecks aufgefasst werden, bei dem alle Strecken, die durch Verbindung je zweier Ecken entstehen, ganzzahlige Länge haben. Dies führt auf die Frage, ob es eine rechteckige Schachtel mit ganzzahligen Seiten geben kann dergestalt, dass die durch paarweises Verbinden aller sechs Ecken entstehenden Strecken ebenfalls ganzzahlige Länge haben; eine derartige Schachtel wird perfekt genannt. Auf diese Weise entstehen vier neue Längen: Die drei Diagonalen der Seitenflächen und die Hauptdiagonale, die durch den Mittelpunkt der Schachtel geht. Im Jahr 1895 meinte Pierre Brocard bewiesen zu haben, dass es keine perfekte Schachtel geben könne; sein Beweis war jedoch fehlerhaft, denn er setzte voraus, dass die Seitenlängen paarweise teilerfremd sind.
	Aufgabe 1: Beweisen Sie, dass bei einer perfekten Schachtel zwei ihrer Seiten nicht tellerfremd sind! Gesucht ist also eine positive ganzzahlige Lösung des folgenden Gleichungssystems: x2 + y2 = a2, x2 + z2 = b2, y2 + z2 = c2, x2 + y2 + z2 = d2, wobei x, y, z die Länge der Seiten, a, b, c die der Seitendiagonalen und d die der Hauptdiagonalen ist. Fordern wir lediglich, dass nur sechs der sieben Größen ganzzahlig sind, bekommen wir drei einfachere Problemversionen: Die Hauptdiagonale braucht nicht ganzzahlig zu sein; in diesem Fall wird die Schachtel semiperfekt genannt. Eine der Seitendiagonalen braucht nicht ganzzahlig zu sein. Eine der Seiten braucht nicht ganzzahlig zu sein.
	Aufgabe 2: Schreiben Sie ein Programm zum Finden semiperfekter Schachteln. Die kleinste Lösung war schon Paul Halcke (1719) bekannt; wie lautet sie? Angenommen, jemand hat zur Lösung von Problemversion 2 folgenden Algorithmus aufgeschrieben und ausgeführt: FÜR x VON 1 BIS 100 WIEDERHOLE FÜR y VON 1 BIS 100 WIEDERHOLE FÜR z VON 1 BIS 100 WIEDERHOLE d := sqrt(sqr(x) + sqr(y) + sgr(y)) WENN d ganzzahlig DANN Ausgabe: x, y, z, d ENDE-WIEDERHOLE Dabei stellt er fest, dass unnötigerweise gewisse Lösungen mehrfach vorkommen. Aufgabe 3: Mit welchen Änderungen des Algorithmus lässt sich dies vermeiden, und wie viel Rechenschritte können gespart werden?

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

	Kein mächtiges Problem, aber imenser Rechenaufwand, da jedes Argument a mit zwei weiteren Argumenten verrechnet und verglichen werden muss.

3. Lösungsalgorithmus

	Der Lösungsalgorithmus besteht in der Kernprozedur darin, einen ganzzahligen Wert a anzunehmen, sein Quadrat zu berechnen und für diese in den angegebenen Dimensionen zwei weitere Quadratzahlen b2 sowie c2 zu suchen, welche in sich die Eigenschaft besitzen, das gilt: a2 + b2 = c2.

4. Programmvorschläge

	Entstanden im Kursunterricht der Jahrgangsstufe 12 des Schuljahres 2007/08 ist dieser Vorschlage, welcher in sich schon recht effizient und somit auch hinreichend schnell arbeitet. Bedingt durch die progressiv ansteigende Zahl komplexer Berechnungen sowie Vergleichsoperationen kann die Rechenzeit sehr groß werden.
	Finden phytagoräischer Tripel Programm zur Ermittlung phytagoräischer Tripel bis 100000 Download als ZIP-Archiv im Delph 6.0-Format Download als startbare .EXE-Datei

5. Zusammenfassung

6. Weiterführende Informationen

	War 'ne tolle Sache (zumindest für mich als Lehrer), einmal ein Schuljahr lang mit Schülern über doch die Grenzen von Programmiersprachen tangierende Probleme zu diskutieren, diese auszuloten, Algorithmen zu finden und wieder wegzuwerfen. Dümmer geworden ist dabei wahrscheinlich keine der betroffenen Seiten, die Schüler werden's teilweise einige Monate später an Universitäten bemerken ;-) Alles war im Rahmen des Möglichen: es anstrengend (was es ja sein soll), aber machbar - unten kann man einige Ergebnisse einsehen. Alles, was präsentiert wird, ist Wissensstand  Juni 2008 ;-)
	die Primzahl-Zwillingssuche der Kaprekar Algorithmus die befreundeten Zahlen das 153-Problem - Narziß-Zahlen die Schmidtzahlen das Autoquadratzahlenproblem Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das Palindrom Spiegelsummen-Problem die Perfect Numbers
	die Zahlenteiler GGT KGV   die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-) die Pseudoprimzahlen Quersummenermittlung Primzahlfaktorisierung

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 28. Januar 2008