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 $

 Name                                   Last modified      Size  Description
 Parent Directory                                            -   
 HEADER.html                            2023-10-11 10:00  2.8K  
 Loesung24.java                         2023-10-11 10:00  1.7K  
 Loesung23.java                         2023-10-11 10:00  1.2K  
 README.html                            2023-10-11 10:00  957   
 Loesung21.java                         2023-10-11 10:00  882   
 Loesung22.java                         2023-10-11 10:00  797