Vorlesung 11 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgabe S. 6 1.1 Add-Funktion in Python 1.2 Multipikationsfunktion in Python 1.3 Potenzfunktion in Python 2 Übungsaufgabe S. 16 2.1 Wiederholte Nachfolgerbildung - primitiv rekursiv? 3 Übungsaufgabe S. 32 3.1 Memoizingtabelle der AP-Funktion 4 Übungsaufgabe S. 45 4.1 Polynome mit natürlichen Koeffizienten primitiv rekursiv?

Übungsaufgabe S. 6

Add-Funktion in Python

def S(x): return x + 1 def add(x, n): if x == 0: return n else: return S(add(x-1, n)) def add_loop(x, n): for i in range(n): x = S(x) return x

print(add(130, 15)) print(add_loop(130, 15))

ausführen

Multipikationsfunktion in Python

def mult(x, n): if x == 0: return 0 else: return add(mult(x-1, n), n) def mult_loop(x, n): res = 0 for i in range(n): res = add(res, x) return res

print(mult(3, 4)) print(mult_loop(3, 4))

ausführen

Potenzfunktion in Python

def pot(exp, base): if exp == 0: return 1 else: return mult(pot(exp-1, base), base) def pot_loop(exp, base): res = 1 for i in range(exp): res = mult(res, base) return res

print(pot(3, 4)) print(pot_loop(3, 4))

ausführen

Übungsaufgabe S. 16

Wiederholte Nachfolgerbildung - primitiv rekursiv?

Übungsaufgabe S. 32

Memoizingtabelle der AP-Funktion

Übungsaufgabe S. 45

Polynome mit natürlichen Koeffizienten primitiv rekursiv?

Polynome mit natürlichen Koeffizienten sind primitiv rekursiv, weil sie sich aus den bereits bekannten primitiv rekursiven Funktionen, Multiplikation, Addition, Potenz, Substraktion, zusammensetzen. Mithilfe der Aufbautechnik Substitution und den erwähnten Grundrechenarten kann man jedes dieser Polynome darstellen.