Fallstudie 3: Bedingungen und Rekursion¶
Patrick Schnider, Marcel LüthiDepartement Mathematik und Informatik, Universität Basel
Boolsche Ausdrücke¶
Wenn wir Situationen in der Programmierung beschreiben, haben wir es oft mit relativ komplexen Boolschen Ausdrücken zu tun. Wir müssen lernen diese zu lesen, verstehen und, wo möglich, zu vereinfachen.
Ein Beispiel, welches zu einem komplexen boolschen Ausdruck führt ist, wenn wir die Punkte in der folgenden farbigen Fläche charakterisieren möchten
class BooleanExpression {
public static boolean isInside(double x, double y) {
// Schreiben Sie hier Ihre Methode
return true;
}
public static void main(String[] args) {
// Testen Sie hier Ihre Methode
}
}
BooleanExpression.main(new String[0]);
Miniübung¶
- Schreiben Sie die Methode
isInsideso um, dass diesetruezurück gibt, wenn die durchxundygegebene Koordinate innerhalb der farbigen Fläche liegt. - Testen Sie die Methode
isInsidemit verschiedenen Werten
Boolsche Algebra¶
Um komplexe boolsche Ausdrücke zu verwenden, können wir die Regeln von De-Morgan verwenden:
!(A && B) ist gleich !A || !B
!(A || B) ist gleich !A && !B
Miniübung¶
- Schreiben Sie ein Programm, welches diese Regeln überprüft.
class BooleanTest {
public static void main(String[] args) {
// Schreiben Sie hier Ihren Code
}
}
BooleanTest.main(new String[0]);
Bindung von Operatoren¶
Bei der Arithmetik kennen wir die Punkt vor Strich-Regel. Gilt so eine Regel auch bei ||, && und !? Experimentieren Sie
class OperationOrder {
public static void main(String[] args) {
// Schreiben Sie hier Ihren Code
}
}
OperationOrder.main(new String[0]);
Hochhäuser zeichnen¶
Wir kommen nun zurück auf unsere Zeichnungsaufgabe vom letzten Mal. Dazu laden wir zuerst wieder die Turtle Bibliothek.
%mavenRepo shapemodelling-repo https://shapemodelling.cs.unibas.ch/repo/
%maven ch.unibas.informatik:jturtle:0.7
import static ch.unibas.informatik.jturtle.TurtleCommands.*;
import java.awt.Color;
Der Folgende Code zeichnet ein vier-stöckiges Hochhaus.
class Building {
public static void drawRectangle(double xPos,
double yPos,
double width,
double height) {
reset(); // set turtle to origin and make it face upwards
penUp();
goTo(xPos, yPos);
penDown();
forward(height);
turnRight(90);
forward(width);
turnRight(90);
forward(height);
turnRight(90);
forward(width);
}
public static void drawFourStoreyBuilding(double xPos,
double yPos,
double width,
double height) {
double heightOfStorey = height / 4.0;
drawRectangle(xPos, yPos, width, heightOfStorey);
drawRectangle(xPos, yPos + heightOfStorey, width, heightOfStorey);
drawRectangle(xPos, yPos + 2 * heightOfStorey, width, heightOfStorey);
drawRectangle(xPos, yPos + 3 * heightOfStorey, width, heightOfStorey);
}
public static void main(String[] args) {
clear();
drawFourStoreyBuilding(0, 0, 30, 50);
display(drawing());
}
}
Building.main(new String[0]);
Mit if-Bedingungen können wir nun zwischen verschiedenen Hochhäusern unterscheiden, ohne dass wir jeweils eine komplett neue Methode schreiben müssen. Zum Beispiel können wir Hochhäuser mit und ohne Antenne auf dem Dach schreiben.
Miniübung¶
- Sie wollen nun zwei Arten von 4-stöckigen Häusern zeichnen, nämlich mit oder ohne Antenne. Dies wollen Sie beim Aufruf der Methode angeben können. Ergänzen Sie die Methode um ein Argument
hasAntenna. - Ergänzen Sie den Code so, dass, falls beim Aufruf gewünscht, eine Antenne gezeichnet wird (zum Beispiel durch einen weiteren Aufruf von drawRectangle).
class Building {
public static void drawRectangle(double xPos,
double yPos,
double width,
double height) {
reset(); // set turtle to origin and make it face upwards
penUp();
goTo(xPos, yPos);
penDown();
forward(height);
turnRight(90);
forward(width);
turnRight(90);
forward(height);
turnRight(90);
forward(width);
}
public static void drawFourStoreyBuilding(double xPos,
double yPos,
double width,
double height) {
double heightOfStorey = height / 4.0;
drawRectangle(xPos, yPos, width, heightOfStorey);
drawRectangle(xPos, yPos + heightOfStorey, width, heightOfStorey);
drawRectangle(xPos, yPos + 2 * heightOfStorey, width, heightOfStorey);
drawRectangle(xPos, yPos + 3 * heightOfStorey, width, heightOfStorey);
}
public static void main(String[] args) {
clear();
drawFourStoreyBuilding(0, 0, 30, 50);
display(drawing());
}
}
Building.main(new String[0]);
Wiederholungen durch Rekursion ausdrücken¶
Bisher hatten unsere Methoden eine grosse Einschränkung. Wir konnten immer nur Häuser mit einer fixen Anzahl Stockwerke zeichnen. Dank Rekursion können wir nun auch Methoden schreiben, bei denen man die Anzahl Stockwerke als Parameter angeben kann.
Die Strategie ist wie folgt:
- um ein $n$-stöckiges Gebäude zu zeichnen, zeichnen wir zuerst ein Rechteck und dann oben drauf ein $(n-1)$-stöckiges Gebäude.
- um ein $0$-stöckges Gebäude zu zeichnen müssen wir nichts machen.
class Building {
public static void drawRectangle(double xPos, double yPos, double width, double height) {
reset(); // set turtle to origin and make it face upwards
penUp();
goTo(xPos, yPos);
penDown();
forward(height);
turnRight(90);
forward(width);
turnRight(90);
forward(height);
turnRight(90);
forward(width);
}
public static void drawBuilding() { // Fügen Sie hier die benötigten Argumente ein
// Schreiben Sie hier Ihren Code
}
public static void main(String[] args) {
clear();
drawBuilding(); // Ergänzen Sie hier den Aufruf mit den benötigten Argumenten
display(drawing());
}
}
Building.main(new String[0]);
Miniübungen¶
- Können Sie mit dieser Strategie ein Programm schreiben, das ein $n$-Eck zeichnet?
class Drawing {
public static void main(String[] args) {
// Schreiben Sie hier Ihren Code
}
}
Drawing.main(new String[0]);
Die Schönheit der Rekursion¶
Zum Schluss noch etwas Schönes. Wir können mittels Rekursion Fraktale Frafiken zeichnen. Fraktale sind gemoetrische Figuren, die als Teil jeweils wieder dieselbe Figur enthalten. Ein Beispiel dafür ist das Sierpinski Dreick. Diese ist aus drei Dreiecken zusammengesetzt, die selbst wieder aus drei Dreicken bestehen, die selbst wieder aus drei Dreicken bestehen, ....
public class Sierpinski {
public static void drawSierpinski(double length, int depth) {
if (depth==0){
for (int i = 0; i < 3; i++) {
forward(length);
turnLeft(120);
}
}
else {
drawSierpinski(length/2.0 , depth-1);
forward(length/2);
drawSierpinski(length/2.0,depth-1);
backward(length/2);
turnLeft(60);
forward(length/2);
turnRight(60);
drawSierpinski(length/2.0,depth-1);
turnLeft(60);
backward(length/2);
turnRight(60);
}
}
public static void main(String[] args) {
home();
clear();
reset();
penUp();
goTo(-80, -80);
turnRight(90);
penDown();
drawSierpinski(160, 7);
display(drawing());
}
}
Sierpinski.main(new String[0]);
Miniübung¶
- Versuchen Sie den Aufgabe dieser Zeichnung zu verstehen, indem Sie das Dreieck mit unterschiedlichen Rekursionstiefen zeichnen.
- Zusätzlich können Sie auch die Dreicke farbig einfärben.