Algorithmen & Datenstrukturen
Programmieren 1
von Prof. Jürgen Plate

Programmierübungen in "C"

Zeichen und Zeilen zählen

Es soll von der Standardeingabe zeichenweise bis EOF eingelesen werden.
Das Programm soll dabei Zeichen und Zeilen zählen und nach Ende der Eingabe die Anzahl gelesener Zeichen und Zeilen ausgeben.

Ablauf:
Zeichenvariable, Zeichen- und Zeilenzähler definieren,
bis EOF einlesen, Zeichen und Zeilen zählen,
Ergebnis ausgeben.

Quadratwurzel

Ein Algorithmus zur Ermittlung der Quadratwurzel einer positiven Zahl X ist iterativ gegeben durch:


    a = X; b = 1;
    solange a > b wiederhole
       a = (a + b)/2; b = X/a;

Schreiben Sie ein Programm, das diesen Algorithmus als Funktion wurz() implementiert und testen Sie die Funktion mit geeigneten Eingabewerten.

Umrechnung in Prozent

Maximal 30 Doublezahlen werden von der Standardeingabe in ein Feld eingelesen.
Das Ende der Eingabe wird durch die Zahl 0.0 mitgeteilt.
Die einzelnen Feldelemente sind zu addieren und eine Tabelle der Werte mit dem prozentualen Anteil an der Gesamtsumme auszugeben.

Ablauf:
Wertearray und Zähler definieren,
bis "0.0" einlesen, Werte addieren und zählen,
für jeden Wert den Wert selbst und den prozentualen Anteil ausgeben.

Zerlegung in Primfaktoren

Schreiben Sie ein Programm, das nach Eingabe einer natürlichen Zahl N die Zerlegung in Primfaktoren angibt. Zum Beispiel ergibt sich für N=100 die Ausgabe

 
     100 = 2 * 2 * 5 * 5

Man muß dazu keine Primzahlen kennen. Es genügt, die Teiler D = 2, 3, ... zu testen und im Erfolgsfall statt mit N nur noch mit N/D weiterzumachen.

Prüfsummenberechnung I

Die Internationale Standardbuchnummer (ISBN), die jedes Buch eindeutig identifiziert, setzt sich zusammen aus der Länderkennung (eine Ziffer, z.B. 3 für Deutschland, 1 für USA), der Verlagsnummer (3 - 6 Ziffern), der Titelnummer (2 - 5 Ziffern) und einer Prüfziffer. Die einzelnen Zifferngruppen werden durch Bindestriche getrennt, z. B.:

3-453-20913-3
3-446-21368-6
3-930673-72-X
usw.

Wenn man die Bindestriche wegläßt, hat die ISBN immer 10 Ziffern. Die letze Ziffer (Prüfziffer), ergibt sich aus der Formel für die einzelnen Ziffern x₁, x₂, ..., x₉:

x₁₀ = Summe(i * x_i) modulo 11 (i = 1, ..., 9)

Sie erlaubt das Erkennen von Einzelfehlern und teilweise Doppelfehlern bei der Eingabe. Da die Prüfziffer modulo 11 berechnet wird, reichen die Ziffern 0 bis 9 nicht aus, sondern für die Zahl 10 wird der Buchstabe 'X' hinzugenommen (römische Zehn).

Entwerfen Sie ein Programm, daß nach Eingabe der 10-stelligen ISBN (als String ohne Bindestriche) die Prüfziffer aus den ersten 9 Stellen berechnet und mit der eingegebenen Prüfziffer (also der letzten Stelle) vergleicht.

Prüfsummenberechnung II

Die Seriennummer eines deutschen Personalausweises besteht aus 10 Ziffern. Dabei ist:

