close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Grundlagen der Programmierung 1 (PRG-1) - G-CSC Home

EinbettenHerunterladen
Goethe-Center for Scientific Computing (G-CSC)
Goethe-Universit¨at Frankfurt am Main
Grundlagen der Programmierung 1 (PRG-1)
¨
(Ubung,
Wintersemester 2014/2015)
S. Reiter, M. Rupp, Dr. A. Vogel, Dr. K. Xylouris, Prof. Dr. G. Wittum
Aufgabenblatt 2 (Abgabe: Mo., 10.11., 12h)
Aufgabe 1 (10 Punkte, EBNF f¨
ur algebraische Gleichungen)
Eine algebraische Gleichung u
urlichen Zahlen ist eine Gleichung
¨ber den nat¨
der Form
n
ai xi = an xn + . . . + a1 x + a0 = 0,
i=0
wobei n ≥ 0 frei w¨ahlbar ist und die Koeffizienten ai ∈ N nat¨
urliche Zahlen
sind. Der Einfachheit halber sollen diese Gleichungen so geschrieben werden,
dass die Potenzen durch Multiplikation dargestellt werden, d.h. x2 = x ∗ x
etc., und dass in der Summe auch mehrfach dieselben Potenzen zugelassen
sind. In der Schreibweise sollen jedoch die x Zeichen in jedem Summand
immer rechts von den Koeffizienten stehen und zudem keine Leerzeichen vorkommen. Beispiele von algebraischen Gleichungen sind dann:
2*x*x*x+67*x*x+122*x+19=0
45*x*x*x*x+30*x*x*x*x=0
45*x+30*x*x=0
3=0
x=0
Verwenden Sie die erweiterte Backus-Naur-Form (EBNF), um die Regeln f¨
ur
eine korrekt geschriebene obige Gleichung zu definieren. (<Gleichung> ::= ...).
Aufgabe 2 (10 Punkte, LEO’)
Sei analog zur Sprache LEO aus der Vorlesung die leicht unterschiedliche
Sprache LEO’ gegeben, die nur die folgenden drei Regeln besitzt:
(i) LE ist ein g¨
ultiges Wort der Sprache.
(ii) Wenn xE ein g¨
ultiges Wort ist, dann auch xEO.
(iii) Wenn Lx ein g¨
ultiges Wort ist, dann auch Lxx.
Beweisen Sie mit vollst¨andiger Induktion, dass das Wort LO nicht Teil der
Sprache LEO’ ist.
Aufgabe 3 (10 Punkte, Fibonacci-Zahlen)
Die Fibonacci-Zahlen sind eine rekursiv definiert Folge von positiven, ganzen
Zahlen. Bezeichne fib: N → N die Funktion, die die n-te Fibonnaci-Zahl
angibt, so ist f¨
ur n ∈ N diese Funktion definiert durch:



0,
n = 0,
fib(n) := 1,
n = 1,


fib(n − 1) + fib(n − 2), n ≥ 2.
Beweisen Sie mit vollst¨andiger Induktion, dass diese Definition der FibonacciZahlen f¨
ur jedes n ≥ 0 terminiert.
¨
Hinweis: Die Abgabe der schriftlichen Ubungszettel
erfolgt vor der
Vorlesung. Bitte schreiben Sie auf die L¨osung Ihren Namen und die
¨
Ubungsgruppe.
Heften Sie gegebenenfalls mehrere Zettel zusammen.
Document
Kategorie
Technik
Seitenansichten
10
Dateigröße
131 KB
Tags
1/--Seiten
melden