Algorithmen und Datenstrukturen 2

Übungsblatt 2: mehr Iteration und Rekursion

Aufgabe 2-1

Implementieren Sie den „modernen“ Euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers (ggT) zweier positiver Ganzzahlen rekursiv in einer Methode.

Tipp. Dr. Bürg würde diesen (nicht offensichtlichen) Algorithmus möglicherweise so formulieren:

Gegeben: zwei Zahlen a und b
Gesucht: größter gemeinsamer Teiler (ggT)

Start

falls b = 0

ggT gefunden (Ergebnis ist a)

sonst

ermittele ggT von b und (a mod b)

Stop

Tipp. Verwenden Sie folgende Methodensignatur:

static int ggT (int a, int b)

Aufgabe 2-2 *

Schreiben Sie eine Methode, die rekursiv die Quersumme einer übergebenen positiven Ganzzahl ermittelt und das Ergebnis zurückgibt.

Tipp. In Java ist der Wert von x % 10 genau der Wert der niederwertigsten Stelle von x. Der Wert von x / 10 hat die Nachkommastellen abgeschnitten.

Aufgabe 2-3

Entwerfen Sie einen Algorithmus, der iterativ feststellt, ob ein Array des Typs int[] aufsteigend sortiert ist.

Formulieren Sie Ihren Algorithmus in „natürlicher Sprache“ nach Dr. Bürg.
Formulieren Sie Ihren Algorithmus in Java.

Tipp. Verwenden Sie für Teilaufgabe (b) folgende Methodensignatur:

static boolean istSortiert (int[] array)

Zusatzaufgabe 2-4

Entwerfen Sie einen Algorithmus, der rekursiv feststellt, ob ein Array des Typs int[] aufsteigend sortiert ist.

Formulieren Sie Ihren Algorithmus in „natürlicher Sprache“ nach Dr. Bürg.
Formulieren Sie Ihren Algorithmus in Java.

Tipp. Für Teilaufgabe (b) ist möglicherweise folgende Methodensignatur geeignet; übergeben Sie beim Erstaufruf z. B. 0 für testeAbIndex:

static boolean istSortiert (int[] array, int testeAbIndex)

$Id: HEADER.html 2009-04-20 $