Mittel 0 gelöst 0% Erfolgsquote

Catalan-Zahlen

Gib die Catalan-Zahlen C(0) bis C(n) aus.

Das lernst du

  • Eine Folge aus früheren Werten aufbauen
  • Eine Rekursionsformel aus einer Summe von Produkten anwenden
  • Überläufe in Zwischenergebnissen vermeiden

Problem

Die Catalan-Zahlen 1, 1, 2, 5, 14, 42, … zählen viele verschiedene Dinge: korrekte Klammerausdrücke aus n Klammerpaaren, Binärbäume mit n Knoten und die Möglichkeiten, ein konvexes Vieleck in Dreiecke zu zerlegen. Sie beginnen mit C(0) = 1 und erfüllen C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).

Implementiere catalan_numbers(n).

Eingabe

n: Der Index der letzten Catalan-Zahl, die in der Liste stehen soll.

Ausgabe

Gib die Liste [C(0), C(1), …, C(n)] mit n + 1 Werten zurück. C(35) ist die größte, die in eine vorzeichenbehaftete 64-Bit-Ganzzahl passt. Achte also auf Überläufe in den Zwischenschritten.

Einschränkungen

0 ≤ n ≤ 35

Beispiele

Beispiel 1
Eingabe:
n = 4

Erwartete Ausgabe:
expected = [1, 1, 2, 5, 14]
Eingabe:
long long n = 4;

Erwartete Ausgabe:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Eingabe:
long n = 4;

Erwartete Ausgabe:
long[] expected = new long[] {1, 1, 2, 5, 14};

Erläuterung

C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, also lautet die Liste [1, 1, 2, 5, 14].

Beispiel 2
Eingabe:
n = 0

Erwartete Ausgabe:
expected = [1]
Eingabe:
long long n = 0;

Erwartete Ausgabe:
std::vector<long long> expected = {1};
Eingabe:
long n = 0;

Erwartete Ausgabe:
long[] expected = new long[] {1};

Erläuterung

Gefragt ist nur C(0) = 1: [1].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Speichere die Werte beim Berechnen in einer Liste.

Hinweis 2

C(k + 1) ist eine Summe über i von C(i) × C(k − i).

Hinweis 3

Jedes Produkt in dieser Summe ist höchstens so groß wie der Endwert, innerhalb der Grenzen gibt es mit der Summenformel also keinen Überlauf.

Erwartete Komplexität

Zeit O(n^2), zusätzlicher Speicher O(n)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.