Effiziente Algorithmen

[jobo]

Als Teeny hatte ich meine ersten Erfahrungen mit "Zahlenraten" gesammelt. Das konnte man aus dem Handbuch eines TI57 abtippen. (ohne Ahnung zu haben) Das war mein erstes Computerspiel.

Der Rechner hat sich eine Zahl ausgedacht zwischen 1 und 1000
Die geratene (eingetippte) Zahl hat er mit +, - oder Blinken beantwortet:
zu groß, zu klein, Treffer

Das gebe ich heute auch Praktikanten als Programmieraufgabe.

Wo ist dabei der Algorithmus?
Auf den kommt man am besten selbst, wenn man die Eingebung hat, dass es bessere Möglichkeiten als "Raten" geben könnte. Der Algorithmus wird also nicht implementiert, sondern intuitiv oder zielgerichtet ersonnen.
Erst wenn man heute "Computergegner" implementieren würde, würde man den Algorithmus schreiben müssen.

An diesem Beispiel ist relativ einfach zu verstehen, was der Unterschied zwischen Raten und Algorithmus ist, im Nebel stochern und zielgerichtetem, effizientem und vorhersehbarem Vorgehen.
Natürlich nur, wenn man auf einen Algorithmus gekommen ist, der ja im Kern in vielen Sortieralgorithmen verwendet wird. Nebenbei ist es auch eine sehr bildliche Nutzung der Strategie Device & Conquer.

Eine Zahl zwischen 1 und 1000 ist sehr schwierig zu raten, aber
Eine Zahl zwischen 1 und 500 ist schon etwas einfacher zu raten...
usw.

[Gausi]

Zitat von jobo:

Nebenbei ist es auch eine sehr bildliche Nutzung der Strategie Device & Conquer.

Die Methode nennt sich Divide & Conquer - Teile und Herrsche.

[jobo]

Richtig!

Ich könnte ja jetzt behaupten, das war die Autokorrektor, aber ich bin wahrscheinlich mit was anderem beschäftigt gewesen.

"Devide and Conquer"
Kannte ich zu TI57 Zeiten noch nicht, gab's aber spät in der Schule. Ich weiß nicht mehr, wo zuerst: Latein oder Informatik

[Andreas13]

Das Horner-Schema zur effizienten Polynomberechnung und die rekursive Berechnung der Fakultät (n!) sind recht verständlich und einfach zu erklären. Wesentlich komplexer ist das KMP-Muster-Suchverfahren (Knuth, Morris und Pratt).

Gruß, Andreas

[p80286]

"Divide et impera"

Ich stelle mich zu den "Binäre-Suche-Leuten". Das einzig dumme daran ist, daß die Daten sortiert sein müssen. Bei Spielkarten mußman sich vorher noch über die Wertigkeit der Bilder und des Asses einigen. MMn ein schönes Beispiel für einen mfassenden Algo.

Gruß
K-H