Wie entwerfe ich Algorithmen in Java?

Worum geht´s?

In diesem Java Tutorial soll der Frage nachgegangen werden, wie wir am einfachsten geeignete Algorithmen für komplexe Probleme finden.

Als Ausgangspunkt nehmen wir dafür ein klassisches Programmier-Problem: Wir wollen überprüfen, ob eine Zahl n eine Primzahl ist.

1. Frage 1: Was ist überhaupt eine Primzahl?

Wer es nicht weiß:

Eine Primzahl ist eine Zahl, die nur durch sich selbst und durch 1 teilbar ist.

Das „teilbar“ bedeutet in diesem Fall, dass bei der Division eine ganzzahlige Zahl rauskommt, also die Division ohne Rest möglich ist.

Was uns gleich zu einem kleinen Teil der Lösung führt:

Den Rest einer Division berechnen wir mit dem Modulo-Operator (%).

Ist die Zahl n durch 3 ohne Rest teilbar, so muss n%3 == 0 sein.

2. Versuch 1: Ein grober Algorithmus

Wir wissen also jetzt, dass wir überprüfen müssen, ob n ohne Rest durch diverse Zahlen teilbar ist.

Aber woher wissen wir, welche Zahlen das sind?

Die erste Zahl, von der wir sinnvollerweise ausgehen können ist 1 (weil die Division durch 0 undefiniert ist).

Die letzte Zahl, die wir überprüfen könnten, ist n selbst (alles darüber würde eine Division mit Rest ergeben).

Nehmen wir also einmal an, wir überprüfen alle Zahlen x von 1 bis n, ob n%x == 0.

Dazu werden wir eine Schleife brauchen.

2.1 Ein erster Prototyp

Das Bringt uns in etwa zu folgendem Pseudo-Code:

Überprüfe alle Zahlen von 1-n mit Hilfe der Zahl x
Ob n%x == 0
Wenn ja, dann …

Ja, was dann eigentlich?

Was soll passieren, wenn eine Zahl teilbar ist?

Wir könnten zählen, wie oft wir eine teilbare Zahl finden.

Also nochmal:

Überprüfe alle Zahlen von 1-n mit Hilfe der Zahl x
Ob n%x == 0
Wenn ja, dann erhöhe counter
Wenn am Ende counter > 2
Dann keine Primzahl
Sonst schon

Das… könnte funktionieren.

2.2 Schreibtischtest!

Wir probieren unsere Lösung mit den Zahlen 3, 8, 9, 11 (jeweils 2 Primzahlen und 2 nicht-Primzahlen, um sicher zu gehen).

• n = 3 führt zu counter = 2, also PRIMZAHL
• n = 8 führt zu counter = 4, also KEINE primzahl
• n = 9 führt zu counter = 3, also KEINE primzahl
• n = 11 führt zu counter = 2, also PRIMZAHL

Scheint zu funktionieren.

Aber können wir das noch irgendwie optimieren?

2.3 Optimieren am Papier

Irgendwie sind es jetzt in jedem Fall mindestens counter = 2, auch wenn es eine Primzahl ist.

Was, wenn wir die Zahl 1 und die Zahl n selbst ausschließen?

Dann hätten wir entweder counter = 0 oder counter > 0, um die Primzahl zu bestimmen.

Vor allem aber könnten wir dann immer dort, wo counter mehr als 0 wird, mit unserer Schleife aufhören.

Eigentlich bräuchten wir auch gar keinen counter mehr… z.B. so:

Setze prim auf true
Überprüfe alle Zahlen von 2 bis (n – 1) mit Hilfe der Zahl x
     Ob n%x == 0
    Wenn ja dann keine Primzahl, beende die Schleife und setze prim auf false
Am Ende: Falls prim==true, dann Primzahl

Hmm, schon viel besser.

2.4 Ausprobieren in IntelliJ

In IntelliJ könnte das ganze dann folgender Java-Code werden:

public class HelloWorld {
    public static void main(String[] args) {
        int n = 38; // zahl zum überprüfen obs Primzahl ist

        boolean prim = true; // ob es Primzahl ist, wir gehen von true aus
        for (int x = 2; x <= (n - 1) && prim; x++) {
            if (n % x == 0)
                prim = false;
        }

        if (prim)
            System.out.println("Ist Primzahl");
        else
            System.out.println("Ist keine Primzahl");
    }
}

3. Versuch 2: Der optimierte Algorithmus

Der Algorithmus oben funktioniert zwar schon, ist aber noch nicht sehr optimal.

Wer mathematisch etwas erfahren ist, kann sich ausrechnen, dass es gar nicht notwendig ist, bis hinauf zu n zu überprüfen, ob die Zahl teilbar ist – einfach, weil sich Teiler einer Zahl ja immer aus zwei Teilen zusammensetzen – es reicht die Hälfte.

Wer es noch mehr optimiert mag, kann statt der Hälfte der Zahl auch die Wurzel davon nehmen.

Je mehr es um Optimierung von Algorithmen geht, desto tiefer kommen wir meist in das Reich der Mathematik.

Ein schönes Reich übrigens – ist fast wie Puzzle bauen 🙂

So in etwa könnte man es angehen, einen Algorithmus zusammenzubauen.

Wir starten beim ganzen, komplexen Problem, und versuchen es in kleinere, schaffbare Teile runterzubrechen. Und diese lösen wir dann Schritt für Schritt – eben wie beim Puzzle bauen.

Viel Freude noch beim Puzzlen 😉

Diskussion zum Tutorial