Blatt 2 - Universität Basel | Informatik

UNIVERSITÄT BASEL
Dozent
Prof. Dr. Thomas Vetter
Departement Informatik
Bernoullistrasse 16
CH 4056 Basel
Assistenten
Bernhard Egger
Andreas Forster
Tutoren
Jan Ebbe
Tatjana Frank
Cedric Geissmann
Sascha Scherrer
Alexander Stiemer
Webseite
http://informatik.unibas.ch/lehre/hs12/cs101/index.html
Grundlagen der Programmierung (CS101) - Blatt 2
Theorie [8 Punkte] - Praxis [15 Punkte]
Vorbesprechung
01. - 05. Okt
Abgabe (Theorie)
10. Okt (bis 12h00 im Briefkasten)
Abgabe (Praxis)
15. - 19. Okt (im Tutorat)
Zusätzliche Aufgaben
Da die Vorlesung in der Woche vom 8.-12. Oktober leider ausfallen muss, wurden diesem Aufgabenblatt zusätzliche Aufgaben hinzugefügt. Die Aufgaben sollen in erster Linie die Programmierroutine fördern und so spätere Aufgabenblätter vereinfachen.
Aufgabe 1: Schleifen schleifen Studenten (Theorie)
[4 Punkte]
In den vier Teilaufgaben ist jeweils eine Problembeschreibung als Text und eine in Java
implementierte Schleife die dieses Problem löst gegeben. Die Implementierungen enthalten
allerdings Fehler.
(i) Finden und korrigieren Sie den Fehler in jeder der Teilaufgaben ohne eine andere
Schleifenart zu verwenden.
(ii) Lösen Sie die Aufgabenstellung mit einer anderen Schleifenart so, dass die Ausgabe
in Ihrem neuen Code identisch ist zu der Ausgabe in der korrigierten Version des
Codes.
(a) Berechne die Anzahl signikanter Stellen einer Zahl vor dem Punkt.
1
2
3
4
5
6
7
8
9
double zahl;
...
for(int stellen=0; stellen<6; ++stellen) {
if (zahl*zahl < 1) {
System.out.println("Die Zahl hat " + stellen + " Stellen");
break;
}
zahl /= 10;
}
(b) Ganzzahlige Division: Dividiere den Dividend durch den Divisor mit Rest.
1
2
3
4
5
6
7
8
int dividend;
int divisor;
...
int ergebnis = 0;
int rest = dividend;
if ( divisor < rest ) {
do {
ergebnis++;
Grundlagen der Programmierung
9
10
11
12
Blatt 2
Seite 2 / 5
rest -= divisor;
} while (divisor < rest);
}
System.out.println(dividend+" geteilt durch "+divisor+" gibt "+ergebnis+" Rest "+rest);
(c) Addiere 5 zu einer Zahl, ist die Zahl dann nicht grösser als 20 wiederhole die Schritte.
1
2
3
4
5
6
7
double zahl;
...
int zaehler = 0;
while (zahl<20 || zaehler!=1) {
zahl += 5; ++zaehler;
}
System.out.println("Der erreichte Wert ist: " + zahl);
(d) Gib für jede Zahl von 1 bis 100 die Summe der Zahlen von 1 bis zu der jeweiligen
Zahl aus.
1
2
3
4
5
6
7
8
9
10
11
12
int summe;
...
int max_zahl = 0;
int zahl = 0;
while(max_zahl<100) {
summe = 0;
while(zahl<max_zahl) {
summe += zahl++;
}
++max_zahl;
System.out.println("Die Summe von 1 bis " + max_zahl + " ist: " + summe);
}
Aufgabe 2: Grammatiken (Theorie)
[4 Punkte]
Geben Sie alle Symbolfolgen an die sich mit Hilfe der folgenden Grammatiken erzeugen
lassen. Ordnen Sie die Symbolfolgen der Länge nach. Sortieren Sie dabei zusätzlich Symbolfolgen gleicher Länge lexikographisch. Im Falle unendlicher Symbolfolgen reicht es die
ersten zehn Symbolfolgen anzugeben.
(a) Terminalsymbole: x, y und z.
G1 = [x](y|z)[x|z]z
(b) Terminalsymbole: a, b und d.
G2 = b{a|G2}d
(c) Terminalsymbole: a, b, c und d.
G3 = a{bb{b}|c|[d]}a
(d) Geben Sie für (c) ein Syntaxdiagramm an.
Grundlagen der Programmierung
Blatt 2
Aufgabe 3: Zahlenschloss knacken (Praxis)
Seite 3 / 5
[1 Punkte]
Die einfachste Strategie ein Zahlenschloss zu knacken heisst Brute-Force (Rohe Gewalt).
Dabei werden alle möglichen Lösungen ausprobiert um das korrekte Passwort zu nden.
Laden Sie die Sourcen zu diesem Aufgabenblatt von der Übungswebseite herunter. Die
Datei Crack.java im Wurzelverzeichniss können Sie als Vorlage für diese Aufgabe verwenden. Die Dateien unter /ch/unibas/informatik/cs101 werden für das funktionieren des Programms benötigt. Um das Programm zu kompilieren, geben Sie folgendes
auf einer Kommandozeile (im Wurzelverzeichniss) ein:
javac Crack.java
Das Program kann dann mit
java Crack
ausgeführt werden.
Auf der Ausgabe sollte false erscheinen, da 1234 nicht die richtige Kombination ist.
Die Methode checkPasscode() gibt für einen Integer zurück ob es sich dabei um ein gültigen
Code handelt (Boolean).
Finden Sie mit Hilfe einer Schleife die gültige Zahlenkombination!
Aufgabe 4: Domino (Praxis)
[2 Punkte]
Schreiben Sie ein Programm, dass alle möglichen Domino-Spielsteine ausgibt, verwenden
Sie dazu zwei geschachtelte Schleifen. Zählen sie jeweils die Anzahl möglicher Steine.
(0|0), (0|1), ..., (1|6), ..., (6|6)
(a) Es dürfen doppelte Steine vorkommen wie z.B. (1|6) und (6|1).
(b) Es dürfen keine doppelte Steine vorkommen (mit Schleifen lösbar).
Aufgabe 5: Zeichnen 1 (Praxis)
[1 Punkt]
[1 Punkt]
[4 Punkte]
In dieser Aufgabe sollen Sie einfache Muster in ein Fenster zeichnen. Verwenden sie wieder
die Sourcen von der Übungswebseite. Die Datei BasicDrawing.java im Wurzelverzeichniss können Sie als Vorlage für die Programme in dieser Aufgabe verwenden. Es sollte
sich ein Fenster mit einem einsamen roten Pixel auf dem weissen Hintergrund önen. Das
Programm läuft weiter solange das Fenster nicht geschlossen wird.
(a) Schreiben Sie ein Programm welches eine horizontale und vertikale Linie über das
ganze Bild zeichnet. Verwenden Sie dafür eine Schleife.
[ 12 Punkt]
(b) Schreiben Sie ein Programm welches ein gefülltes Rechteck zeichnet. Verwenden Sie
dafür zwei geschachtelte Schleifen.
[ 21 Punkt]
Grundlagen der Programmierung
Blatt 2
Seite 4 / 5
(c) Schreiben Sie ein Programm welches ein Schachbrettmuster über das ganze Bild
zeichnet. Die Kantenlänge jedes Feldes soll 20 Pixel betragen. Verwenden Sie zwei
ineinander geschachtelte Schleifen über die Zeilen und Spalten des Bildes, und eine
Bedingung die an jedem Pixel testet, ob dieser Schwarz oder Weiss gezeichnet werden
soll.
Hinweis: Verwenden Sie für die Bedingung die Modulo Operation %.
[1 Punkt]
(d) Zeichnen Sie einen gefüllten Kreis um den Nullpunkt des Bildes. Für jeden Punkt
auf einem Kreis um den Nullpunkt gilt
r 2 = x2 + y 2
(1)
wobei r der Radius des Kreises ist und x, y die Koordinaten eines Punktes auf
dem Kreis sind. Überlegen Sie, welche Bedingung im Inneren eines Kreises gilt,
und markieren Sie alle Pixel die diese Bedingung erfüllen.
[1 Punkt]
(e) Verschieben Sie den Kreis in die Mitte des Bildes.
[1 Punkt]
Aufgabe 6: Iterationsverfahren nach Newton (Praxis)
[4 Punkte]
Die Kubikwurzel einer positiven reellen Zahl a lässt sich näherungsweise durch die Iterationsformel bestimmen:
1
a
xn+1 = (2xn + 2 )
3
xn
(2)
Diese Formel wird wie folgt angewandt. Man wählt einen beliebigen Startwert x1 , und
berechnet mit der Formel den Wert x2 , indem xn = x1 und xn+1 = x2 gewählt werden.
Das Ergebnis wird dann immer wieder (iterativ) in die Formel hineingesteckt. Die Formel
ist so konstruiert, dass die Lösung immer dichter an der Kubikwurzel von a liegt, als der
Eingabewert. Die Formel ergibt sich aus dem Iterationsverfahren nach Newton. Um die
Nullstelle einer Funktion f zu nden, nutzt man die allgemeine Iterationsvorschrift:
xn+1 = xn −
f (xn )
f 0 (xn )
(3)
In unserem Fall ist f (x) = x3 − a.
Schreiben Sie ein JAVA-Programm CubicRoot, das die Kubikwurzel der Eingabe berechnet. Dabei gilt ein Iterationswert als gut genug, falls er von dem nachfolgendem Iterationswert nicht um mehr als 1e − 8 abweicht. Hinweise:
• Deklarieren Sie die Variablen als Typ double.
• Weisen Sie zur Verarbeitung der Eingabe a den Wert Double.parseDouble(args[0])
zu.
• Starten Sie mit dem Iterationswert 1.
• Nutzen Sie zur Berechnung des Absolutbetrags einer Zahl x die Funktion Math.abs(x).
Grundlagen der Programmierung
Blatt 2
Aufgabe 7: Flugsimulator (Praxis)
Seite 5 / 5
[4 Punkte]
Für ein Computerspiel (Flugsimulator) soll die Höhe eines landenden Flugzeuges vereinfacht berechnet werden:
Das Flugzeug iegt im Landeanug exakt mit einer Horizontalgeschwindigkeit von vx = 20
Pixel pro Zeiteinheit. Mit jeder t Zeiteinheit verändern sich die Sinkgeschwindigkeit vy
und die Höhe h nach den folgenden Regeln:
vyt+1 = vyt − 3
(4)
ht+1 = ht − v
(5)
Das Flugzeug soll in einer Höhe von h0 = 456 Pixel den Anug beginnen und einer
Sinkgeschwindigkeit vy0 = 51 Pixel pro Zeiteinheit.
(a)
(b)
(c)
(d)
Geben Sie für jede Zeiteinheit vy und h aus.
[1 Punkt]
Wie viele Zeiteinheiten vergehen bis zur Landung (h <= 0)?
[ 21 Punkt]
Wie gross ist vy bei der Landung?
[ 21 Punkt]
Verwenden Sie erneut die Sourcen BasicDrawing.java als Vorlage und visualisieren Sie den Landeanug durch einzele Punkte für pro Zeiteinheit. Zeichnen sie
dazu die Höhe über die Zeit, d.h. x-Achse Zeit (bzw. horizontale Position) und yAchse Höhe.
[2
Punkt]