Lösungsvorschläge

zu den Aufgaben im Kapitel 7

Aufgabe 7.1: Entwerfen Sie eine schnelle Java-Funktion, die das Problem P11 löst (Eingabe: Eine natürliche Zahl n zwischen 1 und 10, Ausgabe: Die ersten n Ziffern der Zahl p).

Lösung:

static void p11(int n) {
  String pi = "" + java.lang.Math.PI;
  for (int i = 0; i <= n; i++)
   System.out.print(pi.charAt(i)); }

Aufgabe 7.2: Ist das folgende Problem ein algorithmisches Problem? Begründen Sie Ihre Antwort.

P13: Gesucht wird ein Algorithmus mit folgendem Ein/Ausgabeverhalten:

Eingabe: eine positive Zweierpotenz n, d.h. n Î { 1, 2, 4, 8, 16, 32, 64, ... }

Ausgabe: der Logarithmus (zur Basis 2) von n in Binärbruch-Schreibweise, ohne Abkürzungen

Lösung: Ja. Das Problem stellt eine unendliche Menge von Einzelnprobleme dar, für die je eine Lösung gibt.

Aufgabe 7.3: Ist das folgende Problem ein algorithmisches Problem? Begründen Sie Ihre Antwort.

P14: Gesucht wird ein Algorithmus mit folgendem Ein/Ausgabeverhalten:

Eingabe: eine natürliche Zahl n, d.h. n Î { 1, 2, 3, 4, 5, 6, 7, ... }

Ausgabe: der Logarithmus (zur Basis 2) von n in Binärbruch-Schreibweise, ohne Abkürzungen

Lösung: Nein, ist kein algorithmisches Problem (da der Logarithmus einiger natürlichen Zahlen, z.B. 3, sich nicht wirklich endlich darstellen lässt, höchstens "näherungsweise").

Aufgabe 7.4: Ist das folgende Problem ein algorithmisches Problem? Begründen Sie Ihre Antwort.

P15: Gesucht wird ein Algorithmus mit folgendem Ein/Ausgabeverhalten:

Eingabe: eine ganze Dezimalzahl d ohne Vorzeichen, d.h. d Î { 0, 1, 2, 3, 4, 5, 6, 7, ... }

Ausgabe: die entsprechende Binärzahl b, ohne Abkürzungen

Lösung: Ja, ist ein algorithmisches Problem (weil jede endliche Dezimalzahl sich in eine endliche Binärzahl umwandeln lässt).

Aufgabe 7.5: Ist das folgende Problem ein algorithmisches Problem? Begründen Sie Ihre Antwort.

P16: Gesucht wird ein Algorithmus mit folgendem Ein/Ausgabeverhalten:

Eingabe: ein Dezimalbruch d mit genau einer Stelle hinter dem Komma (z.B. d = 7,0 oder 36,5 oder 789,4 oder 0,1 usw.)

Ausgabe: ein entsprechender Binärbruch b, ohne Abkürzungen.

Lösung: Nein, ist kein algorithmisches Problem (weile einige Dezimalbrüche mit einer Stelle hinter dem Komma sich nicht in endlich lange Binärbrüche umwandeln lassen, z.B. der Dezimalbruch 0.1)

Aufgabe 7.6: Ist das folgende Problem ein algorithmisches Problem? Begründen Sie Ihre Antwort.

P17: Gesucht wird ein Algorithmus mit folgendem Ein/Ausgabeverhalten:

Eingabe: eine dreistellige Dezimalzahl d, z.B. d = 123 oder 002 usw.

Ausgabe: die entsprechende Binärzahl b, ohne Abkürzungen

Lösung: Nein, ist kein algorithmisches Problem (weil es nur endlich viele, nämlich 1000, Einzelprobleme zu lösen gibt. Solche Probleme werden ausgeschlossen, weil man bei ihrer Komplexität "schummeln" könnte, indem man alle endlich vielen Einzelprobleme löst, die Ergebnisse in einer Tabelle speichert und dort nachsieht).

Aufgabe 7.7: Für welche Parameterwerte hält die folgende Prozedur haelt7, und für welche hält sie nicht?

void haelt7(int n) { // requires n > 0
  while(n != 7)
   n = n-3;
}

Lösung: Sie hält für die Parameterwerte 7, 10, 13, 16, …

Bemerkung: Sie hält für alle Parameterwerte, aber nur wegen des int-Überlaufs bei Integer.MIN_VALUE. Hierbei wird aber die Vorbedingung n > 0 nicht erfüllt.

Aufgabe 7.8: Für welche Parameterwerte hält die folgende Prozedur haeltVielleicht und für welche hält sie nicht?

void haeltVielleicht(int n) { // requires n > 0
  while (n != 1)
   if ((n % 2) == 0) // n ist gerade
     n = n / 2;
   else // n ist ungerade
     n = 3 * n + 1;
}

Lösung: Es ist nicht bekannt, ob eine positive Zahl gibt, für die die Prozedur haeltVielleicht nicht halten würde.

Aufgabe 7.9: Zeigen Sie, dass man mit dem Katalog in der Abbildung 7.5 noch nicht einmal eine 3´3 Fläche kacheln kann.

Lösung: Alle 3⁹ Möglichkeiten sollen ausprobiert werden.

Aufgabe 7.10: Entwerfen Sie einen einfachen Lösungsalgorithmus und ermitteln Sie seine Zeitkomplexität. Die besten bekannten Lösungsalgorithmen sind nicht „wesentlich“ schneller als der von Ihnen entwickelte Algorithmus.

Lösung: Ein Algorithmus zum „probieren“: Alle Permutationen (alle mögliche Anordnungen) der n² Kacheln werden untersucht, ob die Anordnung die Fläche korrekt kachelt oder nicht. Die Zeitkomplexität ist 2 hoch n²

Aufgabe 7.11: Entwerfen Sie einen Lösungsalgorithmus und ermitteln Sie seine Zeitkomplexität.

Lösung: Ein Algorithmus zum „probieren“: Die Gewichte und die Werte aller Untermengen der Gegenstände werden errechnet; das Maximum aller Werte wird gesucht, bei denen das Gewicht unter dem Fassungsvermögen des Rucksacks bleibt. Die Zeitkomplexität ist 2ⁿ, weil es 2ⁿ Untermengen einer Menge der Größe n gibt.

Aufgabe 7.12: Entwerfen Sie einen Lösungsalgorithmus und ermitteln Sie seine Zeitkomplexität.

Lösung: Ein Algorithmus zum „probieren“: Die Differenz der Werte aller Aufteilungen der Diamanten wird errechnet und das Minimum gesucht. Die Zeitkomplexität ist 2ⁿ.

Aufgabe 7.13: Entwerfen Sie einen Lösungsalgorithmus und ermitteln Sie seine Zeitkomplexität.

Lösung: Ein Algorithmus zum „probieren“: Alle Wege im Graph werden ermittelt und nicht Hamilton-Wege verworfen. Die Zeitkomplexität ist 2ⁿ.