Algorithm Entwuerf Flashcards
Minimum
Implementieren Sie die folgenden zwei Funktionen:
static int min2(int a, int b)
static int min6(int a, int b, int c, int d, int e, int f)
Die Funktionen sollen jeweils das kleinste ihrer Argumente als Ergebnis zurückliefern.
Es dürfen keine Bibliothesfunktionen verwendet werden. Für jede Anwendung einer gewöhnlichen (“if) oder arithmetischen (?:”) Kontrollstruktur werden Ihnen drei Punkte abgezogen (Maximal 9 Punkte sind zu erreichen).
Ansonsten dürfen alle anderen Anweisungen benutzt werden, einschließlich Aufrufe von min2() und min6().
Eine mögliche Lösung ohne Verwendung von “if” oder “?”-Operator ist die folgende:
static int min2(int a, int b) {
int diff = a - b;
int min = b + (diff & (diff»_space; 31));
return min;
}
static int min6(int a, int b, int c, int d, int e, int f) {
int min1 = min2(a, b);
int min2 = min2(c, d);
int min3 = min2(e, f);
int min4 = min2(min1, min2);
int min5 = min2(min4, min3);
return min5;
}
Die Funktion min2() berechnet das Minimum von a und b, indem sie den Unterschied zwischen a und b berechnet und dann die Summe von b und dem Ergebnis einer bitweisen Operation auf diesem Unterschied ausgibt. Diese bitweise Operation gibt entweder 0 oder -1 zurück, abhängig davon, ob der Unterschied positiv oder negativ ist. Wenn der Unterschied negativ ist, addiert die bitweise Operation -1 auf b, um das Minimum zurückzugeben.
Die Funktion min6() ruft min2() wiederholt auf, um das Minimum aller sechs Argumente zu finden. Zunächst werden min1 und min2 mit min2() berechnet, dann wird min3 mit min2() von e und f berechnet. Danach wird das Minimum von min1 und min2, also min4, mit min2() berechnet. Schließlich wird das Minimum von min4 und min3, also min5, mit min2() berechnet und zurückgegeben.
Die Verwendung von bitweisen Operationen ermöglicht es, Vergleiche zu vermeiden und dadurch die Anzahl der Kontrollstrukturen zu minimieren.
Minimum
Implementieren Sie die folgenden zwei Funktionen:
static int min2(int a, int b)
static int min6(int a, int b, int c, int d, int e, int f)
Die Funktionen sollen jeweils das kleinste ihrer Argumente als Ergebnis zurückliefern.
Es dürfen keine Bibliothesfunktionen verwendet werden. Für jede Anwendung einer gewöhnlichen (“if) oder arithmetischen (?:”) Kontrollstruktur werden Ihnen drei Punkte abgezogen (Maximal 9 Punkte sind zu erreichen).
Ansonsten dürfen alle anderen Anweisungen benutzt werden, einschließlich Aufrufe von min2() und min6().
Eine mögliche Lösung ohne Verwendung von “if” oder “?”-Operator ist die folgende:
static int min2(int a, int b) {
int diff = a - b;
int min = b + (diff & (diff»_space; 31));
return min;
}
static int min6(int a, int b, int c, int d, int e, int f) {
int min1 = min2(a, b);
int min2 = min2(c, d);
int min3 = min2(e, f);
int min4 = min2(min1, min2);
int min5 = min2(min4, min3);
return min5;
}
Die Funktion min2() berechnet das Minimum von a und b, indem sie den Unterschied zwischen a und b berechnet und dann die Summe von b und dem Ergebnis einer bitweisen Operation auf diesem Unterschied ausgibt. Diese bitweise Operation gibt entweder 0 oder -1 zurück, abhängig davon, ob der Unterschied positiv oder negativ ist. Wenn der Unterschied negativ ist, addiert die bitweise Operation -1 auf b, um das Minimum zurückzugeben.
Die Funktion min6() ruft min2() wiederholt auf, um das Minimum aller sechs Argumente zu finden. Zunächst werden min1 und min2 mit min2() berechnet, dann wird min3 mit min2() von e und f berechnet. Danach wird das Minimum von min1 und min2, also min4, mit min2() berechnet. Schließlich wird das Minimum von min4 und min3, also min5, mit min2() berechnet und zurückgegeben.
Die Verwendung von bitweisen Operationen ermöglicht es, Vergleiche zu vermeiden und dadurch die Anzahl der Kontrollstrukturen zu minimieren.
Einfache Rekursion:
In der Vorlesung haben wir erfahren, dass man eine for-Schleife in eine Tail-
Rekursion umschreiben kann und zurück.
Für eine Liste vom typ
class Node{
int value;
Node next;
}
braucht Ihr noch eine Funktion, die die Anzahl der Elemente in der Liste
aufzählt. Würde man es als for-Schleife schreiben, würde die Funktion beispielsweise
so aussehen.
public static int count(Node liste){
int cnt=0;
for(Node n=liste; n!=null; n=n.next){
cnt++;
}
return cnt;
}
Jedoch sind eure f und w Tasten defekt, daher dürft ihr weder for noch while
schreiben, if sei aber erlaubt.
Schreibt die Funktion als (Tail-)Rekursion auf, falls ihr if nicht verwendet
erhaltet ihr einen Zusatzpunkt.
Hier ist eine Tail-Rekursion-Variante der count-Funktion für die gegebene Liste:
java
Copy code
public static int count(Node liste) {
return countHelper(liste, 0);
}
private static int countHelper(Node node, int acc) {
if (node == null) {
return acc;
} else {
return countHelper(node.next, acc + 1);
}
}
Die count-Methode ruft eine Hilfsmethode countHelper auf, die als zweites Argument einen Akkumulatorwert für die Anzahl der Elemente verwendet. In jedem rekursiven Schritt wird der Akkumulatorwert um 1 erhöht und die countHelper-Methode wird mit dem nächsten Knoten in der Liste aufgerufen, bis das Ende der Liste erreicht ist. Wenn das Ende erreicht ist, wird der endgültige Akkumulatorwert zurückgegeben. Diese Funktion ist eine Tail-Rekursion, da der rekursive Aufruf am Ende des Methodenkörpers steht und keine weiteren Aktionen nach dem rekursiven Aufruf ausgeführt werden.
