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

Programmierübungen in "C"

Zur Vorbereitung der Aufgabe gehören: Je nach Komplexität der Aufgabe können einzelne Punkte stark gekürzt werden.


Erste Schritte

Potenzierung

Ein schnelles Potenzierungsverfahren für ganze Zahlen bietet der folgende Algorithmus (WertExponente): 
Potenz = 1
solange Exponent ungleich 0 ist wiederhole:
   Wenn Eponent gerade dann:  Exponent = Exponent/2, Wert = Wert * Wert
                       sonst: Exponent = Exponent-1, Potenz = Potenz * Wert
Setzen Sie das Verfahren in ein C-Programm um und testen Sie es mit verschiedenen Werten.

Zahlentabelle

Schreiben Sie ein Programm, das in Tabellenform Zahlenwerte in dezimal, oktal und hexadezimal (= sedezimal) darstellt. Der Wertebereich der Zahlen soll im Dialog mit dem Benutzer eingegeben werden (untere Grenze, Obere Grenze). Denken Sie an eine Überschriftszeile und die rechtsbündige Ausrichtung der Zahlen. Anmerkung: Sie sollen nicht per Programm in hexadezimal oder oktal umrechnen, sondern diese Arbeit der Funktion printf anvertrauen.

Ausgabe und Eingabe von Zeichen auf dem Bildschirm

  1. Schreiben Sie ein Programm, das ein Zeichen (z.B. '*') in einer Zeile "laufen läßt". Benutzen Sie dazu nur einfache Zeichenausgabe-Funktionen. Um den Vorgang am Bildschirm verfolgen zu können, benutzen Sie als Verzögerungsfunktion den Aufruf der Systemfunktion sleep(sec), die sec Sekunden wartet (Headerdatei: unistd.h). Wenn Ihnen sleep() zu langsam ist, können Sie auch usleep() verwenden. Das "u" steht für "Mikro". Hier wird die Anzahl der Mikrosekunden als Parameter angegeben (max. 1000'000 Mikrosekunden = 1 Sekunde). Das Programm soll abbrechen, wenn das Zeichen am rechten Rand angekommen ist (Bildschirm ist ca. 80 Zeichen breit).

    Hinweis: Wie bei den meisten Betriebssystemen wird auch bei dem im Praktikum verwendeten UNIX die Ausgabe gepuffert. Das heißt, es wird erst etwas ausgegeben, wenn ein Newline kommt oder gar erst, wenn das Programm zuende ist. Sie müssen also dafür sorgen, daß nach jedem Zeichen wirklich auch eine Bildschirmausgabe erfolgt. Sie erreichen dies durch den Funktionsaufruf fflush(stdout); nach jeder Ausgabe.

    Erweitern Sie das Programm außerdem um die Fähigkeit, das Zeichen auch links zu schieben, nämlich dann, wenn es am rechten Rand angekommen ist. Programmende bei Rückkehr des Zeichens zum Zeilenanfang.

  2. Schreiben Sie nun das Programm so um, dass für das Schieben Funktionen verwendet werden:
    1. Verwenden Sie zwei Funktionen: void movright(void) und void movleft(void), die beim Aufruf das Zeichen jeweils um eine Position nach rechts oder links bewegen. Stellen Sie Ihr Programm (genauer: die Funktion main()) so um, daß nun anstelle der Ausgabeanweisungen die FUnktionsaufrufe verwendet werden.
    2. Verwenden Sie danach eine universelle Funktion void movrl(int rl), die abhängig vom Parameter nach rechts oder links schiebt (z.B.: rl == 0 schiebt rechts, rl != 0 schiebt links).
    3. Erweitern Sie das Programm um die Fähigkeit, im Dialog mit dem Benutzer die Schieberichtung zu steuern. So soll ein eingegebenes Leerzeichen ein Rechtsschieben um eine Position bewirken, ein 'b' das Linksschieben. Andere Zeichen sollen direkt wieder ausgegeben werden und ein bestimmtes (z.B. 'e') soll das Programm beenden.

    Hinweis: Auch die Eingabe wird wie die Ausgabe gepuffert. Das heißt, es wird beim Aufruf von getchar() gewartet, bis nach dem Zeichen die Enter-Taste gedrückt wird. Um das zu vermeiden, muß das System in den ungepufferten Betrieb geschaltet werden. Verwenden Sie statt der Funktion getchar() die Funktion getch(), die in der Headerdatei adprakt.h definiert ist. Mit getch() wird das eingegebene Zeichen auch nicht mehr automatisch auf dem Bildschirm geechot, sondern erst durch die Ausgabe in Ihrem Programm.
    Das Programmskelett sieht im Prinzip so aus: 

    #include <stdio.h>
#include <stdlib.h>
#include <adprakt.h>

int main()
  {
  char c = ' ';
  while (c != 'e')
   {
   c = getch();
   switch (c)
     {
     case ' ': moveright();  break; /* rechtsschieben */
     case 'b': moveleft();   break; /* linksschieben */
     case 'e': printf("\a"); break; /* fertig, Beep! */
     default  : putchar(c);   break; /* anderes Zeichen */
     }
   fflush(stdout);
   }
  printf("\n"); /* Newline */
  return 0;
  }

Relais-Steuerung

Verwenden Sie die Unterprogramme zur Relais-Steuerung (siehe auch Praktikumsanleitung), um eine Verkehrsampel zu programmieren. Beachten Sie dabei die Lichterfolge (rot, rot-gelb, grün, gelb, rot, ...) und die Schaltzeiten (kurze Zeit: 2s, lange Zeit: 10s). Welche Schaltzeiten sind lang, welche kurz? Hinweis: Zur Zeitverzögerung dient die Funktion sleep(), deren Parameter die Wartezeit in Sekunden angibt. Die Zuordnung der Lampen ist R1: rot, R2: gelb, R3: grün.

Die Headerdatei adprakt.h stellt zwei Funktionen für das Praktikum zur Verfügung:

int relais(int R1, int R2, int R3, int R4, int R5, int R6, int R7, int R8, char Result[200])

schaltet Relais in der Relaisbox des Rechners "blackhole", der sich im Labor ganz hinten rechts befindet. Die Relaisbox wird für das Praktikum mit dem schwarzen Hauptschalter eingeschaltet (die roten Schalter bitte auf Stellung "ein" belassen). Nach dem Praktikum abschalten nicht vergessen (die Box, nicht den Rechner).

Durch den Wert 1 werden die Relais R1 - R8 eingeschaltet, durch den Wert 0 wieder ausgeschaltet. Als Rückgabewert erhält man den Return-Value der Steuersoftware oder bei einem Fehler (z. B. Box nicht eingeschaltet) -1. Im String "Result" wird die Klartextmeldung der Steuersoftware zurückgegeben.

int relais_off(char Result[200])

Mit diesem Befehl werden alle Relais wieder ausgeschaltet. Als Rückgabewert erhält man den Return-Value der Steuersoftware (Link siehe unten) oder bei einem Fehler -1. Im String "Result" wird die Klartextmeldung der Steuersoftware zurückgegeben.

Das folgende Programm schaltet die rote Lampe ein und aus. 

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <adprakt.h>

int main()
  {
  char Result[200];
  int erg;
  erg = relais(1,0,0,0,0,0,0,0,Result); 
  printf("Erg.: %d Res.: %s\n", erg,Result);
  sleep(1);
  erg = relais(0,0,0,0,0,0,0,0,Result); 
  printf("Erg.: %d Res.: %s\n", erg,Result);
  return(0);
  }
Beachten Sie, daß für die Funktion sleep() die Headerdatei unistd.h zusätzlich benötigt wird.

Hinweis: Da nicht alle gleichzeitig auf die Relais-Fernsteuerung zugreifen können, werden die beiden o. a. Funktionen für die Dauer der Programmentwicklung simuliert, indem man sie zunächst im Programm selbst definiert, z.B. als Ausgabefunktion mit printf für die einzelnen Relais-Werte. Der Rückgabewert kann dann immer 0 sein.

Wenn das Programm dann lauffähig ist, kommentiert man die selbst geschriebenen Funktionen aus und läßt; es auf die realen Relais zugreifen.

Stringausgabe

Entwickeln Sie ein C-Programm, das auf die Eingabe von Abkürzungsbezeichnungen für die Wochentage (in deutsch) mit der Ausgabe des vollen Namens der Wochentage (in englisch) reagiert.

Beispiel für einen Programmdialog:

Geben Sie die Abkürzung eines Wochentages ein
? mon
--> Monday
? mo 
--> No_day
? Dienstag 
-->Tuesday 
? ^D

Hinweise zur Lösung:

Buchstabenhäufigkeit

Schreiben Sie ein Programm, das einen Text einliest und die Häufigkeiten der eingegebenen Zeichen ermittelt (also die einzelnen ASCII-Zeichen zählt). Ist der Text zuende, sollen die Häufigkeiten der Buchstaben 'A' bis 'Z', 'a' bis 'z' und der Ziffern von '0' bis '9' absolut und prozentual ausgegeben werden.

Verwenden Sie zur Speicherung der Häufigkeiten ein Array mit 256 Elementen. Das jeweils aktuelle Eingabezeichen wird als Feldindex verwendet. Zählen Sie gleichzeitig alle eingegebenen Zeichen - dieser Wert wird für die Prozentangabe benötigt.

Temperaturen umrechnen

Entwickeln Sie zwei Funktionen ToFahrenheit und ToCelsius, die eine Temperatur von Fahrenheit nach Celsius und umgekehrt konvertieren. Die Umrechnung erfolgt nach folgenden Formeln:

Celsius nach Fahrenheit: tF = 9 / 5 * tC + 32

Fahrenheit nach Celsius: tC = (tF - 32) * 5 / 9

Welchen Parametertyp und Rückgabewert haben die Funktionen?

Testen Sie die neuen Funktionen, indem Sie in einem Hauptprogramm eine Temperatur zuerst von Celsius nach Fahrenheit und wieder zurück nach Celsius konvertieren und das Ergebnis ausgeben.

Schreiben Sie anschliessend ein Programm, das eine Umrechnungstabelle Fahrenheit nach Celsius für das Intervall von +32 bis +212 Fahrenheit sowie eine Umrechnungstabelle Celsius nach Fahrenheit für das Intervall von -30 bis +50 Celsius ausgibt.

Widerstandswerte

Gemäß DIN 41429 wird der Wert eines elektrischen Widerstands durch einen Farbcode dargestellt: Zwei Ziffern, gefolgt von 0 bis 6 Nullen. Die beiden Ziffern und die Anzahl der Nullen wird durch folgende Farben dargestellt:
z. B. 1200 Ohm = braun-rot-rot. Schreiben Sie ein Programm, das für eine eingegeben Zahlenwert den Farbcode ausgibt.

Es sollen nur Widerstandswerte zwischen 1 Ohm und 5 Megohm berücksichtigt werden.

Tip: Ermitteln Sie die Anzahl der Nullen durch fortlaufende Division durch 10 und zerlegen Sie die verbleibende zweistellige Zahl in Zehner- und Einerstelle.

Maße geometrischer Körper

Schreiben Sie ein Programm, das die Oberfläche und das Volumen der geometrischen Körper Quader, Kugel und Zylinder berechnet. Die Eingabe des Programms besteht aus einer Zeile, welche alle benötigten Angaben enthält: Die Formeln für die Berechnung lauten (Hinweis: Die Konstante PI heißt in C "M_PI" und ist in math.h mit dem Zahlenwert definiert.):

Kaufmännische Zinsrechnung

Ein Kapital K werde T Tage lang mit P% pro Jahr verzinst. Die Zinsen Z werden nach der sogenannten kaufmännischen Zinsformel berechnet: 
                  P       T
        Z = K * ----- * -----
                 100     360
Es ist ein Programm zu schreiben, das aus je drei der vier Größen die vierte Größe berechnet. Das Programm fragt dazu per Menü ab, welcher Wert gesucht wird (Eingabe durch einen Buchstaben: K, P, Z oder T). Danach werden die anderen drei Größen abgefragt und der gewünschte Wert berechnet und ausgegeben. Die Eingaben sollen auf Plausibilität geprüft und gegebenenfalls neu abgefordert werden.

Zahlenraten

Variante 1:

Der erste Mitspieler gibt eine ganze Zahl im Bereich von 0..999 vor. Aufgabe des zweiten Mitspielers ist es diese Zahl mit möglichst wenigen Versuchen zu erraten. Entsprechend der Qualität des Rateversuchs ist ein geeigneter Text mit den Hinweisen "zu klein", "zu groß" oder "stimmt" auszugeben.

Algorithmus: Zerlegung in Einzelprobleme, z. B.:

  1. Ausgabe eines Textes als Aufforderung zur Eingabe der Geheimzahl,
  2. Einlesen des Zahlenwertes durch Funktionsaufruf,
  3. Löschen des Bildschirminhaltes,
  4. Aufforderung einen Rateversuch auszuführen,
  5. Vergleich der Geheimzahl und der geratenen Zahl,
  6. Ausgabe des Textes mit der Qualität des Ratens,
  7. Beenden falls die Zahl richtig war,
  8. Fortsetzen bei Punkt 4, falls die Zahl falsch war.

Bibliotheks-Funktionen: scanf(), printf(), clrscr()

Variante 2:

Die Geheimzahl wird durch den Rechner ermittelt, der eine Zufallszahl im Bereich 0 ... 999 ermittelt. Die Anzahl der Rateversuche wird auf 9 begrenzt.

Algorithmus: (ersetzt den vorhergehenden teilweise)

Bibliotheks-Funktionen: rand(), srand().

Variante 3:

Abhängig von der Nähe des Rateversuchs zur gesuchten Zahl werden Texte ausgegeben (kalt, heiß, wärmer...), die auch von dem vorhergehenden Rateversuch abhängen können.

Präzisieren der Aufgabenstellung für den ersten Rateversuch:

Für Folgeversuche, die im gleichen Intervall liegen:

Algorithmus:
setzt bei (5) ein, der Vergleich muß bezüglich weiterer Schwellen durchgeführt werden, basierend auf der Differenz zwischen Geheimzahl und geratener Zahl;

  1. der Vergleich führt zu einem in einer Variablen festzuhaltenden Ergebnis -> 0 richtig, 1 heiß zu groß, 2 heiß zu klein ....;
  2. der Vergleich mit der vorhergehenden Differenz führt zu weiteren Zuständen der Ergebnisvariablen
  3. für die Textausgabe kann nun die Mehrfachverzweigung basierend auf der Ergebnisvariablen angewandt werden
  4. oder diese als Index für eine Texttabelle (Array von Strings) verwendet werden.

Münzautomat

Erstellen Sie ein ANSI-C-Programm, das einen Münzautomaten simuliert. Dazu geben Sie einen beliebigen Betrag zwischen 1 Euro und 10 DM vor (entweder durch Eingabe oder als Zufallszahl). Der Betrag kann mit verschiedenen Münzen "abgezahlt" werden: 
        2 Euro
        1 Euro
        50 Cent
        10 Cent
         5 Cent
Die Münzen werden in beliebiger Reihenfolge "eingeworfen" (durch Eingabe im Programm) und der Restbetrag jeweis angezeigt. Überzahlen soll nicht möglich sein. Die Anzeige soll in großen Ziffern erfolgen und wie im folgenden Beispiel aussehen: 
      #####   ##### #####
      #   #       # #
      #####      #  ####
      #   #     #       #
      ##### *   #   ####
Tipp: Rechnen Sie mit Cent (1 Euro wird dann als 100 und 2 Euro als 200 eingegeben).

Die Bildschirmausgabe soll als Funktion formuliert werden, die eine Integerzahl als Eingabeparameter besitzt und diese in der oben angegebenen Form auf dem Bildschirm ausgibt. Der Dezimalpunkt, dargestellt durch ein Sternchen, ist fester Bestandteil der Ausgabe und nicht Kennzeichen einer float-Variablen.

Hinweise zur Lösung:

Die Vereinbarung der Ziffern ist unter /home/praktikum/ziff.h zu finden. Sie lautet: 
char * ziff[10][5] = 
    { {" ### ",
       "#   #",
       "#   #",
       "#   #",
       " ### " },

      {"   ##",
       "    #",
       "    #",
       "    #",
       "    #" },

      {"#### ",
       "    #",
       " ### ",
       "#    ",
       "#####" },

      {"#### ",
       "    #",
       " ### ",
       "    #",
       "#### " },

      {"#  # ",
       "#  # ",
       "#####",
       "   # ",
       "   # " },
       
      {"#####",
       "#    ",
       "#### ",
       "    #",
       "#### " },

      {" ####",
       "#    ",
       "#####",
       "#   #",
       "#####" },

      {"#####",
       "    #",
       "   # ",
       "  #  ",
       "  #  " },

      {"#####",
       "#   #",
       "#####",
       "#   #",
       "#####" },

      {"#####",
       "#   #",
       "#####",
       "    #",
       "#### " }};
(Sie können die Definition auch per "Cut-and-paste" von der Webseite übernehmen). Die Ziffer j (j = 0...9) ist durch folgendes Programmstück zum Testen darstellbar: 
    for (i=0; i<5; i++)
      printf("%s ",ziff[j][i]);

Arbeiten mit Binärdateien

Zum Speichern von Daten für das Telefonverzeichnis des Fachbereichs wird die folgende Struktur definiert: 
struct Adresse
  {
  char Name[30];
  char Vorname[30];
  int Raumnummer;
  int Telefon;
  };
Gegeben ist eine Binärdatei namens "teldat", die Datensätze vom Struktur-Typ "Adresse" enthält.

1. Schreiben Sie eine Funktion tabelle, welche die Binärdatei zum Lesen öffnet, und alle Datensätze nacheinander als formatierte Tabelle ausdruckt. Die Tabelle soll folgendes Aussehen besitzen: 


+-----------------------------------------+------+------+
| Name                                    | Raum | Tel. |
+-----------------------------------------+------+------+
| Dr. Martin Bechteler                    | 4038 | 3418 |
| Dr. Gerd Becker                         | 4036 | 3416 |
| Dr. Maximilian Bleicher                 | 2051 | 3467 |
  ...
Die Funktion hat folgenden Prototyp: 
int tabelle(char dateiname[]);
Sie gibt 0 zurück, wenn das öffen der Datei fehlschlägt, sonst 1.

2. Schreiben Sie eine Funktion kopiere, welche die Binärdatei mit den Adressen (also die Quelldatei) zum Lesen öffnet und gleichzeitig eine weitere Binärdatei, die Zieldatei, zum Schreiben öffnet. Die zweite Binärdatei soll Datensätze enthalten, die folgender Struktur genügen: 

struct NeueAdresse
  {
  char Name[30];
  int Telefon;
  };
Aufgabe der Funktion ist es, jeweils einen Datensatz aus der Quelldatei zu lesen, die Inhalte in einen Datensatz der Zieldatei zu übertragen und diesen dann in die Zieldatei zu schreiben. Die Funktion hat folgenden Prototyp: 
int kopiere(char quelldateiname[], char zieldateiname[]);
Sie gibt 0 zurück, wenn das öffen der Dateien fehlschlägt, sonst 1.

Entwerfen Sie ein geeignezes Hauptprogramm zum Testen der FUnktionen.

Fahrstuhl

In einem Hochhaus mit 20 Stockwerken fährt ein Aufzug. Im Aufzug gibt es 20 Knöpfe zur Wahl des Fahrtzieles, und auf jedem Stock gibt es einen Knopf zur Anforderung des Fahrstuhles.
Ohne auf die faire Behandlung der Aufzugsbenutzer zu achten, entwickeln Sie einen einfachen Algorithmus für einen Fahrstuhl, der, solange es geht, seine Fahrtrichtung beibehält, bis in seine augenblickliche Fahrtrichtung keine Anforderungen mehr existieren, woraufhin er die Fahrtrichtung wechselt, oder aber, falls gerade keine Anforderungen anliegen, einfach auf dem augenblicklichen Stockwerk bleibt und auf die nächste Anforderung wartet. Es wird angenommen, die Stockwerke seien von 1 bis 20 durchnummeriert.
Nehmen Sie folgende Grundaktionen an: Simulieren Sie den Aufzug mit Hilfe von Bildschirm und Tastatur.

Iteration, Abfrage und Funktion

Sie sollen eine mathematische Funktion double mysin (double x); entwerfen und programmieren, die mittels der Taylorreihenentwicklung für ein hinreichend großes n:

für ein gegebenen Wert x den Sinus berechnet.

Die Genauigkeit des über die Reihenentwicklung gewonnen Sinuswertes hängt von der Anzahl m der beteiligten Summanden [..] ab. Diese Anzahl m ist abhängig vom Wert x und im voraus nur schwer abzuschätzen.

Wir geben einen Wunschfehler vor und berechnen die Summe, durch Addition weiterer Summanden [..], solange bis die gewünschte Genauigkeit erreicht ist. D. h.: Ist der jeweils hinzuzufügende Betrag des Summanden kleiner oder gleich dem Wunschfehler, so ist die gewünschte Genauigkeit erreicht.

Wunschfehler: 10 -10

Auffrischung:

Der Sinus ist eine periodische Funktion. Seine Funktionswerte kehren alle x = x + 2*PI wieder. D. h. der relevante Definitionsbereich von sin x liegt zwischen 0 und 2*PI. Ist der x-Wert größer als 2*PI, so kann vor der Reihenberechnung, das überzählige Vielfache von 2*PI von x abgezogen werden, bis der Wert wieder im o. g. relevanten Definitionsbereich ist.

Häusliche Vorbereitung

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.

Bringen Sie Ihr Programm zum Laufen. Die Differenzen zur C-Bibliotheksfunktion sollten sich maximal in der Größenordnung 10-12 bewegen.

Magische Quadrate

Ein magisches Quadrat ist eine quadratische Anordnung mit n Zeilen und n Spalten von Zahlen derart, dass die Summe der Zahlen in einer beliebigen Zeile, Spalte, oder in der Hauptdiagonale alle gleich sind.

492
357
816

Wenn n ungerade ist, kann man ein magisches Quadrat folgendermaßen erstellen. Im Feld Q[i][j] (i=1..n, j=1..n) wird eingetragen:

  1. Setzen Sie k = j - i + (n -1)/2 und m = 2*j - i.
  2. Wird k >= n, ersetzen Sie k durch k - n und fahren Sie fort bei Schritt 4.
  3. Wird k < 0, ersetzen Sie k durch k + n.
  4. Wird m > n, so ersetzen Sie m durch m - n und fahren Sie fort bei Schritt 6.
  5. Wird m <= 0, ersetzen Sie m durch m + n.
  6. Ergebnis: Q[i][j] = K*n + m.

Erstellen Sie ein Programm, das mit diesen Regeln bei Benutzereingabe von ungeradem n ein magisches Quadrat erzeugt, das in einem Array gespeichert und dann am Bildschirm schön formatiert ausgegeben wird.

Textanalyse

Ein über die Standardeingabe einzugebender Text soll zeichenweise gelesen und analysiert werden.

Erstellen Sie ein ANSI-C-Programm, mit dem

des Eingabetextes ermittelt werden kann. Unter einem Wort sei dabei jede Zeichenfolge, die mit einem Buchstaben oder Underscore ('_') beginnt, nur aus Buchstaben, Ziffern und den Underscore ('_') besteht und von beliebigen Steuer- oder Sonder-Zeichen (nicht aber Ziffern) begrenzt wird, verstanden. Beachten Sie, daß nach dieser Definition z. B. die Zeichenfolge ;2abc% kein Wort enthält.

Hinweise zur Lösung: