Lösungshinweise zu den Aufgaben aus Elementare Syntax von C++: Bedingung, Alternative und Mehrfachalternative

Zu Aufgaben, die zu längeren Algorithmen führen, in denen insbesondere Bedingungs-Prüfungen und Alternativen vorkommen, werden einige Lösungshinweise gegeben.

walter

14 Nov. 2018

Taylor-Reihe Sortieralgorithmen Kosinusfunktion Bedingung Sinusfunktion C++ Alternative Gleichungssystem

Inhaltsverzeichnis

Einführung in die Informatik
- Einführung in C++
  - Elementare Syntax von C++: Bedingung, Alternative und Mehrfachalternative
  - Lösungshinweise zu den Aufgaben aus Elementare Syntax von C++: Bedingung, Alternative und Mehrfachalternative

Methodischer Hinweis

Die hier besprochenen Aufgaben sind etwas umfangreicher, so dass es dem Programmier-Anfänger sicher schwer fällt, aus der Aufgabenstellung sofort den Quelltext zu entwickeln. Ein erfahrener Programmierer ist dazu in der Lage — aber auch nur, weil er zuvor schon viele (ähnliche) Algorithmen entwickelt hat.

Als Anfänger sollte man deshalb:

Den in der Aufgabe geforderten Algorithmus zunächst im Pseudocode entwickeln. Dazu werden die Arbeitstechniken eingesetzt, die im Kapitel Einführung in die Programmierung besprochen wurden.
Erst wenn man sich sicher ist, dass man den Algorithmus vollständig verstanden hat, beginnt man damit, den Quelltext in der Programmiersprache zu schreiben.

Auf diese Weise lassen sich die beiden Anforderungen:

Entwickeln eines Algorithmus aus einer konkreten Aufgabenstellung und
Einsetzen der Sprachelemente einer Programmiersprache unter Beachtung ihrer Syntax

voneinander trennen. Dem Anfänger bereiten üblicherweise beide Anforderungen große Schwierigkeiten — erst recht, wenn man es nicht schafft, sie klar voneinander zu trennen. Sie werden aber sehen, wie schnell Sie nach einigen konsequenten Übungen diese Anforderungen meistern.

Aufgaben

Sortieren von Zahlen

Der Nutzer soll drei Zahlen zwischen 0 und 1000 eingeben.

Falls eine Zahl (oder mehrere Zahlen) dies nicht erfüllt, sollen die falschen Zahlen ausgegeben werden; der Nutzer wird aufgefordert, die entsprechenden Zahlen erneut einzugeben.

Falls jetzt die drei Zahlen immer noch nicht zwischen 0 und 1000 liegen, bricht das Programm ab.

Andernfalls sollen die drei Zahlen der Größe nach sortiert ausgegeben werden.

Näherungsweise Berechnung der Sinus- und Kosinusfunktion

Der Nutzer soll gefragt werden, ob er den Winkel im Bogen- oder im Winkelmaß eingegeben möchte. Anschließend soll er den Winkel eingeben.

Das Programm soll den Winkel durch folgende Näherung berechnen (die Berechnungen werden im Bogenmaß durchgeführt):

Zuerst wird die Berechnung der Winkelfunktion auf einen Winkel x im Intervall [0; π / 4] zurückgeführt.
Für x ∈ [0; π / 4] kann eine Näherung verwendet werden, nämlich die Approximation durch eine Taylor-Reihe, siehe Abbildung 1.

Abbildung 1: Formeln zur näherungsweisen Berechnung der Sinus- und Kosinusfunktion.

Ausgegeben werden sollen die Näherungen für sin x und cos x sowie die exakten Werte (berechnet mit den Funktionen aus der Standard-Bibliothek).

Zwei Gleichungen mit zwei Unbekannten

Gegeben ist ein Gleichungssystem wie in Abbildung 2 mit gegebenen Koeffizienten und gesuchten x, y.

Abbildung 2: Gleichungssystem bestehend aus 2 Gleichungen mit 2 Unbekannten und gegebenen Koeffizienten.

Ein Programm soll ausgeben:

Wieviele Elemente hat die Lösungsmenge des Gleichungssystem?
Die Lösungsmenge des Gleichungssystems.

Lösungshinweise

Sortieren von Zahlen

Der schwierige Teil der Aufgabe besteht darin, die drei eingegebenen Zahlen zu sortieren. Dies ist ein Problem, das in zahllosen Anwendungen vorkommt und für das viele Lösungen existieren, die alle ihre Vor- und Nachteil haben. (Wie umfangreich das Problem ist, erkennen Sie, wenn Sie in einem Lehrbuch über Algorithmen oder Algorithmen und Datenstrukturen unter Sortieralgorithmen nachschlagen.

Hier sollen drei einfache Algorithmen vorgestellt werden; in Quelltext umgesetzt werden nur die ersten beiden Algorithmen. Wie dies Sortieralgorithmen auf beliebig viele Elemente zu übertragen sind, ist nicht schwer zu sehen, aber jetzt noch nicht zu realisieren — das Problem ist, dass wir bisher keine geeignete Datenstruktur kennengelernt haben, um beliebig lange Listen darzustellen.

Die Aufgabe wird hier so bearbeitet, dass die eingegebenen Zahlen (a, b, c) ausgegeben werden sollen, und zwar mit der größten Zahl zuerst (absteigende Anordnung — die ansteigende Anordnung ist völlig analog zu behandeln).

1. Der wohl klarste Algorithmus ist eine Variante des SelectionSort-Algorithmus:

Man deklariert zunächst drei Zahlen maximum, medium, minimum, die noch nicht initialisiert werden.
Man beginnt mit der ersten eingegebenen Zahl a: Ist a größer als b und zugleich größer als c, so ist maximum = a.
Andernfalls liefert der Vergleich von b und c das Maximum.
In beiden Fällen erhält man durch je einen weiteren Vergleich, welche Zahl der Variable medium beziehungsweise minimum zugewiesen wird.

Der Quelltext könnte folgendermaßen aussehen (und kann auch kürzer realisiert werden):

// int a, b, c sind bereits eingegeben

int maximum, medium, minimum;

if ((a >= b) and (a >= c))      // a ist Maximum
{
	maximum = a;
	if (b>= c)
	{
	medium = b;
	minimum = c;
	}
	else        // also c > b
	{
	medium = c;
	minimum = b;
	}
}
	else            // a ist nicht Maximum -> entweder b oder c ist Maximum
	{
		if (b >= c)     // b ist Maximum
		{
			maximum = b;
			if (a >= c)
			{
			medium = a;
			minimum = c;
			}
				else
				{
				medium = c;
				minimum = a;
				}
		}
			else        // c ist Maximum
			{
				maximum = c;
				if (a >= b)
				{
					medium = a;
					minimum = b;
				}
					else
					{
						medium = b;
						minimum = c;
					}
			}
	}

cout << "Maximum: " << maximum << endl;
cout << "mittlere Zahl: " << medium << endl;
cout << "Minimum: " << minimum << endl;

Dieser Algorithmus hat zwar eine klar nachvollziehbare Logik, seine Realisierung führt aber zu enorm vielen verschachtelten if-else-Abfragen.

2. Deutlich schlanker ist der BubbleSort-Algorithmus:

Er beruht auf der Beobachtung, dass durch einfache Vertauschungen benachbarter Zahlen in einer Liste jede beliebige Reihenfolge hergestellt werden kann. Im Fall von drei Zahlen reichen sogar drei Vertauschungen. Im schlimmsten Fall sind die drei Zahlen genau falsch herum angeordnet, zum Beispiel 1 2 3 und müssen zu 3 2 1 umsortiert werden. Man geht von vorne nach hinten durch die Liste und und untersucht jeweils ein Zahlenpaar: die Zahlen werden vertauscht, wenn sie falsch angeordnet sind. Hat man die Liste einmal abgearbeitet, beginnt man wieder von vorne. Wie in Abbildung 3 zu sehen ist, reichen bei drei Zahlen schon zwei Durchgänge durch die Liste (man kann sich leicht überlegen, wie viele bei n Zahlen nötig sind).

Abbildung 3: Vorgehensweise beim BubbleSort-Algorithmus.

Zur Realisierung dieses Algorithmus führt man anders als beim SelectionSort-Algorithmus keine neuen Variablen ein, sondern arbeitet mit a, b, c. Man benötigt stattdessen die Vertauschung zweier Zahlen; die entsprechende Funktion wird oft als swap bezeichnet. Man definiert sich eine temporäre Variable, in der eine der zu vertauschenden Zahlen zwischengespeichert wird. Der Quelltext für den swap könnte etwa so aussehen:

int a {1};
int b {2};

// Implemetierung der Funktion swap(), die zwei gegebene Zahlen a und b vertauscht
int temp {a};
a = b;          // a == 2
b = temp;       // b == 1

Damit lässt sich das Sortieren der drei Zahlen a, b, c in einer Mischung aus Pseudocode und C++ leicht formulieren:

if (a < b)
	swap (a,b);
if (b < c)
	swap (b,c);
if (a < b)
	swap (a,b);

Im Vergleich zum SelectionSort-Algorithmus entfallen hier die lästigen Umbenennungen, die jetzt in der einfachen swap-Funktion mit Hilfe der temporären Variable temp geschehen. Bei langen zu sortierenden Listen führt der BubbleSort-Algorithmus aber zu sehr vielen Abfragen und Vertauschungen, was eine sehr lange Rechenzeit verursacht.

Nebenbei: Die Funktion swap() gibt es in der Standard-Bibliothek und erfüllt genau die hier vorgestellte Aufgabe!

3. Zum Sortieren langer Listen eignet sich der QuickSort-Algorithmus:

man startet mit einem beliebigen Element, etwa mit a,
die anderen Elemente werden in zwei Gruppen eingeteilt:
- Elemente links von a (also solche die größer sind als a) und
- Elemente rechts von a (kleiner als a).
Für diese Einteilung müssen also alle Elemente mit a verglichen werden.
Auf die beiden Gruppen von Elemente links und rechts von a wird wieder der QuickSort-Algorithmus angewendet (der jetzt rekursiv aufgerufen wird).

Angewendet auf das Problem, drei Zahle zu sortieren, kann der QuickSort-Algorithmus seine Vorteile noch nicht ausspielen: Dazu müsste man wissen, wie man eine Liste beliebiger Länge abarbeitet und wie man einen rekursiven Aufruf realisiert.

Versucht man den QuickSort-Algorithmus hier umzusetzen (Sortieren von drei Zahlen), gelangt man zu einem Quelltext, der ähnlich aufgebaut ist wie oben beim SelectionSort-Algorithmus. Bei beliebig langen Listen wird der QuickSort-Algorithmus — dadurch er sich selbst aufruft (Rekursion) — zu einem sehr schlanken Quelltext führen.

Näherungsweise Berechnung der Sinus- und Kosinusfunktion

Die Umrechnung vom Winkelmaß ins Bogenmaß ist lediglich ein Dreisatz, der hier nicht erklärt wird.

Für die Berechnungen wird die Kreiszahl π benötigt, die man folgendermaßen laden kann:

#define _USE_MATH_DEFINES 
#include <cmath>                /* für M_PI = 3.14159265358979323846 */

Die Berechnungen werden im Bogenmaß durchgeführt, wobei man von einem beliebigen Winkel ausgeht. Die Berechnung erfolgt dann in vier Schritten (wobei einige der ersten drei Schritte bei speziellen Winkeln entfallen können):

Der Winkel wird in einen positiven Winkel umgerechnet.
Der Winkel wird in das Intervall [0; 2 π] abgebildet (Periodenlänge der Sinus- und Kosinusfunktion ausnützen).
Der Winkel wird in das Intervall [0; π / 4] abgebildet (Symmetrien und Verwandtschaft von Sinus- und Kosinusfunktion ausnützen). Diese Transformation wird für Sinus- und Kosinusfunktion separat durchgeführt, da man andere Symmetrien verwendet.
Es werden die gegebenen Näherungsformeln eingesetzt.

Abbildung 4 zeigt insgesamt 3 Perioden der Sinus-Funktion y = sin x. Am Graphen können die relevanten Transformationen veranschaulicht werden, mit denen ein beliebiger Winkel x auf einen Winkel im Intervall [0; π / 4] zurückgeführt wird:

Orange: Verschiebung um eine ganze Periodenlänge (oder um ein Vielfaches davon); Transformation in das Intervall [0; 2 π].
Blau: Verschiebung um π nach links (mit Vorzeichenwechsel).
Grün: In dem gezeichneten Spezialfall führt die Spiegelung an x = π / 2 bereits auf einen Winkel im Intervall [0; π / 4]. Hier liegt die Formel sin (π - x) = sin(x) zugrunde, die zu keinem Vorzeichenwechsel führt. Falls der Winkel x noch größer als π / 4 ist, muss eine weitere Transformation erfolgen (siehe Abbildung 5).

Abbildung 4: Sinus-Funktion und Veranschaulichung der relevanten Transformationen (Erklärung im Text).

Abbildung 5: Für den Fall, dass der Spezialfall aus Abbildung 1 noch nicht eintritt, also der Winkel nach der Spiegelung an x = π / 2 noch größer als π / 4 ist, wird der Zusammenhang zwischen der Sinus- und Kosinusfunktion verwendet: sin(x) = cos(π / 2 - x).

Im Detail:

1. Mit den Formeln

sin(-x) = - sin(x ) und cos(-x) = cos(x)

wird ein Winkel x ≥ 0 erzeugt.

Dazu wird eine Variable angelegt, die sich merkt, dass im Fall der Sinus-Funktion das Vorzeichen gewechselt wurde. Für die Kosinusfunktion wird diese Variable ebenso vorbereitet, da bei den folgenden Transformationen des Winkels auch die Kosinusfunktion das Vorzeichen wechseln kann.

int faktor_sin {1};
int faktor_cos {1};

if (x < 0)
	{
	faktor_sin *= -1;
	x *= -1;
	}

2. Liegt x schon im Intervall [0; 2 π], kann man zum dritten Schritt übergehen; andernfalls benötigt man die Division n = x / (2 π), wobei n zur nächsten ganzen Zahl abgerundet wird. Der Winkel x - 2 π n liegt jetzt im Intervall [0; 2 π]. Der Wert der Sinus- oder Kosinusfunktion wird dabei nicht verändert.

int n {0};      // Verschiebung um n Perioden nach links
if (x > 2 * M_PI)
	{
	n = x / (2 * M_PI);
	x -= 2 * M_PI * n;      // Verschiebung um n Perioden nach links
	}

3. Der Winkel x liegt jetzt mit Sicherheit im Intervall [0; 2 π]. Durch weitere Transformationen (Verschiebungen und Spiegelungen wird der Winkel jetzt in das Intervall [0; π / 4] abgebildet. Da diese Transformationen für die Sinus- und Kosinusfunktion anders sind, werden die beiden Berechnungen separat durchgeführt.

A) Sinus-Funktion:

1. Fall: x > π:

Da sin(x - π) = - sin(x), wird x um π verschoben und der Vorzeichen-Faktor wechselt sein Vorzeichen:

if (x > M_PI)
{
	faktor_sin *= -1;
	x -= M_PI;          
}

Der neue x-Wert liegt im Intervall [0; π].

2. Fall: x > π / 2:

Jetzt wird sin(π - x) = sin(x) verwendet, wobei die Sinus-Funktion das Vorzeichen nicht wechselt.

if (x > M_PI / 2)
{
	x = M_PI - x;
}

Jetzt liegt x im Intervall [0; π / 2].

3. Fall: x > π / 4:

Es gilt sin(x) = cos(π / 2 - x), das heißt x wird in das Intervall [0; π / 4] abgebildet und zur Approximation der Sinusfunktion wird die Näherung für die Kosinusfunktion verwendet. Wenn der 3. Fall nicht eintritt, ist 0 ≤ x < π / 4 (4. Fall), der unten im else-Zweig behandelt wird; es kann sofort die Näherungsformel für die Sinus-Funktion eingesetzt werden (nur als Pseudocode angegeben):

double q = x * x;       // Zur einfacheren Berechnung der Näherungsformeln

if (x > M_PI / 4)
{
	x = M_PI / 2 - x;
	double q = x * x;
	// Näherung für sin x ist 
	// faktor_sin * (1 - q /2 + q * q / 4)
}
else            // x < M_PI / 4; (4. Fall)
{
	// Näherung für sin x ist 
	// faktor_sin * (x * (1 - q  / 2 + q * q / 5) )
}

B) Kosinusfunktion:

Für die Kosinusfunktion werden nicht nochmal alle Schritte erläutert, es werden nur kurz die Transformationen beschrieben. Der Winkel liegt im Intervall [0; 2 π]. (Achtung: wenn die Formeln unten in Quelltext umgesetzt werden, muss x wieder auf den Wert zurückgesetzt werden, den es nach der Transformation in das Intervall [0; 2 π] hatte!)

1. Fall: x > π:

cos(2 π - x) = cos(x), also kein Vorzeichenwechsel.

2. Fall: x > π / 2:

cos( π - x) = - cos(x), also Vorzeichenwechsel.

3. Fall: x > π / 4:

cos( π / 2 - x) = sin(x), also kein Vorzeichenwechsel; zur Berechnung der Näherung der Kosinusfunktion wird die Näherung der Sinusfunktion verwendet.

4. Fall: 0 ≤ x < π / 4:

Jetzt kann sofort in die Näherungsformel für die Kosinusfunktion eingesetzt werden.