Schöne Probleme der Informatik?

[zarcaphii]

Hallo Forum,

ich bin neu hier, also mal eben was zu meinem Hintergrund:
Ich bin mit (Delphi)Programmierung in der elften Klasse in Berührung gekommen. Seitdem ist es mein Hobby, wobei ich noch nicht wirklich tief in der Materie bin. Die Grundlagen der OOP beherrsche ich.

Ich habe schon eine ganze Reihe von Problemen bzw. die Lösungen dazu programmiert. Angefangen von der Berechnung von Fakultäten oder der Fibonaccireihe bis hin zu Labyrinthen und dem Game of Life.

Alle diese Projekte hängen sehr stark an der Logik und weniger an der Oberfläche (in meinen Augen ein Pluspunkt!). Außerdem sind sie meiner Meinung nach sehr schön zu lösen.

Meine Frage ist, ob ihr in der Art noch weiter Probleme kennt. Solche Sachen machen mir einfach am meißten Spaß!

Ich würde mich über Links freuen!

[Fussball-Robby]

Hey und herzlichen Willkommen in der DP
Ich habe in den letzten Tagen eine Aufgabe bearbeitet, die irgendwann in der Oberstufe vorkommen wird: Das sog. 8-Damen-Problem. Wieviele Möglichkeiten gibt es, 8 Damen auf einem Schachbrett anzuordnen, ohne dass auch nur eine Dame eine andere schlagen kann? Stichwort dazu ist Backtracking bzw. rekursive Funktionen. Diese Aufgabe kann man auch schön mit OOP lösen.

[zarcaphii]

Ja, stimmt. Das habe ich auch mal gemacht. Allerdings hatte ich eine Iterative Lösung mit 8 Schleifen und endlos langen if-Abfragen. Das könnte ich natürlich mal neu programmieren, sodass es eben rekursiv arbeitet und flexibler(z.B. mehr/weniger Felder) ist. Alternativ könnte ich auch versuchen eine möglichst schnelle Lösung zu finden.

Danke für den Tipp!

[Nikolas]

Das SpringerProblem gehört auch in die Kategorie: Finde einen Weg auf einem Schachbrett (Brett beliebiger Größe), den ein Springer gehen darf, so dass er jedes Feld genau einmal betritt und wieder auf dem Ausgangsfeld landen kann. Hier kannst du Backtracking mit ein bischen Heuristik verbinden (wenn du ein EckFeld betreten kannst, dann mach es auch!).

[zarcaphii]

Ich habe mir mal den Wikipedia Artikel durchgelesen.

Zitat:

Nach der Wansdorffregel zieht der Springer immer auf das Feld, von dem aus er für seinen nächsten Zug am wenigsten freie (d.h. noch nicht besuchte) Felder zur Verfügung hat.
[...]
Die Verbindung von Warnsdorffregel und Backtracking-Verfahren ist möglich, führt aber bei großen Brettern wiederum zu exponentiell anwachsender Laufzeit.

Das hört sich ja machbar an. Gut, damit hätte ich ja schonmal 2 Probleme zu lösen.

Zitat von Fussball-Robby:

Das sog. 8-Damen-Problem.
[...]
Diese Aufgabe kann man auch schön mit OOP lösen.

Hm, so spontan fällt mir nicht ein, wie eine besonders objektorientierte Lösung da aussehen könnte. Hattest du an was bestimmtes gedacht? Gib mir nen Tipp

[bluesbear]

Was auch sehr interessant ist: Simplex
Und falls dir dann immer noch langweilig ist - es macht Spaß, sich mal mit
PROLOG zu beschäftigen.

[Lingel]

Etwas einfacher als die zuletzt genannten: Magische Quadrate

[Khabarakh]

Wenn's mathematisch sein darf: Project Euler.

[Meniskusschaden]

Eine interessante Aufgabe ist auch das sogenannte Problem der stabilen Heirat.

n Frauen und n Männer stellen jeweils eine Liste der von ihnen bevorzugten Partner auf, wobei der absolute Wunschpartner ganz oben steht, dann der nächste usw..

Aus diesen Listen müssen jetzt n Ehepaare gebildet werden. Wenn dabei mindestens ein Mann und eine Frau nicht miteinander verheiratet sind, obwohl beide auf der Liste des jeweils anderen auf einer höheren Position stehen als der tatsächliche Ehepartner, ist die Lösung instabil.

[Nikolas]

Und wo ist die Schwierigkeit?