Das Teilerproblem history menue Letztmalig dran rumgefummelt: 24.12.07 18:41:43

Die Baronin von Birlinghoven hat ihren beiden Töchtern eine Truhe voller Goldmünzen hinterlassen. Ihr Testament bestimmt, dass das Gold einem benachbarten Kloster zukommt, falls es den Töchtern nicht gelingt, den Inhalt der Truhe wertmäßig genau in zwei Hälften untereinander aufzuteilen. Die Goldmünzen haben nur ganzzahlige Werte.
Beispiel: Eine Truhe Goldmünzen mit den Werten 1, 9, 5, 3, 8 Taler könnten die Töchter in die Hälften 1, 9,3 Taler und 5, 8 Taler teilen.
Eine Truhe mit den Werten 1, 9, 7, 3, 8 Taler fiele an das Kloster, weil die Aufteilung nicht möglich ist.
Aufgabe: Schreibe ein Programm, das bei Eingabe einer Folge ganzer Zahlen für die in der Truhe vorkommenden Werte die beiden Erbteile genau aufzählt, andernfalls das Erbe dem Kloster zuspricht, wenn eine Aufteilung nicht möglich ist.
Erstelle mindestens fünf Beispiele mit verschiedenen Truheninhalten. Der Inhalt einer Truhe sei 15, 27, 39, 7, 23,56,13. 39; 22, 5, 42, 34 Taler.
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 das Teilerproblem

Informatik-Profi-Wissen

Quellen:

LOG IN - Heft 146/147 (2007) Seite 47 ff.


1. Problembeschreibung history menue scroll up

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 history menue scroll up

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 history menue scroll up
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 history menue scroll up

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 history menue scroll up

 
 
 
 


6. Weiterführende Literatur history menue scroll up

 
 
 
 


7. Links zum Thema history menue scroll up

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


8. Verwandte Themen history menue scroll up

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 24. Dezember 2007

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)