Skip to main content

Aufgabenblock 2

Alle Aufgaben sollen als eigenständige Funktionen implementiert werden, die Sie aus einer eigenen main-Funktion heraus testen. Testen Sie unterschiedliche Eingaben, sofern die Funktionen Eingaben erwarten, und überlegen Sie, welches Ergebnis Sie von dem Programm erwarten. Erst durch das Testen der Funktionen mit unterschiedlichen Eingabewerten kann man einigermaßen sichergehen, dass der Algorithmus richtig implementiert wurde.

2.1. Die Sache mit dem Teilen​

Euklid beschrieb ein Verfahren zum Bestimmen des größten gemeinsamen Teilers zweier nicht-negativer ganzer Zahlen a und b, wobei a größer oder gleich b sein muss. Ist der Parameter b gleich 0, dann ist a das Ergebnis der Funktion. Ansonsten wird so lange die folgende Berechnung durchgeführt, bis b gleich 0 ist:

  • h ist der ganzzahlige Rest der Division von a durch b
  • a erhält den Wert von b
  • b erhält den Wert von h

Sobald b den Wert 0 annimmt, enthält a den größten gemeinsamen Teiler. Überlegen Sie zudem, wie Sie diesen Algorithmus rekursiv umsetzen können.

2.2. Die Sache mit der Wurzel.​

In vielen Berechnungen braucht man die Quadratwurzel einer Zahl. Während man das Quadrat einer Zahl noch als Produkt der Zahl mit sich selbst berechnen kann, ist dies bei der Quadratwurzel nicht mehr so leicht möglich. Hierfür hat Heron von Alexandria einen Näherungsalgorithmus vorgeschlagen, der schnell gute Werte liefert und den Sie bitte als Funktion implementieren. Dieser Algorithmus bekommt die Fließkommazahl x als Parameter und gibt den genäherten Wert der Wurzel von _x: zurück. Der Algorithmus verwendet eine weitere Fließkommazahl e, die den initialen Wert von 1 hat. Nähern Sie nun die Wurzel von x in N Schritten an. In jedem Schritt wird e zum Mittel aus e und x / e. e enthält nach den N Schritten die genäherte Wurzel.

Testen Sie ihren Algorithmus durch eine selbst geschriebene main-Funktion. Testen Sie auch, wie sich die Konstante N auf den genäherten Wert auswirkt. Sie können die Funktion zu Übungszwecken einmal iterativ und einmal rekursiv lösen.

2.3. Die Sache mit Pi​

Nähern Sie Pi mit dem Verfahren von de Buffon an. Das Verfahren von de Buffon sieht vor, dass man Zahlenpaare zwischen 0 und 1 zufällig wählt. Diese Zahlenpaare stellen Koordinatenpaare in der zweidimensionalen Ebene dar. Für jedes Koordinatenpaar wird geprüft, ob der Abstand zum Ursprung kleiner oder gleich 1 ist (hier hilft der Satz des Pythagoras). Die Anzahl der Koordinatenpaare, auf die das zutrifft, wird gezählt. Um auf die Zahl Pi zu kommen, muss die Zahl der zutreffenden Koordinatenpaare mit 4 multipliziert werden und durch die Anzahl der bereits erzeugten Koordinatenpaare geteilt werden. Geben Sie alle 100 Koordinatenpaare den genäherten Wert für Pi aus. Zur Übung implementieren Sie dieses Näherungsverfahren einmal unter der Verwendung einer for-Schleife (benutzen Sie einen ausreichend großen Wert als Abbruchkriterium) und einmal unter Verwendung einer while-Schleife.

Hinweis: Wenn Sie die Ausgabe "pausieren" wollen, um die Häufigkeit in Ruhe zu lesen, dann können Sie mit dem Einlesen eines Zeichens das Programm zum Anhalten "zwingen".

2.4. Die Sache mit dem Zufall​

Die rand() Funktion soll Zufallszahlen generieren. In dieser Aufgabe schauen wir uns an, wie zufällig diese Zahlen wirklich sind. Sind die Zufallszahlen gut sein, so sind diese auf lange Sicht gleichmäßig verteilt. Hierfür erzeugen Sie zunächst ein zweidimensionales Array, welches 250 x 250 Eintragungen enthält. Anschließend soll das Programm wieder ganzzahlige Koordinatenpaare zwischen 0 und 249 erzeugen und die Eintragung an der entsprechenden Stelle im Array um 1 vergrößern. Führen Sie dies für eine ausreichend große Anzahl an Koordinatenpaaren durch und geben Sie das entstehende Array aus. Was können Sie beobachten?

Herausforderung: Sie können Sie die Ausgabe auch optisch ansprechend gestalten, indem sie die Bildbibliothek verwenden. Hiermit können Sie alle 1000 Koordinatenpaare das Array farbcodiert ausgeben. Ein Eintrag entspricht einem Pixel und die Anzahl entspricht der "Helligkeit" des Farbwerts (verwenden Sie einfach Grauabstufungen).