Algorithmen und Programmierung II

 


SS 2002 Dr. Hannes Federrath
Übung 7 Natalie Ardet
Abgabe bis zum Do. 20.06.02

Die Lösung der Aufgaben und die Abgabe der Lösungen erfolgt in Zweiergruppen!

Hinweis: Benutze die Ressourcen der ALP2 Webseite.

Aufgabe 1 (10 P.)

Führe eine Laufzeitanalyse der Methode getPowerOf() durch. Erkläre die Einzelschritte deiner Berechnung.

static int getPowerOf(int a, int x) {
	// requires (x >= 0);
	int power = 1;
	while (x != 0) {
		power = power * a;
		x--;
	}
	return power;
}

Aufgabe 2 (5 + 5 = 10 P.)

Die Prozedur solve  aus der Vorlesung benutzt zwei Ergebnisparameter x1 und x2. Java bietet jedoch keine Ergebnisparameter.

void solve (in float p, in float q, out float x1, out float x2)
{ 
	float root = sqrt( p * p / 4 – q );
	x1 = -p / 2 + root;
	x2 = -p / 2 – root;
}
  1. Schreibe die Prozedur solve als JAVA-Methode dessen Rückgabewert das Ergebnis der Berechnung ist.
  2. Schreibe die Prozedur solve als JAVA-Methode mit dem Rückgabewert void und den formalen Parametern p und q. Hinweis: Definiere eine Klasse Equation.

Aufgabe 3 ( 10 P.)

Gegeben sind zwei Zeichenketten muster und text; muster muss in text gefunden werden.
Schreibe eine iterative Java-Funktion mit der Spezifikation

int suchen(final char[] muster, final char[] text)

die den Wert -1 zurückgibt, wenn muster nicht in text vorkommt und sonst den Index, bei dem das erste Vorkommnis von muster in text beginnt. Die Funktion darf nur den Vergleich von Zeichen mit Hilfe des Operators == durchführen.

Aufgabe 4 (20P.)

Entwerfe einen Algorithmus  der das Problem der stabilen Liebesbeziehungen löst. Hier müssen n Ehepaare so einander zuneigen, dass ihre Ehen ungefährdet sind. Jeder der 2n Beteiligten besitzt eine Liste der Länge n, in der die Personen des anderen Geschlechts in der Reihenfolge der Zuneigung aufgeführt wird. Im Idealfall steht der Ehepartner auf der ersten Stelle. Eine Ehe gilt als gefährdet, wenn es einen anderen Mann und eine andere Frau gibt, dem die Frau bzw. der der Mann mehr zugeneigt ist als dem Ehepartner.
Für die Darstellung des Algorithmus ist Pseudo-Code oder ein grafische Darstellung zulässig. 
Die Erläuterung der Funktionsweise des Algorithmus fließt in die Bewertung mit ein.
Hinweis: Ein Algorithmus der alle mögliche Paarbildungen berechnet ist nicht zulässig, weil ineffizient.

Implementiere den Algorithmus in JAVA. 
Für die Speicherung der Paare kann java.util.Hashtable verwendet werden.
Zur Information:
java.util.Hashtable ist in der neuen Java Version durch java.util.HashMap ersetzt worden.

Beispiel einer instabilen Beziehung:
Adam hat Bella lieber als seine Ehefrau Anna, und Bella hat Adam lieber als ihren Ehemann Berthold.

Bemerkung: Ich habe gleichgeschlechtliche Paare weggelassen, denn das hätte das Problem ein bisschen komplizierter gemacht ;)


10.06.2002