Aufgabe 3: Rekursion/Iteration

Die catalanschen Zahlen treten in vielen Problemen in der Kombinatorik auf (zum Beispiel zum Abzählen von verschiedenen Auswahlöglichkeiten, siehe: https://de.wikipedia.org/wiki/Catalan-Zahl). Die Zahlen sind eine Folge von natürlichen Zahlen, die sich rekursiv wie folgt berechnen lassen:

Cn+1 = Cn (4n+2)/(n+2), C0=1

1. Schreiben Sie ein Unterprogramm catalan_number_rec(n), das Cn rein rekursiv (also ohne Verwendung von Schleifen) berechnet und zurück gibt.

2. Schreiben Sie ein Unterprogramm catalan_number_it(n), das Cn iterativ berechnet und zurück gibt. Erklären Sie kurz die Vorteile der iterativen Version.

Scaffold Head: import sys # suppress users print and input commands _print = print _input = input print = lambda msg, *args, **kwargs: _print('#'+str(msg), *args, **kwargs) def input(message): print("input-command suppressed for", message) return 1
Scaffold Foot: print = _print input = _input nums = [int(next(sys.stdin)) for i in range(5)] #1 for n in nums: print(int(catalan_number_rec(n))) #2 for n in nums: print(int(catalan_number_it(n)))

Start time:: Fr 08 Dez 2017 15:15:07
End time:: Do 14 Dez 2017 14:00:13

General test timeout:: 10.0 seconds

Tests

Comment prefix	`#`
Given input	10 12 22 13 1
Expected output	16796 208012 91482563640 742900 1 16796 208012 91482563640 742900 1

Aufgabe 3: Rekursion/Iteration Assignment

Tests