• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Tribonacci-Folge

Contents

  • Tribonacci-Folge
    • Händische Lösung
    • Rekursive Lösung
    • Bottom-Up Ansatz
    • Fill it
    • Wertetabelle
    • Java

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 :=

\begin{cases} 1 &\text{, falls } n \in \{0,1,2\}\\ a_{n-1} + a_{n-2} + a_{n-3} & \text{, falls } n \geq 3 \end{cases}
\).

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

ia_i
01
11
21
33
45
59
617
731
857
9105
10193
11355
12653
131201
142209
154063
167473
1713745
1825281
1946499
2085525
21157305
22289329
23532159
24978793
251800281
263311233
276090307
2811201821
2920603361
3037895489
3169700671
32128199521
33235795681
34433695873
35797691075
361467182629
372698569577
384963443281
399129195487
4016791208345

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));
    }

}

Published

Nov 19, 2012
by Martin Thoma

Category

Code

Tags

  • Java 36
  • Programming 52

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor