Project Euler
it-single, 10:23h
Momentan arbeite ich in meiner Freizeit am Projekt Euler.
Eigentlich wollte ich nur die neue Programmiersprache Scala erlernen. Da mir aber nur das Lesen eines Buches zu theoretisch war, habe ich mir Programmieraufgaben gesucht, bei der ich die neue Programmiersprache gleich ausprobieren konnte. Ein Artikel in einer Computerzeitschrift hat mich dann zum Projekt Euler gebracht.
Bei diesem Projekt muss man mathematische Rechenaufgaben mit Hilfe des Computers lösen. Nach der Eingabe der richtigen Lösung in ein Internet-Formular steigt der Wert des eigenen Benutzerprofils.
Um diese Aufgaben zu lösen, muss man mathematische Fähigkeiten mit Programmierfähigkeiten kombinieren. Betrachten wir dazu mal die folgende Aufgabe:
Diese Aufgabe kann der beste Mathematiker nicht lösen, wenn er nur Papier und Bleistift zur Verfügung hat. Diese Lösung muss mit Hilfe des Computers gesucht werden. Ein einfacher Brute-Force-Ansatz mit dem Computer ohne vorherige mathematische Überlegungen ist aber ebensowenig zielführend. Wenn man einfach für die Variablen a, b und c jeweils alle 1000 Kombinationen durchprobieren würde, müsste man eine Milliarde Möglichkeiten durchrechnen. Die Rechenzeit des Computerprogramms muss aber gemäß den Regeln unter einer Minute bleiben. Deshalb muss man den Suchraum, der vom Computer durchsucht wird, reduzieren. Der erste Ansatz dazu wäre, für die Variable c nicht alle 1000 Kombinationen durchzuprobieren, sondern die Variable c aus (1000 - a - b) zu berechnen. Im nächsten Schritt könnte man sogar noch b aus a bestimmen, so dass man nur noch 1000 Möglichkeiten für a durchprobieren müsste. Dieses Beispiel zeigt, wie man zur Lösung dieser Aufgaben mathematische Kenntnisse mit Programmierfähigkeiten verknüpfen muss.
Nach der richtigen Lösung einer Aufgabe wird man für das Diskussionsforum zu dieser Aufgabe freigeschaltet. Es ist interessant, die dort aufgeführten Lösungen zu studieren. Zum Beispiel schreibt ein leicht frustrierter Basic-Programmierer, dass sein Computerprogramm 3 Stunden rechnen musste, um zur Lösung zu kommen. Nachdem ich das gelesen habe, war ich ganz stolz, dass mein Programm dafür nur eine halbe Sekunde benötigt hat. Aber danach liest man von dem C-Programm eines russischen Mathematikers, welches nur 14 Millisekunden benötigt. Die Russen scheinen dort insgesamt gut vertreten zu sein.
Momentan habe ich nach einer Woche (in der es Abends immer spät wurde) 40 Aufgaben gelöst. 300 Aufgaben warten noch auf mich. Ich hatte schon etwas Sorgen, dass ich irgendwann alle Aufgaben gelöst habe und mir langweilig wird. Diese Bedenken wurden aber schnell zersteut, als ich die Liste der Aufgaben mal nach dem Schwierigkeitsgrad sortiert habe. Auf Platz 83 steht die Entwicklung eines Computerprogramms, welches automatisch Sudokus löst. Die Funktionsfähigkeit dieses Programms muss man dadurch beweisen, dass man eine Sammlung von Sudoku-Aufgaben herunterlädt, diese automatisch vom Programm lösen läßt und dann eine Quersumme dieser Lösungen in das Lösungsformular eingibt.
Eigentlich wollte ich nur die neue Programmiersprache Scala erlernen. Da mir aber nur das Lesen eines Buches zu theoretisch war, habe ich mir Programmieraufgaben gesucht, bei der ich die neue Programmiersprache gleich ausprobieren konnte. Ein Artikel in einer Computerzeitschrift hat mich dann zum Projekt Euler gebracht.
Bei diesem Projekt muss man mathematische Rechenaufgaben mit Hilfe des Computers lösen. Nach der Eingabe der richtigen Lösung in ein Internet-Formular steigt der Wert des eigenen Benutzerprofils.
Um diese Aufgaben zu lösen, muss man mathematische Fähigkeiten mit Programmierfähigkeiten kombinieren. Betrachten wir dazu mal die folgende Aufgabe:
Diese Aufgabe kann der beste Mathematiker nicht lösen, wenn er nur Papier und Bleistift zur Verfügung hat. Diese Lösung muss mit Hilfe des Computers gesucht werden. Ein einfacher Brute-Force-Ansatz mit dem Computer ohne vorherige mathematische Überlegungen ist aber ebensowenig zielführend. Wenn man einfach für die Variablen a, b und c jeweils alle 1000 Kombinationen durchprobieren würde, müsste man eine Milliarde Möglichkeiten durchrechnen. Die Rechenzeit des Computerprogramms muss aber gemäß den Regeln unter einer Minute bleiben. Deshalb muss man den Suchraum, der vom Computer durchsucht wird, reduzieren. Der erste Ansatz dazu wäre, für die Variable c nicht alle 1000 Kombinationen durchzuprobieren, sondern die Variable c aus (1000 - a - b) zu berechnen. Im nächsten Schritt könnte man sogar noch b aus a bestimmen, so dass man nur noch 1000 Möglichkeiten für a durchprobieren müsste. Dieses Beispiel zeigt, wie man zur Lösung dieser Aufgaben mathematische Kenntnisse mit Programmierfähigkeiten verknüpfen muss.
Nach der richtigen Lösung einer Aufgabe wird man für das Diskussionsforum zu dieser Aufgabe freigeschaltet. Es ist interessant, die dort aufgeführten Lösungen zu studieren. Zum Beispiel schreibt ein leicht frustrierter Basic-Programmierer, dass sein Computerprogramm 3 Stunden rechnen musste, um zur Lösung zu kommen. Nachdem ich das gelesen habe, war ich ganz stolz, dass mein Programm dafür nur eine halbe Sekunde benötigt hat. Aber danach liest man von dem C-Programm eines russischen Mathematikers, welches nur 14 Millisekunden benötigt. Die Russen scheinen dort insgesamt gut vertreten zu sein.
Momentan habe ich nach einer Woche (in der es Abends immer spät wurde) 40 Aufgaben gelöst. 300 Aufgaben warten noch auf mich. Ich hatte schon etwas Sorgen, dass ich irgendwann alle Aufgaben gelöst habe und mir langweilig wird. Diese Bedenken wurden aber schnell zersteut, als ich die Liste der Aufgaben mal nach dem Schwierigkeitsgrad sortiert habe. Auf Platz 83 steht die Entwicklung eines Computerprogramms, welches automatisch Sudokus löst. Die Funktionsfähigkeit dieses Programms muss man dadurch beweisen, dass man eine Sammlung von Sudoku-Aufgaben herunterlädt, diese automatisch vom Programm lösen läßt und dann eine Quersumme dieser Lösungen in das Lösungsformular eingibt.
