Primitive Rekursion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeigen Sie, dass das Prädikat P = {n [mm] \in \IN [/mm] | n ist gerade} primitiv rekursiv ist. Geben Sie dazu eine primitiv rekursive Darstellung der charakteristischen Funktion [mm] X_p(n)=\begin{cases} 0, & \mbox{falls } n \mbox{ sonst} \\ 1, & \mbox{falls n gerade} \end{cases} [/mm] |
Ich glaubte zuerst eine primiiv rekursive Darstellung zu haben. Leider darf bei der primitiven Rekursivität nur ein Basisfall angegeben werden.
Ich habe noch Probleme damit, auseinanderzuhalten, was ein Basisfall ist.
Ich schreibe einfach mal meinen jetzigen Lösungsansatz auf:
[mm] X_p(n)=X_p(sub(n,2))
[/mm]
[mm] X_p(1)=1-X_p(0)
[/mm]
[mm] X_p(0)=1
[/mm]
Erklärung. Ein gegebenes n führe ich zunächst auf die Berechnung von [mm] X_p(n-2) [/mm] zurück bzw. sage, dass hier Gleichheit herrscht. Wenn n ungerade ist, dann wird es irgendwann 1. Also wird [mm] X_p(1) [/mm] aufgerufen und dann [mm] X_p(0). [/mm] Da das 1 ist, kommt 0 heraus.
Frage: Sind dies nun zwei Basisfälle?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:21 Do 03.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
