close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

3. Übungsblatt - G-CSC Home - Goethe-Universität

EinbettenHerunterladen
Goethe-Center for Scientific Computing (G-CSC)
Goethe-Universit¨at Frankfurt am Main
Einfu
¨ hrung in die Programmierung (EPR)
¨
(Ubung,
Wintersemester 2014/2015)
S. Reiter, M. Rupp, Dr. A. Vogel, Dr. K. Xylouris, Prof. Dr. G. Wittum
Aufgabenblatt 3 (Abgabe: Fr., 14.11., 9:29h online)
¨
F¨
ur dieses Ubungsblatt
soll erneut ausschließlich funktionale Programmierung verwendet werden. Es stehen Ihnen folglich die Programmiermittel zur
Verf¨
ugung, so wie sie in der Vorlesung bis Kap. 2 behandelt worden sind.
Bei funktionaler Programmierung besteht eine Funktion nur aus Ausdr¨
ucken.
Sie d¨
urfen zudem if-Verzweigung und die Notation (cond)?op1:op2 (siehe
¨
vorheriges Ubungsblatt)
verwenden.
Nicht erlaubt hingegen sind Zuweisungen an Variablen oder Schleifen (wie
for oder while). Sollten Sie solche C++-Konstrukte bereits kennen, so warten
Sie bitte mit der Verwendung, bis diese in der Vorlesung eingef¨
uhrt wurden.
Aufgabe 1 (5 Punkte, Multiplikation)
Bei der Berechnung von Potenzen kann man sich einige Multiplikationen
sparen. Zum Beispiel kann man
x8 = x · x · x · x · x · x · x · x
in die folgenden Schritte zerlegen
x2 = x · x,
x4 = x2 · x2 ,
x8 = x4 · x4 ,
und ben¨otigt dann nur 3 statt 7 Multiplikationen. Allgemein l¨asst sich dies
folgendermaßen rekursiv ausdr¨
ucken:
 n

x 2

n
· x2,
falls n gerade,
n
(n−1)
x = x·x
, falls n ungerade,



