Manuel A. Krischer

Wissenschaftlicher Mitarbeiter

»Habe Mut, dich deines eigenen Verstandes zu bedienen!«
(Immanuel Kant)

AP1 - FAQ

Nachbetrachtung zu den häufigsten Anmerkungen zum Praktikum.

Algorithmen & Programmieren I

Tauschen von Variablen

Um die Werte von zwei Variablen a, b zu tauschen wird immer ein dritter temporärer Speicherplatz c benötigt. Beim Zuweisen muss immer sichergestellt werden, das der zu überschreibende Speicherplatz vorher in einer anderen Speicherstelle gesichert wurde.

	c = a;
	a = b;
	b = c;

Arrays und Schleifen

Beim Zuweisen von Werten zu einem Array innerhalb von Schleifen muss zu jedem Zeitpunkt sichergestellt sein, dass der Index des Arrays nicht über der Arraygröße liegt. Eine nachfolgende Prüfung ist nicht Zielführend, denn zu dem Zeitpunkt wurde schon in einen illegalen Speicherbereich geschrieben.

int array[10], i=0;
while(scanf("%d", array[i])) {
	if(i >= 10) {
		break;
	}
	i++;
}

Der zulässige Index im Beispiel liegt zwischen [0..9]. Bei i=9 würde die Schleife jedoch noch einen weiteren Durchlauf starten und einen Wert in array[10] schreiben, um anschliessend festzustellen, dass i >= 10 ist.

call by value, call by reference

Gegeben sei folgendes (stark vereinfachtes) Programm zur Berechnung der Collatzfolge mit Ermittlung der Anzahl und größten Zahl für die Ausgabe im Hauptprogramm.

void collatz(int n, int *max, int *counter ) {
	while(n != 1) {
		if(n%2 == 0)	n = n/2;
		else		n = 3 * n + 1;
		printf("%3d",n);
		*counter = *counter + 1;
		if(n > *max) *max = n;
	}
}
void main() {
	int n, counter=0, max;
	scanf("%d",&n);
	max = n; 
	collatz(n, &max, &counter);
	printf("\nDie grösste vorkommende Zahl ist: %3d\n",max);
	printf("Anzahl der ermittelten Collatzzahlen = %3d\n",counter);
}

Besondere Bedeutung kommt beim Funktionsaufruf dem &-Zeichen, dem address-of-operator zu. Wir übergeben an Stelle 2 und 3 im Funktionsaufruf collatz() nicht den Wert/Value der Variable, sondern die Position im Speicher des Programms, einen Pointer. Die Funktion collatz() legt jetzt 3 lokale Variable (n, max, counter) an, doch nur die Variable n bekommt einen neuen Speicherplatz, der den Wert aus dem Aufruf (7) bekommt. Es handelt sich also hierbei um eine Kopie der Variable mit dem gleichen Namen n aus der main() Funktion. Die Variablen max und counter der collatz()-Funktion verweisen hingegen auf den selben Programmspeicher wie ihre Namensgleichen Variablen aus der Funktion main(). Die Funktion wird durch den * darauf hingewiesen, dass es sich nicht um einen Wert sondern einen Speicherplatz handelt.

Wenn jetzt eine gedachte Zahl "7" in der scanf() Anweisung in #12 eingelesen wird, anschließend in #13 auch max aus main() zugewiesen wird, steht folgender Aufruf der collatz() Funktion während der Programmausführung im Programm: collatz(7, &00002, &00003)

Folgende Tabelle zur Verdeutlichung:

Speicheradresse	Value/Wert	Name in main()	Name in collatz()
&00001	7	n
&00002	7	max	max
&00003	0	counter	counter
&00004	7		n

Die Namen für einen Speicherplatz könnten in beiden Funktionen auch völlig unterschiedlich lauten, denn sie gelten nur für die jeweilige Funktion und nicht ausserhalb. Da aber beide Funktionen auf den selben Speicherplatz zugreifen, sind die Änderungen von collatz() an max und counter auch in der main()-Funktion sichtbar. Die Speicherplätze &00001 und &00004 (n) sind jeweils nur innerhalb der Funktion zugreifbar, die Veränderung die collatz() an n (&00004) vornimmt, haben keine Auswirkungen auf n (&00001) der main()-Funktion.

Rekursion

Eine Rekursion lässt sich immer dann erkennen, wenn innerhalb des Funktions-/Methodenkörpers die Funktion selbst erneut aufgerufen wird. Fehlende Schleifen, IF-Bedingungen, oder return-Anweisungen lassen nicht alleine auf eine Rekursion schließen.

Gabel des Todes

Warum sollte folgender Code nie ausgeführt werden?

:(){ :|:& };:

Der oben aufgeführte Code ist eine sogenannte "Fork-Bombe". Unter Unix wird für die Erstellung eines neuen Prozesses der aufrufende Prozess geclont und anschließend i.d.R. mit dem Code des neuen Programms bestückt. Erfolgt der zweite Schritt nicht, existieren zwei nahezu gleichartige Prozesse im Code, die abwechselnd arbeiten. Der Code oben wird in einer Shell ausgeführt und dort interpretiert. Er enthält eine Funktionsdefinition mit Namen :, die im Funktionsblock { .. }; die Anweisung enthält, sich selbst mehrfach aufzurufen, unteranderem im Hintergrund &. Anschließend wird die soeben definierte Funktion mit dem Kommando : gestartet und erzeugt dann in sehr kurzen Abständen jeweils zwei Aufrufe von sich selbst, die sich ebenfalls jeweils zwei Mal aufrufen ( O(n²) ). Innerhalb kürzester Zeit werden so also sehr viele Prozesse gestart, die alle Systemressourcen verbrauchen und den Rechner unbenutzbar (bis zum harten Neustart) machen.