Informatik - Algorithmen

Algorithmen in Pseudocode

Die Algorithmen sind in echten Programmen umzusetzen, d.h. im Programm sind entsprechende Variablen zu definieren, Dialoge für die Eingaben zu schreiben und der Pseudocode in entprechenden Programmcode zu übersetzen. Vergessen Sie nicht auch die Resultat auszugeben.

Treffen Sie die Wahl des Datentyps sorgfältig: Den Typ int nur für ganze Zahlen und wenn es ums zählen geht, physikalische Größen sind immer reele Zahlen und der geeignete datentyp ist deshalb double.
Verwenden Sie den Debugger und/oder zusätzliche Ausgaben, um den Ablauf der Algorithmen zu verfolgen.

 

Wurzelziehen nach Archimedes

Archimedes (um 287-212 v. Chr.) hat für die Berechnung der Quadratwurzel einer Zahl a folgende Iterationsformel angegeben:

Ein Algorithmus zur Verwendung dieser Formel lautet:

  Zahl a lesen
  xneu = a
  Wiederhole 
    xalt = xneu
    xneu = (xalt + a/xalt)/2
  solange |xneu - xalt| > epsilon

epsilon ist die Genauigkeit der Berechnung, z.B. 1E-4.

Anzahl der Ziffern einer ganzen Zahl bestimmen

Der folgende kurze Algorithmus bestimmt die Anzahl der Ziffern (w) einer ganzen Zahl z (im Zehnersystem):

w = 1, s = 10
Solange s <= z wiederhole
  w = w + 1
  s = s * 10
GGT

Führe folgenden Pseudocode für die Berechnung des größten gemeinsamen Teiler (GGT) zweier natürlichen Zahlen a, b aus. Wähle dazu zwei geeignete Werte für a und b (a und b > 20). Schreibe ein C Programm zu diesem Algorithmus. 

a und b einlesen;
Wiederhole
  Berechne den Rest r der Ganzzahldivision a / b.
  Ersetze a durch b.
  Ersetze b durch den berechneten Rest.
solange Rest r ungleich Null ist.
Der letzte Wert von a ist der GGT.
0.xxxxx in Dualzahl umwandeln

Folgender Pseudocode für die Umrechnung des Nachkommateiles einer Dezimalzahl in das Dualsystem soll in ein C-Programm umgesetzt werden.

Variablen

z .. die Zahl in der Form 0.xxxxxx
n .. Anzahl der Nachkommastellen

Algorithmus für n Nachkommastellen:

Zahl z einlesen
Anzahl der zu berechnenden Nachkommastellen einlesen
Für i = 1 bis n führe aus {
  multipliziere z mit 2 ( z = 2*z )
  Falls ( z  1.0 ) dann {
    1 ausgeben (drucken)
    von z 1.0 subtrahieren ( z = z - 1 ) }
  sonst
    0 ausgeben
}
Fibonacci-Zahlen

Führe folgenden Pseudocode aus. Welche Folge von Zahlen wird ausgegeben ?

amax einlesen;
a = 1;
b = 1;
Wiederhole
   a ausgeben;
   c = a + b;
   a = b;
   b = c;
solange a < amax ;
Widerstandskette
Folgender Algorithmus zeigt, dass der Widerstandswert einer beliebig langen Anordnung von Widerständen in der folgenden Form einen endlichen Wert hat.

Rneu = R2 + 2 R1
Wiederhole
  Ralt = Rneu
  Rneu = 2 R1 + R2 || Ralt
solange | Rneu - Ralt | > eps
Zapfenrechnung

Ein Programm soll eine Zapfenrechnung ausführen und die einzelnen Ergebnisse sauber formatiert ausgeben.

Pseudocode:

Anfangswert für z einlesen und ausgeben
Für m = 2 bis 9
  z = z * m
  z ausgeben
Für m = 2 bis 9
  z = z / m
  z ausgeben