x,
falls n = 1.
Schreiben Sie eine Funktion
double Potenz(double x, int exp),
die auf diese Weise schnell Potenzen mit exp ≥ 1 berechnet. Benutzen Sie
dazu auch die in der Vorlesung vorgestellte Funktion Quadrat, die zu einer
double-Zahl dessen Quadrat zur¨
uckliefert.
Aufgabe 2 (15 Punkte, Wechselgeld)
Sie m¨
ussen ein Wechselgeld von w Cent herausgeben. Dazu stehen Ihnen die
n = 6 M¨
unzarten von 1, 2, 5, 10, 20 und 50 Cent zur Verf¨
ugung. Sie fragen
sich, wie viele M¨oglichkeiten es gibt, den Betrag von w Cent herauszugeben,
wenn die Reihenfolge der M¨
unzen nicht beachtet wird. Zum Beispiel gibt es
f¨
ur die Herausgabe von 5 ct die 4 M¨oglichkeiten
1 × 5ct,
2 × 2ct + 1 × 1ct,
1 × 2ct + 3 × 1ct,
5 × 1ct.
Schreiben Sie eine Funktion
int ChangeOptions(int value),
die zu gegebenem Wechselgeldwert die Anzahl der M¨oglichkeiten der M¨
unzaufteilung zur¨
uckgibt und testen Sie diese f¨
ur w = 500.
Hinweis: Diese Aufgabe l¨asst sich sehr gut mit einer Rekursion l¨osen. Dazu u
¨berlegt man sich Folgendes: Man hat einen Betrag von w Cent und n
unzen zur Verf¨
ugung. Sei d der h¨ochste Nennwert unter den n M¨
unzen.
M¨
Nun gibt es zwei M¨oglichkeiten:
(i) Man verwendet eine M¨
unze mit Wert d. Dann bleibt noch der Rest
w − d aufzuteilen mit weiterhin m¨oglichen n M¨
unzarten.
(ii) Man verwendet die M¨
unze mit Wert d nicht. Dann muss der Betrag w
mit den n − 1 kleineren M¨
unzarten zerlegt werden.
Sei A(w, n) die Anzahl den Betrag w mit n M¨
unzarten aufzuteilen. Nun kann
man sich gut u
¨berlegen, wie die obigen F¨alle die Rekursion bilden. Zudem
u
¨berlege man sich die Extremf¨alle w = 0, w > 0 und n = 0, und w < 0.
Aufgabe 3 (10 Punkte, Zahlen im Bin¨arsystem)
Jede nat¨
urliche Zahl n ∈ N l¨asst sich im Bin¨arsystem schreiben, d.h. die Zahl
wird in der Darstellung
m
ai 2i ,
n=
i=0
ai ∈ {0, 1},
geschrieben. F¨
ur eine kompakte Notation bieten sich zwei Schreibweisen an:
(a0 a1 . . . am )2 , (Little-Endian),
(am am−1 . . . a0 )2 , (Big-Endian).
Die Darstellungen unterscheiden sich dadurch, ob der signifikanteste Koeffizient am oder der kleinstwertige Koeffizient a0 an der ersten Stelle steht. (Die
gebr¨auchliche Dezimalnotation ist in diesem Sinne eine Big-Endian Schreibweise zur Basis 10.)
¨
Uberlegen
Sie sich, wie man ausgehend von einer Zahl in Dezimaldarstellung
die Darstellung im Bin¨arsystem gewinnen kann. Schreiben Sie dann ein Programm, das zu einer nat¨
urlichen Zahl n die zugeh¨origen Bin¨ardarstellung auf
dem Bildschirm ausgibt. Dabei soll die Bin¨ardarstellung im Little-EndianFormat ausgegeben werden. Testen Sie Ihr Programm f¨
ur n = 10, 16 und
25.
Beispiele f¨
ur Umrechnungen:
(10)10 → (0101)2 ,
(16)10 → (00001)2 ,
(25)10 → (10011)2 .
Tipp: Beachten Sie, dass bei Integerdivision in C++ die potenziellen Nachkommastellen verworfen werden – das Ergebnis wir also stets auf den n¨achsten
Integer abgerundet, falls die Integerdivision nicht exakt aufgeht. Zudem wird
Ihnen der Operator % hilfreich sein. Durch diesen Operator lassen sich in C++
Modulo-Operationen berechnen, d.h. der Rest bei Ganzzahldivision.
5 % 2; // Wertet aus zu 1, denn 5 / 2 = 2 Rest 1
5 / 2; // Wertet aus zu 2, denn 5 / 2 = 2.5, gerundet 2
6 % 2; // Wertet aus zu 0, denn 6 / 2 = 3 Rest 0
6 / 2; // Wertet aus zu 3, denn 6 / 2 = 3,
gerundet 3
Aufgabe 4 (10 Bonuspunkte, T¨
urme von Hanoi)
Die T¨
urme von Hanoi sind ein bekanntes mathematisches R¨atsel. Es lautet
wie folgt:
Es gebe drei Positionen: Position 1, Position 2 und Position 3. Auf Position 1 seien n flache Steinscheiben u
¨bereinandergestapelt. Die Steine haben
alle einen anderen Durchmesser und sind nach ihrer Gr¨oße derart sortiert,
dass Steine mit gr¨oßerem Durchmesser unten liegen. Die anderen beiden Positionen sind zun¨achst leer. Die Aufgabe ist es nun, alle Steine von Position
1 nach Position 3 zu bewegen. Dabei darf jedoch in jedem Zug immer nur
ein Stein bewegt werden und zu jeder Zeit muss die Gr¨oßenreihenfolge eingehalten werden – d.h. nur kleinere Steine d¨
urfen auf gr¨oßeren Steinen liegen.
Schreiben Sie ein Programm, das Anweisungen ausgibt, um die n Steine
von Position 1 nach Position 3 unter Ber¨
ucksichtigung der obigen Regeln zu
bef¨ordern. F¨
ur n = 3 w¨
urde die Ausgabe folgendermaßen aussehen:
Bewege
Bewege
Bewege
Bewege
Bewege
Bewege
Bewege
obersten
obersten
obersten
obersten
obersten
obersten
obersten
Stein
Stein
Stein
Stein
Stein
Stein
Stein
von
von
von
von
von
von
von
Position
Position
Position
Position
Position
Position
Position
1
1
3
1
2
2
1
nach
nach
nach
nach
nach
nach
nach
Position
Position
Position
Position
Position
Position
Position
3
2
2
3
1
3
3
Information zur Abgabe: Bitte schicken Sie Ihre L¨osung als *.cpp Datei
¨
an Ihren Ubungsgruppenleiter
per Mail. Wichtig ist, dass Sie Ihre L¨osung
freitags vor 9:30h abgeschickt haben. Bitte schicken Sie nur den Quellcode,
nicht jedoch ihr gesamtes Eclipse-Projekt oder ausf¨
uhrbare Dateien.
Information zu Bonuspunkten: Wenn Sie die Bonusaufgabe nicht bearbeiten, jedoch ansonsten alles richtig haben, erreichen Sie 100% der m¨oglichen
Punkte. Die Bonuspunkte dienen dazu, dass Sie verpasste Punkte ausgleichen
k¨onnen.
Document
Kategorie
Internet
Seitenansichten
27
Dateigröße
166 KB
Tags
1/--Seiten
melden