731731731    731731  731731
*********    ******  ******
wwwwNNNNNaD<<yyMMddb<YYmmDDc<<<<<<d
|||||||||||  ||||||| |||||||      |
|||||||||||  ||||||| |||||||      -\__ Pruefsumme ALLER Ziffern
|||||||||||  ||||||| |||||||
|||||||||||  ||||||| ||||||-\__ Pruefsumme Ablaufdatum
|||||||||||  ||||||| ||||--\__ Ablaufdatum Tag
|||||||||||  ||||||| ||--\__ Ablaufdatum Monat
|||||||||||  ||||||| --\__ Ablaufdatum Jahr
|||||||||||  |||||||
|||||||||||  ||||||-\__ Pruefsumme Geb.-Datum
|||||||||||  ||||--\__ Geb.-Tag
|||||||||||  ||--\__ Geb.-Monat
|||||||||||  --\__ Geb.-Jahr
|||||||||||
|||||||||| \__ Staatszugehoerigkeit (D = Deutsch?)
||||||||| \__ Pruefsumme fuer wwwwNNNNN
||||-----\__ laufende Zaehlnummer
----_ Erstwohnsitz Kennzahl

Für die Berechnung der Püfziffern gilt folgende Regel:

Prüfsumme a:
Beginnend mit der ersten Stelle der Wohnsitzkennung, wird jede Ziffer mit den Faktoren "7 3 1 7 3 1 7 3 1" multipliziert und die Ergebnisse summiert (Also x₁*7, x₂*3, x₃*1, ..., x₉*1). Der Rest einer Division des Endergebnisses durch 10 ergibt die gesuchte Prüfziffer.
Prüfsumme b:
Hier wird beim Geburtsjahr begonnen und die Berechnung endet beim Geburtstag.
Prüfsumme c:
Analog für das Ablaufdatum.

Prüfsumme d:
Hier wird die Gesamtprüfsumme ermittelt:

7317317317   3173173 1731731
wwwwNNNNNaD<<yyMMddb<YYmmDDc<<<<<<d

Beispiel Prüfsumme Ausweisnummer:
Die Ausweisnummer lautet "270752123". Daraus ergibt sich die Prüfziffer:

(2*7 + 7*3 + 0*1 + 7*7 + 5*3 + 2*1 + 1*7 + 2*3 + 3*1) modulo 10 = 7

Entwerfen Sie ein Programm, daß nach Eingabe der 10-stelligen Personalausweisnummer (als String) aus den ersten 9 Stellen die Prüfziffer berechnet und mit der eingegebenen vergleicht. Erweitern Sie dann das Programm, um alle Prüfsummen zu berechnen.

Textkonvertierung

Schreiben Sie nur unter Verwendung der Funktionen getchar() und putchar() ein Kopierprogramm, das jedes TAB-Zeichen in die Zeichenfolge "-->" und jedes BACKSPACE-Zeichen in die Zeichenfolge "<-" umwandelt. So werden TAB- und BACKSPACE- Zeichen sichtbar gemacht. Weiterhin sollen alle Zeichen, deren ASCII-Code einen Wert kleiner 32 besitzt, durch einen '.' dargestellt werden.

Arrayoperationen

Folgende elementare Operationen mit Arrays sind zu programmieren:

Einfügen eines Elementes an einer vorgegebenen Stelle (mit Prüfung, ob das Array überhaupt noch Werte aufnehmen kann).
Löschen eines Elementes an einer vorgegebenen Stelle (mit anschließendem Zusammenschieben der Elemente, damit keine Lücke bleibt).
Suchen eines Elementes.

Verwenden Sie zuerst ein Array von Integer-Werten. Wenn damit alles funktioniert, versuchen Sie es mit einem Array von Zeichenketten der Länge 20.

Mittelwert

Es soll der Mittelwert von Float-Zahlen ermittelt werden. Dazu wird zuerst ein Programm geschrieben, das die Zahlenwerte von Tastatur einliest und sie in einer einer Binärdatei speichert.

Dannach schreiben Sie das Mittelwert-Programm. Dies liest die Daten aus der zuvor erzeugten Binärdatei und berechnet den Mittelwert. Schreiben Sie zwei Varianten des Programms:

