Tribonacci-Folge

Folgende Aufgabe gab es (sinngemäß) für das Modul „Programmieren“ im zweiten Übungsblatt 2012:

Sei \((a_n)_{n \in \mathbb{N}}\) eine Folge und definiert durch:

\(a_n :=

Ich werde im folgenden mal kurz mögliche Lösungen in Python (und eine in Java) vorstellen. Python hat bei solchen Aufgaben den Vorteil, dass es viel kompakter ist und Ganzzahlen beliebig groß werden können.

Händische Lösung

Bevor man irgendwas programmiert, sollte man sicherstellen, dass man es testen kann. Was wären also die ersten paar Folgenglieder?

\(a_0 = a_1 = a_2 = 1, a_3 = 3, a_4 = 5, a_5 = 9, a_6 = 17, a_7 = 31, a_8 = 57\)

Rekursive Lösung

Solche Aufgaben lassen sich häufig sehr einfach rekursiv lösen:

def tribonacci(n):
    if n < 3:
        return n
    else:
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

Allerdings hat diese rekursive Lösung den riesigen nachteil, dass viele Berechnungen redundant sind. Angenommen, wir wollen tribonacci(5) berechnen. Dann läuft folgendes ab:

1. Aufruf tribonacci(5)
   1. Aufruf tribonacci(4)
      1. Aufruf tribonacci(3)
         1. Aufruf tribonacci(2)
         2. Aufruf tribonacci(1)
         3. Aufruf tribonacci(0)
      2. Aufruf tribonacci(2)
      3. Aufruf tribonacci(1)
   2. Aufruf tribonacci(3)
      1. Aufruf tribonacci(2)
      2. Aufruf tribonacci(1)
      3. Aufruf tribonacci(0)
   3. Aufruf tribonacci(2)

Man sieht deutlich, dass z.B. tribonacci(3) mehrfach berechnet werden muss.

Wie kann man so was verbessern?

Bottom-Up Ansatz

Wir benötigen für ein neues Folgenglied immer nur das vorhergehende. Das kann dann so aussehen:

def tribonacciBottomUp(n):
    last = 1
    secondLast = 1
    thirdLast = 1
    for i in range(2, n):
        new = last + secondLast + thirdLast
        thirdLast = secondLast
        secondLast = last
        last = new
    return last

Fill it

Eine weitere Möglichkeit wäre die schwäche des rekursiven Ansatzes zu eliminieren, indem man alle bisher berechneten Werte in einem Array speichert.

Wertetabelle

Java

Java-Nutzer müssen sich darüber im klaren sein, dass alle Elemente, die größer als 36 sind, die int-Grenzen sprengen. Eine Lösung für das Übungsblatt könnte ungefähr so aussehen:

/** This class calculates numbers of the Tribonacci sequence. */
public final class Tribonacci {
    /**
     * Utility classes should not have a public or default
     * constructor.
     */
    private Tribonacci() {
    }

    /**
     * Calculate the n'th Element of the Tribonacci sequence (a_n).
     * The sequence is defined as:
     *   a_0 = a_1 = a_2 = a
     *   a_n = a_(n-1) + a_(n-2) + a_(n-3)
     *
     * @param n the element of the Tribonacci sequence you want to
     *          calculate
     * @return the value of the n'th element in the Tribonacci
     *         sequence
     */
    public static long calculateTribonacci(final long n) {
        long last = 1;
        long secondLast = 1;
        long thirdLast = 1;

        for (int i = 2; i < n; i++) {
            long newTri = last + secondLast + thirdLast;
            thirdLast = secondLast;
            secondLast = last;
            last = newTri;
        }
        return last;
    }

    /**
     * Prints out the Tribonacci number a_36
     * the (37th Tribonacci number)
     * @param args the command line arguments
     */
    public static void main(final String[] args) {
        System.out.println(calculateTribonacci(36));
    }

}