Einlesen aller Werte in ein eindimensionales Array mit anschließender Summenbildung und Mittelwertberechnung (Mittelwert = Summe/Anzahl).

Sukzessive Mittelwertbildung nach dem Lesen eines Wertes (also ohne Array). Dazu verwenden Sie die Formel:

       Mittel = X;                         1. Wert
       Mittel = Mittel - (Mittel - X)/i    i. Wert

Wie leitet sich die Formel der zweiten Variante her?

Abschreibung

In einem weiteren Programm sollen die Abschreibungen und Restbuchwerte für Maschinen berechnet werden. Als Abschreibungsmethode soll die degressive Abschreibung angewendet werden. Die Formel hierfür lautet wie folgt:

                                        (Laufzeit - i + 1)*Anschaffungswert
degressive Abschreibung des Jahres i = -------------------------------------
                                            0.5*Laufzeit*(Laufzeit + 1)

Erstellen Sie ein Programm, mit dem die jährliche Abschreibung bis zum Ende der Laufzeit der Maschine ausgegeben werden kann. Eingabe ist Laufzeit und Anschaffungswert, Ausgabe ist eine Tabelle der jährlichen Abschreibung.

Geschwindigkeit

Um sich nun einmal ein Bild vom Effekt der Geschwindigkeit eines Autos zu machen, sollen Sie ein Programm schreiben, welches zu einer Liste von Geschwindigkeiten von 10 km/h bis 200 km/h in Abstufung von 10 km/h jeweils die Geschwindigkeit in m/s und die Fallhöhe angibt, bei der Sie im freien ungebremsten Fall eben diese Geschwindigkeit erreicht hätten.

Die notwendige Physik ist elementarer Gymnasiallehrstoff: Der freie Fall ist eine gleichförmig beschleunigte Bewegung, die allgemein durch die Formeln

v = b * t + v₀

und

x = b*t²/2 + v₀*t + x₀

für die Geschwindigkeit v und den Ort x beschrieben wird. Darin stehen b für die Beschleunigung und v₀ und x₀ für die initiale Geschwindigkeit und den initialen Ort. Für den freien Fall (idealisiert, ohne Luftwiderstand) ist die Beschleunigung b die Erdbeschleunigung g mit dem Wert von 9.81 Meter pro Sekunde zum Quadrat.

Schiefer Wurf

Schreiben Sie ein C-Programm, das die Wurfweite und Wurfhöhe beim schiefen Wurf berechnet. Das Programm soll den Abwurfwinkel µ (in Grad) und die Abwurfgeschwindigkeit v₀ einlesen.

Die Wurfweite w und die Wurfhöhe h berechnen sich zu:

w = v₀²/g * sin(2*µ)

h = v₀²/2g * (sin(µ))²

g ist die Erdbeschleunigung (9,81 m/s).

Eingabedaten und Ergebnis sollen jeweils mit zwei Stellen hinter dem Komma ausgegeben werden.

Hinweis: #include <math.h> am Anfang des Hauptprogramms ist notwendig, um auf die C-Bibliotheks-Funktion double sin(double x) zugreifen zu können. Außerdem muß im Menü Projekt die Auswahl Optionen angewählt werden. Im Reiter Linkeroptionen muß im Bereich Bibliotheken die Bibliothek math ausgewählt werden.

Pointer

Es ist gegeben:

int x;
int *p;
int **q;

x = 42;
p = &x;
q = &p;

Geben Sie die printf-Anweisungen an, die folgendes ausgeben:

den Wert von x:
die Adresse von x:
die Adresse von p:
den Wert von x unter Verwendung von p:
den Wert von x unter Verwendung von q:
den Wert von p:
den Wert von p unter Verwendung von q:

Zur Vorbereitung gehören:

Sauber gezeichnete Struktogramme und vollständige C-Quellprogramme.
Die Listings und Struktogramme der erfolgreich demonstrierten Programme sind mit Namen und Unterschriften versehen abzugeben.