Programmieren mit Harald R. Haberstroh

Implementieren Sie eine einfache dynamische Speicherverwaltung, die nach dem in der folgenden Skizze gezeigten Prinzip funktioniert.

Diese Speicherverwaltung soll es ermöglichen, Speicher in beliebiger Reihenfolge zu allozieren und wieder freizugeben. Siehe auch Dynamische Speicherverwaltung
Schreiben Sie ein Modul heap für die Speicherverwaltung selbst, welches folgende Funktionen enthält (exportiert):

• void *halloc(size_t size); zum Anfordern von Speicher der Größe size
• void hfree(void *p); zum Freigeben des Speichers, auf den der Zeigern p zeigt.

Erstellen Sie eine weitere Version des Moduls heap, welches bei jedem Aufruf von halloc() bzw. hfree() den gesamten Speicher in lesbarer Form auf stderr ausgibt, damit man das Allozieren der Speicherblöcke sehen kann (die Größe des Heaps sollte dabei eher klein gewählt werden!).
Schreiben Sie weiters ein Modul, welches Ihre Speicherverwaltung testet durch Anfordern von Speicher, belegen und lesen des allozierten Speichers und wieder Freigeben des Speichers in verschiedenen Varianten.
Erstellen Sie dazu eine Liste von Testfällen und beschreiben Sie das Ergebnis der Tests (die Speicherauszüge bekommen Sie mit obiger Variante des Moduls).
Beispiele von Testfällen:
n. Test: allozieren eines Strings der Länge HEAPSIZE - sizeof(heap_t), füllen des Strings mit lauter 'A' und ausgeben des Strings. OK
n+1. Test: freigeben des Speichers aus Test n. OK

Zu jedem Test ist anzugeben, ob der Test erfolgreich war. Falls ein Test nicht erfolgreich war, so ist festzustellen, warum und ggf. der Fehler zu beheben. Wird am Programm etwas verändert, so müssen alle Tests noch einmal gemacht werden!
Schreiben Sie ein passendes Makefile, mit dem man alternativ die normale Variante von heap und die Testvariante von heap erzeugen kann!
Organisieren Sie sich in Kleingruppen und versuchen Sie die einzelnen Funktionen gemeinsam zu entwerfen und zu programmieren. Welche Hilfsfunktionen braucht z.B. das halloc()?
Erweitern Sie die Speicherverwaltung um eine "Garbage Collection", die freie Speicherbereiche, die hintereinanderliegen zusammenfasst.
Erstellen Sie eine geeignete Verzeichnisstruktur und verwenden Sie CVS.
Tauschen Sie die Module mit anderen Gruppen aus (das müßte ganz einfach sein, da die Schnittstellen immer gleich sind (s.o.).
Abgabe:
Nennen Sie das Projekt 5ad-name-heap bzw. 5bd-name-heap und checken Sie es ein.
Beantworten Sie weiters folgende Fragen (die Antworten müssen in der Datei heap.txt gespeichert werden):

1. Was passiert, wenn man einen String der Länge n alloziert und einen String der Länge n speichert?
2. Was passiert, wenn man einen String der Länge n alloziert und einen String der Länge n + 1 speichert?
3. Sie allozieren einen String der Länge 11 und speichern "0123456789" und geben den String wieder frei. Danach allozieren Sie einen String der Länge 20 und geben diesen String aus. Was passiert? (die Speicheranforderungen bzw. die Freigabe muss unmittelbar hintereinander erfolgen).
4. Welche Speicheranforderungen benötigen mehr Speicher - 10 Strings der Länge 100 oder 100 Strings der Länge 10? Begründen Sie die Antwort.
5. Wie könnten Sie im Modul heap sicherstellen, dass bei einem Aufruf von hfree(p); der Parameter p tatsächlich auf einen mit halloc() allozierten Speicherbereich zeigt?

heap.txt muss auch die Liste der Testfälle mit ihren Ergebnissen enthalten.
Geben Sie einen Ausdruck der ausgearbeiteten Fragen ab!

Labels: Aufgabe, C, PR5

Erstellen Sie ein Python-Programm zum Darstellen von Daten in einem Diagramm. Die Daten stammen aus einer Textdatei mit Zeilen mit Datum und Wert. Zum Beispiel:

10.9.2010 70
11.10.2010 36
10.11.2010 50
11.11.2010 70
1.12.2010 30

Auf der X-Achse soll das Datum aufgetragen werden und auf der Y-Achse der jeweilige Wert.

Wählen Sie einen passenden Maßstab. Das erste Datum soll der Null-Punkt auf der X-Achse sein.
Verwenden Sie die Turtle-Grafik (from turtle import *). Hilfe zur Turtle-Grafik finden Sie in einer Python-Konsole mit:

import turtle
help(turtle)

Damit Sie passende Testdaten bekommen, schreiben Sie auch einen Testdatengenerator, der 3 Parameter auf der Kommandozeile hat:

1. Name der Datei
2. Anfangsdatum
3. Anzahl der Datensätze

Die Datumswerte generierern Sie so, dass, beginnend mit dem Anfangsdatum, immer eine zufällige Anzahl von Tagen zwischen 1 und 31 dazugezählt werden soll. Die Werte sollen zufällige ganze Zahlen zwischen 0 und 100 (inclusive) sein.

Nennen Sie das Projekt 2x-name-python-diagramm, den Testdatengenerator testdaten.py und das Diagramm diagramm.py.

Labels: Aufgabe, POS1-2, Python

Man kann die Wurzel einer Zahl berechnen mit folgender Formel

x_n = (x_n-1 + a / x_n-1) / 2

Man beginnt damit, dass a und x₀ gleich der Zahl, aus der man die Wurzel ziehen will, setzt und x₁ berechnet. Dann berechnet man x₂ usw. bis sich die beiden letzten Werte nur mehr gering unterscheiden (z.B. die Differenz kleiner 0,0000001 ist).

Schreiben Sie eine Funktion wurzel(zahl, genauigkeit), welche nach obiger Methode die Wurzel berechnet.

Erstellen Sie ein Programm wurzel.py, welche eine Tabelle der Wurzeln der Zahlen 1 bis 20 bei den Genauigkeiten 0.01, 0.0001 sowie 0.0000001 ausgibt:

 1:  1.0000000  1.0000000  1.0000000
 2:  1.4142157  1.4142136  1.4142136
 3:  1.7320508  1.7320508  1.7320508
 4:  2.0000001  2.0000000  2.0000000
 5:  2.2360689  2.2360680  2.2360680
 6:  2.4494944  2.4494897  2.4494897
 7:  2.6457670  2.6457513  2.6457513
 8:  2.8284271  2.8284271  2.8284271
 9:  3.0000000  3.0000000  3.0000000
10:  3.1622777  3.1622777  3.1622777
11:  3.3166248  3.3166248  3.3166248
12:  3.4641017  3.4641016  3.4641016
13:  3.6055514  3.6055513  3.6055513
14:  3.7416576  3.7416574  3.7416574
15:  3.8729837  3.8729833  3.8729833
16:  4.0000006  4.0000000  4.0000000
17:  4.1231067  4.1231056  4.1231056
18:  4.2426425  4.2426407  4.2426407
19:  4.3589018  4.3588989  4.3588989
20:  4.4721402  4.4721360  4.4721360

Labels: Aufgabe, POS1-1, Python

Prüfen, ob durch die Angabe dreier Längen ein Dreieck gegeben ist.
Zwei Seiten müssen immer länger als die dritte sein. Man muss dies für alle Möglichkeiten prüfen, denn z.B.
a = 3, b = 4, c = 1
Da stimmt zwar a + b > c (7 > 1) und b + c > a (4 > 3), jedoch nicht a + c > b (4 == 4)!
Bei der Lösung wird eine Schleife verwendet.

def ist_dreieck(a, b, c):
    """liefert True, wenn durch a, b und c ein gültiges Dreieck definiert
    ist"""
    i = 3
    while i > 0:
        if a + b <= c:
            return False # kein Dreieck
        a, b, c = b, c, a
        i = i - 1
    return True

Man könnte das Problem natürlich auch durch logische Verknüpfung der Prüfungen lösen:

def ist_dreieck(a, b, c):
    """liefert True, wenn durch a, b und c ein gültiges Dreieck definiert
    ist"""
    if a + b > c and b + c > a and c + a > b:
        ret = True
    else:
        ret = False
    return ret

Oder gleich so:

def ist_dreieck(a, b, c):
    """liefert True, wenn durch a, b und c ein gültiges Dreieck definiert
    ist"""
    return a + b > c and b + c > a and c + a > b

Bei der zweiten Aufgabe soll geprüft werden, ob durch zwei Seiten und einem Winkel ein Quadrat gegeben ist. Die beiden Seiten müssen gleich lang sein (und größer 0) und der Winkel 90°:

def ist_quadrat(a, b, w):
    """liefert True, wenn durch a und b sowie dem Winkel w ein 
    Quadrat definiert ist"""
    quadrat = False
    if a > 0:
        if a == b:
            if w == 90:
                quadrat = True
    # else entfällt, da die Variable quadrat schon mit False vorbelegt ist.
    return quadrat

Oder wieder kürzer mit logischer Verknüpfung:

def ist_quadrat(a, b, w):
    """liefert True, wenn durch a und b sowie dem Winkel w ein 
    Quadrat definiert ist"""
    return a == b and w == 90 and a > 0

Die Schaltjahrprüfung könnte so erfolgen:

def ist_schaltjahr(jahr):
    """liefert True, wenn das gegebene Jahr ein Schaltjahr ist.
    Seit Ende 1582 gilt der Gregorianische Kalender, bei dem folgende Regel
    für die Schaltjahrbestimmung anzuwenden sind:
        In allen Jahren, deren Jahreszahl durch vier teilbar ist, ist der 
        29. Februar ein Schalttag und damit ist dieses Jahr ein Schaltjahr.
        Eine Ausnahme bilden allerdings die vollen Jahrhundertjahre 1700, 
        1800, 1900 usw., auch Säkularjahre genannt. Hiervon erhalten nur 
        diejenigen einen Schalttag, deren Jahreszahl durch 400 teilbar ist. 
        Jedes vierte Säkularjahr ist somit ein Schaltjahr.
    Für alle Jahre <= 1582 liefert die Funktion False, weil da das
    Schaltjahr nicht definiert ist, sonst gilt obige Regel."""
    if jahr <= 1582:
        schaltjahr = False
    elif jahr % 400 == 0:
        schaltjahr = True
    elif jahr % 100 == 0:
        schaltjahr = False
    elif jahr % 4 == 0:
        schaltjahr = True
    else:
        schaltjahr = False
    return schaltjahr

Jahre bis 1582 können keine Schaltjahre sein, da der Gregorianische Kalender erst im Jahr 1582 definiert wurde. Zum Test der Schaltjahrprüfung noch ein paar Worte, aber zunächst die Testfunktion, die ein paar Jahreszahlen prüft, von denen man weiß, dass sie kein Schaltjahr sind sowie Zahlen, bei denen bekannt ist, dass sie Schaltjahre sind:

def test_ist_schaltjahr():
    for jahr in (1000, 1580, 1581, 1582, 1900, 1999, 2003):
        assert not ist_schaltjahr(jahr)
    for jahr in (1996, 2000, 2004):
        assert ist_schaltjahr(jahr)
    print("ist_schaltjahr ok")

Die Anweisung assert ist für Programmierer und dient zum Prüfen der Bedingung, die gleich dahinter folgt, gedacht. Zum Beispiel:

assert 3 < 4

Die Bedingung ist wahr, daher läuft das Programm weiter. Ist die Bedingung hingegen falsch, so wird das Programm mit einer Fehlermeldung abgebrochen:

>>> assert 3 > 4
Traceback (most recent call last):
  File "", line 1, in 
    assert 3 > 4
AssertionError

Zusätzlich kann ein Text als Fehlermeldung angegeben werden:

>>> assert 3 > 4, "3 ist nicht größer als 4"
Traceback (most recent call last):
  File "", line 1, in 
    assert 3 > 4, "3 ist nicht größer als 4"
AssertionError: 3 ist nicht größer als 4

Angewendet auf obige Testfunktion bedeutet das, dass immer, wenn assert not ist_schaltjahr(jahr) die Funktion ist_schaltjahr(jahr) den Wert False leifern muss und wenn assert ist_schaltjahr(jahr) steht, True geleifert werden muss, damit das Programm nicht abgebrochen wird. Der nächste Punkt ist die for jahr in (1000, 1580, 1581, 1582, 1900, 1999, 2003):-Zeile. Die Variable jahr bekommt der Reihe nach die Werte 1000, 1580, 1581, 1582, 1900, 1999, 2003 und der eingerückte Code-Block (die eine Zeile) wird ausgeführt. Das ist die for-Schleife, welche im Buch im Kapitel 7 auch erklärt wird. Die Funktion test_ist_schaltjahr() prüft also zunächst ein paar Jahre, die kein Schaltjahr sind und ein paar Schaltjahre. Die Fibonaccizahlen können wie folgt ermittelt werden:

def fib(n):
    """liefert die Fibonaccizahl zu n. Die Zahlen sind wie definiert:
        fib(0) -> 0
        fib(1) -> 1
        fib(2) -> 1
        fib(3) -> 2
        fib(4) -> 3
        fib(5) -> 5
        fib(6) -> 8
        ...
        fib(10) -> 55
        ...
        fib(15) -> 610"""
    f = 0
    a = 0
    b = 1
    i = 0
    while i < n:
        f = a + b
        b, a = a, f
        i += 1
    return f

Für n = 0 und n = 1 sind die (Anfangs-)Werte vordefiniert. fib(0) = 0 und fib(1) = 1. Danach gilt die Regel, dass die n. Fibonaccizahl die Summe der beiden Vorgänger ist, also fib(n - 1) + fib(n - 2) (Siehe dazu auch Wikipedia: Fibonacci-Folge). Die Variable f hat immer den Wert der aktuellen Fibonaccizahl und ist daher mit 0 initialisiert. Die Variable a und b haben immer den Wert der beiden Vorgänger. Sie können das leicht sehen, wenn Sie print(...)-Anweisungen einfügen und sich dadurch den Ablauf der Berechnung anzeigen lassen:

def fib(n):
    """liefert die Fibonaccizahl zu n."""
    f = 0
    a = 0
    b = 1
    i = 0
    while i < n:
        f = a + b
        print(i, ":  f =", f, "a =", a, "b =", b) # Testausgabe
        b, a = a, f
        i += 1
    return f

print(fib(10))

..gibt dann folgendes aus:

0 :  f = 1 a = 0 b = 1
1 :  f = 1 a = 1 b = 0
2 :  f = 2 a = 1 b = 1
3 :  f = 3 a = 2 b = 1
4 :  f = 5 a = 3 b = 2
5 :  f = 8 a = 5 b = 3
6 :  f = 13 a = 8 b = 5
7 :  f = 21 a = 13 b = 8
8 :  f = 34 a = 21 b = 13
9 :  f = 55 a = 34 b = 21
55

Die Ausgabe einer Tabelle mithilfe der Funktion fib() ist einfach (oder doch etwas kompliziert, weil die eckigen Klammern dazukommen):

def fibtab(n):
    """erzeugt eine Tabelle der Fibonaccizahlen bis inclusive n.
    z.B. gibt fibtab(10) folgendes aus:
        [0, 1, 1, 2, 3, 5, 8]
    oder fibtab(100):
        [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    Hinweis:
        verwenden Sie als Zeilenumbruch ", " beim print, also
            print(wert, end=', ')
        außer natürlich beim letzten Wert, hier ist "]" gefordert.
    """
    i = 0
    print("[", end = "")
    f = fib(i)
    while f <= n:
        print(f, end = "")
        i += 1
        f = fib(i)
        if f > n:
            print("]")
        else:
            print(", ", end = "")

Wir müssen sicherstellen, dass zunächst "[" ohne Zeilenumbruch ausgegeben wird. Die Funktion print(...) hat einen optionalen Parameter end, der angibt, was zum Schluss ausgegeben werden soll. Standardmäßig ist das "\n", was einen Zeilenumbruch bewirkt. Setzt man den Wert end = "", so wird ein Leerstring, also nichts, ausgegeben. In der Schleife muss man noch prüfen, ob man das Ende erreicht hat und in diesem Fall "]" (mit Zeilenumbruch) ausgibt. Im Normalfall wird ein Komma ohne Zeilenumbruch ausgegeben (letzte Zeile). Beachten Sie, dass der Parameter n hier die Grenze der Fibonaccizahl angibt und nicht die wievielte (wie bei fib(n)). Die Lösung zum Beispiel, die Summe der Vielfachen von 3 und 5 kleiner als ein Maximum:

def sum_3_5(max):
    """
    bilde Summe der Vielfachen von 3 und 5 kleiner als max.
    Beispielsweise liefert sum_3_5(10) 23, weil
        die Vielfachen von 3 < 10 sind
            3 + 6 + 9 = 18
        die Vielfachen von 5 < 10 sind
            5
        18 + 5 = 23
    sum_3_5(20) liefert 78, weil
        3+  6+9+   12+15+18=63
          5+    10+        =15 (15 ist in obiger Liste schon enthalten!)
    sum_3_5(25) liefert 143, weil
        3+  6+9+   12+   18+   21+24=93 (Vielfache von 5 stehen darunter)
          5+    10+   15+   20      =50
    sum_3_5(100) liefert 2318 (ohne Beweis)
    """
    summe = 0
    i = 0
    while i < max:
        if i % 5 == 0:
            summe += i
        elif i % 3 == 0:
            summe += i
        i += 1
    return summe

Die Laufvariable i wird immer dann zur summe dazugezählt, wenn sie durch 5 teilbar ist oder wenn sie durch 3 teilbar ist. Der Operator % berechnet den Rest der Division. Ist der Rest 0, so ist die erste durch die zweite Zahl teilbar. Das Beispiel zum finden des nächstkleineren bzw. gleichen Quadrats kann so mit einer Probiermethode gelöst werden:

def minquad(zahl):
    """finde die nächstkleinere oder gleichgroße ganze Zahl, die eine 
    Quadratzahl ist. Beispiele:
        minquad(16) -> 16 (weil 4 * 4 = 16 <= 16)
        minquad(24) -> 24 (weil 4 * 4 = 16 <= 14)
        minquad(25) -> 25 (weil 5 * 5 = 25 <= 25)
        minquad(26) -> 25 (weil 5 * 5 = 25 <= 26)
    """
    i = 0
    mq = 0
    while i ** 2 <= zahl:
        mq = i ** 2
        i += 1
    return mq

i ** 2 bedeutet i². Man könnte natürlich auch i * i schreiben. Diese Funktion prüft einfach sukzessive alle Quadrate, bis eines gefunden wurde, das größer als die gegebene Zahl ist. Der Wert davor (die Variable mq) ist natürlich das Ergebnis, weil das der größte Wert war, für den die Bedingung gilt. Es geht natürlich schneller und einfacher, wenn man sich eine Formel überlegt:

from math import sqrt
from math import floor
def minquad(zahl):
    """finde die nächstkleinere oder gleichgroße ganze Zahl, die eine 
    Quadratzahl ist. Beispiele:
        minquad(16) -> 16 (weil 4 * 4 = 16 <= 16)
        minquad(24) -> 16 (weil 4 * 4 = 16 <= 24)
        minquad(25) -> 25 (weil 5 * 5 = 25 <= 25)
        minquad(26) -> 25 (weil 5 * 5 = 25 <= 26)
    """
    return int(floor(sqrt(zahl))) ** 2

Die Funktion floor(x) liefert die nächstkleinere ganze Zahl zu x (bei positiven Zahlen schneidet dir Funktion die Nachkommastellen der übergebenen Zahl ab). Z.B:

>>> from math import floor
>>> floor(3.14)
3
>>> floor(3)
3
>>> floor(-3.14)
-4

Wenn man die nächstkleinere ganze Zahl der Wurzel quadriert, hat man das gewünschte Ergebnis. Die Turtle-Funktion zum Dreieckzeichnen könnte wie folgt aussehen und braucht nicht weiter erklärt werden:

def dreieck(a, w):
    """zeichnet ein gleichseitiges Dreieck der Seitenlänge a, gedreht um
    den Winkel w. w = 0 bedeutet, dass die eine Seite horizional ist. w = 90
    bedeutet, dass das Dreieck nach LINKS um 90° gedreht ist, d.h. eine Seite
    ist vertikal.
    Das Dreieck soll rechts neben des angegebenen Punktes gezeichnet werden.
    """
    # nehme an Turtle sieht nach oben (wie auch beim Starten)
    right(90 - w)
    pendown()
    for i in range(3):
        forward(a)
        left(120)
    penup()
    left(90 - w)

Um ein Dreieck an eine bestimmte Position zu setzen, kann zusätzlich die Funktion setpos(x, y), welche die Turtle an die Postion x,y setzt, verwendet werden:

def dreieck_an_pos(a, w, x, y):
    """zeichnet ein Dreieck mit Hilfe der Funktion dreieck(a, w) an der 
    Position x, y."""
    penup()
    setpos(x, y)
    dreieck(a, w)

Abgesehen von den Turtle-Funktionen können Sie die Funktionen direkt auf der Website http://codepad.org testen. Dort können Sie auch andere Programmiersprachen probieren. Die Python-Version ist leider nicht aktuell, daher könnte es sein, dass einiges doch nicht direkt so funktioniert. Diese einfachen Beispiele funktionieren aber.
Hier ist zu minquad(zahl) zu sehen:

Labels: Lösung, POS1-1, Python

Datumsberechnungen sind immer wieder eine Quelle großer langwieriger, fehleranfälliger Programmteile. Vor allem in Sprachen, die solche Datumsoperationen nicht unterstützen. Sie sind auch immer wieder geeignet, Programmieren zu üben. Hier die Musterlösung zu einem einfachen Kalenderprogramm in C, bei dem ein Großteil der Datumsfunktionen selbstgestrickt sind. Viel Spaß damit!
Verwendung:
Ohne Parameter gibt es einfach das aktuelle Monat mit Markierung < 2> für den heutigen Tag und : 8: als Markierung für österreichische Feiertage. Danach wird die Liste der Feiertage ausgegeben.

$ ./cal 
Dezember 2010

    Montag       6  13  20  27     
  Dienstag       7  14  21  28     
  Mittwoch   1 : 8: 15  22  29     
Donnerstag < 2>  9  16  23  30     
   Freitag   3  10  17 :24::31:    
   Samstag   4  11  18 :25:        
   Sonntag : 5::12::19::26:    

 5.12. 2. Advent
 8.12. Maria Empfängnis
12.12. 3. Advent
19.12. 4. Advent
24.12. Heiligabend
25.12. Christtag
26.12. Stefanitag
31.12. Silvester :-)

Here comes the Source...

/*
 * File:    cal.c
 *
 * Zweck:   Kalenderprogramm
 *          ...für ein gegebenes Monat.
 *          mit/ohne argc/argv
 *
 * Autor:   Harald Haberstroh
 *
 * Algorithmus:
 *
 * History: 2002-09-29
 *          2003-10-15, Feiertage + Argumente von main()
 *          2004-11-05, Liste der Feiertage
 */

/*--------------------------- includes ------------------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

/*--------------------------- defines -------------------------------*/
#define  WOCHENTAG   3                 /* Wochentag des 1.1.1582 */
#define  MONTAG 0
#define  DIENSTAG 1
#define  MITTWOCH 2
#define  DONNERSTAG 3
#define  FREITAG 4
#define  SAMSTAG 5
#define  SONNTAG 6

/*--------------------------- typedefs ------------------------------*/

/*--------------------------- globals -------------------------------*/
enum {
   KEIN = 0,
   NEUJAHR,
   HL3KOENIGE,
   ASCHERMITTWOCH,
   PALMSONNTAG,
   KARFREITAG,
   OSTERSONNTAG,
   OSTERMONTAG,
   STAATSFEIERTAG,
   MUTTERTAG,
   PFINGSTSONNTAG,
   PFINGSTMONTAG,
   DREIFALTIGKEITSSONNTAG,
   FRONLEICHNAM,
   MARIAHIMMELFAHRT,
   NATIONALFEIERTAG,
   REFORMATIONSTAG,
   ALLERHEILIGEN,
   ALLERSEELEN,
   MARIAEMPFAENGNIS,
   ADVENT1,
   ADVENT2,
   ADVENT3,
   ADVENT4,
   HEILIGABEND,
   CHRISTIANI,
   STEFANI,
   SILVESTER
};

/*-------------------------- prototypes -----------------------------*/
void printFeiertage(int jahr, int monat);
int tagemonat( int jahr, int monat );
int sonntag( int jahr, int monat, int tag );
void tag2datum( int tagzahl, int *jahr, int *monat, int *tag );
void ostern( int jahr, int *monat, int *tag );
int feiertag(int jahr, int monat, int tag);
int anzProMonat(int jahr, int monat);
void printcal(int start, int anz, int heute, int monat, int jahr);
int schaltjahr( int Jahr );
int Anzahl_Tage( int Jahr, int Monat, int Tag );

/*----------------------------- main --------------------------------*/
int main( int argc, char *argv[] )
{
   int tage, tag, monat, jahr, start;
   struct tm *zeit;
   time_t   sec;

   if (argc == 2 && strcmp(argv[1], "-i") == 0)
   {                                   /* interaktiv */
      printf("Jahr> ");scanf("%d", &jahr);
      printf("Monat> ");scanf("%d", &monat);
      printf("Tag (0 für kein bestimmter)> ");scanf("%d", &tag);
      if (tag == 0)
      {
         tag = 1;
         if (1 <= monat && monat <= 12 &&
             1582 < jahr && jahr < 3000)
         {
            tage = Anzahl_Tage( jahr, monat, 1);
            start = (tage + WOCHENTAG) % 7;
            printcal(start, anzProMonat(jahr, monat), 0, monat, jahr);
            return 0;
         }
         else
         {
            fprintf(stderr, "Monat zwischen 1 und 12 und Jahr zwischen "
                            "1583 und 2999\n");
            return 2;
         }
      }
      if (1 <= monat && monat <= 12 &&
          1582 < jahr && jahr < 3000 &&
          1 <= tag && tag <= anzProMonat(jahr,monat))
      {
         tage = Anzahl_Tage( jahr, monat, 1);
         start = (tage + WOCHENTAG) % 7;
         printcal(start, anzProMonat(jahr, monat), tag, monat, jahr);
         return 0;
      }
      else
      {
         fprintf(stderr, "Monat zwischen 1 und 12 und Jahr zwischen "
                         "1583 und 2999\n"
                         "[Tag zwischen 1 und Anzahl für dieses Monat]\n");
         return 2;
      }
   }
   else if (argc == 3)                      /* Monat, Jahr */
   {
      monat = atoi(argv[1]);
      jahr = atoi(argv[2]);
      tag = 1;
      if (1 <= monat && monat <= 12 &&
          1582 < jahr && jahr < 3000)
      {
         tage = Anzahl_Tage( jahr, monat, 1);
         start = (tage + WOCHENTAG) % 7;
         printcal(start, anzProMonat(jahr, monat), 0, monat, jahr);
         return 0;
      }
      else
      {
         fprintf(stderr, "Monat zwischen 1 und 12 und Jahr zwischen "
                         "1583 und 2999\n");
         return 2;
      }
   }
   else if (argc == 4)                 /* ganzes Datum */
   {
      monat = atoi(argv[2]);
      jahr = atoi(argv[3]);
      tag = atoi(argv[1]);
      if (1 <= monat && monat <= 12 &&
          1582 < jahr && jahr < 3000 &&
          1 <= tag && tag <= anzProMonat(jahr,monat))
      {
         tage = Anzahl_Tage( jahr, monat, 1);
         start = (tage + WOCHENTAG) % 7;
         printcal(start, anzProMonat(jahr, monat), tag, monat, jahr);
         return 0;
      }
      else
      {
         fprintf(stderr, "Monat zwischen 1 und 12 und Jahr zwischen "
                         "1583 und 2999\n"
                         "[Tag zwischen 1 und Anzahl für dieses Monat]\n");
         return 2;
      }
   }
   else if (argc == 1)                 /* aktuelles Monat */
   {
      time(&sec);
      zeit = localtime(&sec);
      tag = zeit->tm_mday;
      monat = zeit->tm_mon + 1;
      jahr = zeit->tm_year + 1900;
      tage = Anzahl_Tage( jahr, monat, 1);
      start = (tage + WOCHENTAG) % 7;
      printcal(start, anzProMonat(jahr, monat), tag, monat, jahr);
      return 0;
   }
   else
   {
      fprintf(stderr, "Aufruf:\n%s [[tag] monat jahr]\n", argv[0]);
      return 1;
   }
}

/*-------------------------- functions ------------------------------*/
/** Kalender ausgeben
 *  start ... Wochentag des 1. dieses Monats
 *  anz   ... Anzahl der Tage dieses Monats
 *  heute ... Datum des heutigen Tages, 0, falls in einem anderen Monat
 *  monat ... Monat (1..12)
 *  jahr
 */
void printcal(int start, int anz, int heute, int monat, int jahr)
{
   char *tage[] = { "Montag", "Dienstag", "Mittwoch", "Donnerstag",
                    "Freitag", "Samstag", "Sonntag" };
   char *monate[] = { "Jänner", "Februar", "März", "April",
                      "Mai", "Juni", "Juli", "August",
                      "September", "Oktober", "November", "Dezember" };
   int i;
   int tag;

   printf("%s %d\n\n", monate[monat-1], jahr);
   for (i = 0; i < 7; i++)
   {
      printf("%10s ", tage[i]);
      for (tag = i + 1 - start; tag < anz + 7 + start; tag += 7)
         if (tag == heute && feiertag(jahr, monat, tag)
               && tag >= 1 && tag <= anz)
            printf("[%2d]", tag);
         else if (tag == heute && tag >= 1 && tag <= anz)
            printf("<%2d>", tag);
         else if (feiertag(jahr, monat, tag) && tag >= 1 && tag <= anz)
            printf(":%2d:", tag);
         else if (tag >= 1 && tag <= anz)
            printf("%3d ", tag);
         else
            printf("    ");
      printf("\n");
   }
   printf("\n");
   printFeiertage(jahr, monat);
}

/*
 * Function schaltjahr
 *
 * Zweck:   Liefert 1, wenn angegebenes Jahr ein Schaltjahr ist
 *
 * Algorithmus:
 *          ab 1582 gilt folgende Regel für Schaltjahre:
 *             Ist die Jahreszahl durch 400 teilbar oder
 *             ist die Jahreszahl durch 4 teilbar aber nicht durch 100
 *             dann ist das Jahr ein Schaltjahr
 *
 * Parameter:
 *       IN: Jahr
 *      OUT:
 *
 * Return-Wert: 1 ... Schaltjahr
 *              0 ... sonst
 */
int schaltjahr( int Jahr )
{
   if ( Jahr % 400 == 0 )
      return 1;
   else if ( Jahr % 100 == 0 )
      return 0;
   else if ( Jahr % 4 == 0 )
      return 1;
   else 
      return 0;
}

int anzProMonat(int jahr, int monat)
{
   switch(monat)
   {
      case 2:
         return 28 + schaltjahr(jahr);
         break;
      case 4:
      case 6:
      case 9:
      case 11:
         return 30;
         break;
      default:
         return 31;
   }
}

/*
 * Function Anzahl_Tage
 *
 * Zweck:    Bestimmt die Anzahl der Tage ab 1.1.1582
 *
 * Algorithmus:
 *           Tag + Anzahl Tage für Monate + Anzahl Tage für Jahre
 *
 * Parameter:
 *       IN: Jahr, Monat, Tag
 *      OUT:
 *
 * Return-Wert: Anzahl der Tage ab 1.1.1582
 */
int Anzahl_Tage( int Jahr, int Monat, int Tag )
{
   int   j;
   int   m;
   int   tage = Tag; /* Monatstag */

   /*
    * Tage für Jahre berechnen
    */
   for ( j = 1582; j < Jahr; j++ )
      tage += 365 + schaltjahr( j );

   /*
    * Tage für Monate berechnen
    */
   for ( m = 1; m < Monat; m++ )
      switch( m )
      {
         case 2:
            tage += 28 + schaltjahr( Jahr );
            break;
         case 4:
         case 6:
         case 9:
         case 11:
            tage += 30;
            break;
         default:
            tage += 31;
      }
   return( tage );
}

/** Bestimmt Feiertag.
 *  @param jahr
 *  @param monat
 *  @param tag
 *  @return Nummer des Feiertags, 0 sonst
 */
int feiertag(int jahr, int monat, int tag)
{
   int tagzahl, j, m, t;
   ostern(jahr, &m, &t);
   tagzahl = Anzahl_Tage(jahr, m, t);
   
   if (monat == m && tag == t)         /* Ostern */
      return OSTERSONNTAG;
   tag2datum(tagzahl + 1, &j, &m, &t);
   if (monat == m && tag == t)         /* Ostern */
      return OSTERMONTAG;
   tag2datum(tagzahl - 46, &j, &m, &t);
   if (monat == m && tag == t)         /* Aschermittwoch */
      return ASCHERMITTWOCH;
   tag2datum(tagzahl - 7, &j, &m, &t);
   if (monat == m && tag == t)         /* Palmsonntag */
      return PALMSONNTAG;
   tag2datum(tagzahl - 2, &j, &m, &t);
   if (monat == m && tag == t)         /* Karfreitag */
      return KARFREITAG;
   tag2datum(tagzahl + 49, &j, &m, &t);
   if (monat == m && tag == t)         /* Pfingstsonntag */
      return PFINGSTSONNTAG;
   tag2datum(tagzahl + 50, &j, &m, &t);
   if (monat == m && tag == t)         /* Pfingstmontag */
      return PFINGSTMONTAG;
   tag2datum(tagzahl + 56, &j, &m, &t);
   if (monat == m && tag == t)         /* Dreifaltigkeitssonntag */
      return DREIFALTIGKEITSSONNTAG;
   tag2datum(tagzahl + 60, &j, &m, &t);
   if (monat == m && tag == t)         /* Fronleichnam */
      return FRONLEICHNAM;

   if (monat == 1 && tag == 1)         /* Neujahr */
      return NEUJAHR;
   if (monat == 1 && tag == 6)         /* Heilige 3 Könige */
      return HL3KOENIGE;
   if (monat == 5 && tag == 1)         /* Staatsfeiertag */
      return STAATSFEIERTAG;
   tag2datum(sonntag(jahr, 5, 13), &j, &m, &t);
   if (monat == 5 && tag == t)         /* Muttertag FIXME */
      return MUTTERTAG;
   if (monat == 8 && tag == 15)        /* Mariahimmelfahrt */
      return MARIAHIMMELFAHRT;
   if (monat == 10 && tag == 26)       /* Nationalfeiertag */
      return NATIONALFEIERTAG;
   if (monat == 10 && tag == 31)       /* Reformationstag */
      return REFORMATIONSTAG;
   if (monat == 11 && tag == 1)        /* Allerheiligen */
      return ALLERHEILIGEN;
   if (monat == 11 && tag == 2)        /* Allersselen */
      return ALLERSEELEN;
   if (monat == 11)
   {
      if (sonntag(jahr, 12, 24) == Anzahl_Tage(jahr, 12, 24))
         tagzahl = sonntag(jahr, 12, 24) - 21;
      else
         tagzahl = sonntag(jahr, 12, 24) - 28;
      tag2datum(tagzahl, &j, &m, &t);
      if (tag == t && m == 11)         /* 1. Advent */
         return ADVENT1;
   }
   if (monat == 12)
   {
      if (tag == 8)                    /* Maria Emfängnis */
         return MARIAEMPFAENGNIS;

      if (sonntag(jahr, 12, 24) == Anzahl_Tage(jahr, 12, 24))
         tagzahl = sonntag(jahr, 12, 24) - 21;
      else
         tagzahl = sonntag(jahr, 12, 24) - 28;
      tag2datum(tagzahl, &j, &m, &t);
      if (tag == t && m == 12)         /* 1. Advent */
         return ADVENT1;
      tag2datum(tagzahl+7, &j, &m, &t);
      if (tag == t)                    /* 2. Advent */
         return ADVENT2;
      tag2datum(tagzahl+14, &j, &m, &t);
      if (tag == t)                    /* 3. Advent */
         return ADVENT3;
      tag2datum(tagzahl+21, &j, &m, &t);
      if (tag == t)                    /* 4. Advent */
         return ADVENT4;
      if (tag == 24)                   /* Hl. Abend */
         return HEILIGABEND;
      if (tag == 25)                   /* Christiani */
         return CHRISTIANI;
      if (tag == 26)                   /* Stefanitag */
         return STEFANI;
      if (tag == 31)                   /* Silvester :-) */
         return SILVESTER;
   }

   return KEIN;                        /* Kein Feiertag */
}

void ostern( int jahr, int *monat, int *tag )
{
   int a = jahr % 19;
   int b = jahr / 100;
   int c = jahr % 100;
   int d = b / 4;
   int e = b % 4;
   int f = ( b + 8 ) / 25;
   int g = ( b - f + 1 ) / 3;
   int h = ( 19 * a + b - d - g + 15 ) % 30;
   int i = c / 4;
   int k = c % 4;
   int l = ( 32 + 2 * e + 2 * i -h -k ) % 7;
   int m = ( a + 11 * h + 22 * l ) / 451;
   int p = ( h + l - 7 * m + 114 ) % 31;

   *monat = ( h + l - 7 * m + 114 ) / 31;
   *tag = p + 1;
}
void tag2datum( int tagzahl, int *jahr, int *monat, int *tag )
{
   /*
    * Jahr berechnen
    */
   *jahr = 1582;
   while ( tagzahl > 365 + schaltjahr( *jahr ) )
   {
      tagzahl -= 365 + schaltjahr( *jahr );
      (*jahr)++;
   }
   /*
    * Monat
    */
   for ( *monat = 1; tagzahl > tagemonat( *jahr, *monat ); (*monat)++ )
      tagzahl -= tagemonat( *jahr, *monat );
   /*
    * Tag
    */
   *tag = tagzahl;
}

int sonntag( int jahr, int monat, int tag )
{
   int tagzahl = Anzahl_Tage( jahr, monat, tag );
   int wt = ( DONNERSTAG + tagzahl ) % 7;
   if ( wt == SONNTAG ) /* bereits Sonntag */
      return tagzahl;
   else
      return tagzahl + ( SONNTAG - wt );
}
int tagemonat( int jahr, int monat )
{
   switch( monat )
   {
      case 2:
         return 28 + schaltjahr( jahr );
         break;
      case 4:
      case 6:
      case 9:
      case 11:
         return 30;
         break;
      default:
         return 31;
   }
}

/** gib eine Liste der Feiertage aus.
 *  @param jahr IN
 *  @param monat OUT
 */
void printFeiertage(int jahr, int monat)
{
   int i;
   char *bez = "";
   for (i = 1; i <= tagemonat(jahr, monat); i++)
   {
      bez = "";
      switch (feiertag(jahr, monat, i))
      {
         case NEUJAHR:
            bez = "Neujahr";
            break;
         case HL3KOENIGE:
            bez = "Heilige Dreikönige";
            break;
         case ASCHERMITTWOCH:
            bez = "Aschermittwoch";
            break;
         case PALMSONNTAG:
            bez = "Palmsonntag";
            break;
         case KARFREITAG:
            bez = "Karfreitag";
            break;
         case OSTERSONNTAG:
            bez = "Ostersonntag";
            break;
         case OSTERMONTAG:
            bez = "Ostermontag";
            break;
         case STAATSFEIERTAG:
            bez = "Staatsfeiertag";
            break;
         case MUTTERTAG:
            bez = "Muttertag";
            break;
         case PFINGSTSONNTAG:
            bez = "Pfingstsonntag";
            break;
         case PFINGSTMONTAG:
            bez = "Pfingstmontag";
            break;
         case DREIFALTIGKEITSSONNTAG:
            bez = "Dreifaltigkeitssonntag";
            break;
         case FRONLEICHNAM:
            bez = "Fronleichnam";
            break;
         case MARIAHIMMELFAHRT:
            bez = "Maria Himmelfahrt";
            break;
         case NATIONALFEIERTAG:
            bez = "Nationalfeiertag";
            break;
         case REFORMATIONSTAG:
            bez = "Reformationstag";
            break;
         case ALLERHEILIGEN:
            bez = "Allerheiligen";
            break;
         case ALLERSEELEN:
            bez = "Allerseelen";
            break;
         case MARIAEMPFAENGNIS:
            bez = "Maria Empfängnis";
            break;
         case ADVENT1:
            bez = "1. Advent";
            break;
         case ADVENT2:
            bez = "2. Advent";
            break;
         case ADVENT3:
            bez = "3. Advent";
            break;
         case ADVENT4:
            bez = "4. Advent";
            break;
         case HEILIGABEND:
            bez = "Heiligabend";
            break;
         case CHRISTIANI:
            bez = "Christtag";
            break;
         case STEFANI:
            bez = "Stefanitag";
            break;
         case SILVESTER:
            bez = "Silvester :-)";
            break;
      }
      if (strlen(bez) > 0)
         printf("%2d.%d. %s\n", i, monat, bez);
   }
}

Labels: C, Lösung, PR5

Vervollständigen Sie die folgenden Funktionsdefinitionen und schreiben Sie passende Testaufrufe.

def ist_dreieck(a, b, c):
    """liefert True, wenn durch a, b und c ein gültiges Dreieck definiert
    ist"""
    return True

def ist_quadrat(a, b, w):
    """liefert True, wenn durch a und b sowie dem Winkel w ein 
    Quadrat definiert ist"""
    return True

def ist_schaltjahr(jahr):
    """liefert True, wenn das gegebene Jahr ein Schaltjahr ist.
    Seit Ende 1582 gilt der Gregorianische Kalender, bei dem folgende 
    Regel für die Schaltjahrbestimmung anzuwenden sind:
        In allen Jahren, deren Jahreszahl durch vier teilbar ist, ist
        der 29. Februar ein Schalttag und damit ist dieses Jahr ein 
        Schaltjahr.
        Eine Ausnahme bilden allerdings die vollen Jahrhundertjahre 1700, 
        1800, 1900 usw., auch Säkularjahre genannt. Hiervon erhalten nur 
        diejenigen einen Schalttag, deren Jahreszahl durch 400 teilbar
        ist. Jedes vierte Säkularjahr ist somit ein Schaltjahr.
    Für alle Jahre <= 1582 liefert die Funktion False, weil da das
    Schaltjahr nicht definiert ist, sonst gilt obige Regel."""
    return False

def fib(n):
    """liefert die Fibonaccizahl zu n. Die Zahlen sind wie definiert:
        fib(0) -> 0
        fib(1) -> 1
        fib(2) -> 1
        fib(3) -> 2
        fib(4) -> 3
        fib(5) -> 5
        fib(6) -> 8
        ...
        fib(10) -> 55
        ...
        fib(15) -> 610"""
    return 1

def fibtab(n):
    """erzeugt eine Tabelle der Fibonaccizahlen bis inclusive n.
    z.B. gibt fibtab(10) folgendes aus:
        [0, 1, 1, 2, 3, 5, 8]
    oder fibtab(100):
        [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    Hinweis:
        verwenden Sie als Zeilenumbruch ", " beim print, also
            print(wert, end=', ')
        außer natürlich beim letzten Wert, hier ist "]" gefordert.
    """
    print("[0, 1, 1, 2, 3, 5, 8]")

def sum_3_5(max):
    """
    bilde Summe der Vielfachen von 3 und 5 kleiner als max.
    Beispielsweise liefert sum_3_5(10) 23, weil
        die Vielfachen von 3 < 10 sind
            3 + 6 + 9 = 18
        die Vielfachen von 5 < 10 sind
            5
        18 + 5 = 23
    sum_3_5(20) liefert 78, weil
        3+  6+9+   12+15+18=63
          5+    10+        =15 (15 ist in obiger Liste schon enthalten!)
    sum_3_5(25) liefert 143, weil
        3+  6+9+   12+   18+   21+24=93 (Vielfache von 5 stehen darunter)
          5+    10+   15+   20+     =50
    sum_3_5(100) liefert 2318 (ohne Beweis)
    """
    return 23

def minquad(zahl):
    """finde die nächstkleinere oder gleichgroße ganze Zahl, die eine 
    Quadratzahl ist. Beispiele:
        minquad(16) -> 16 (weil 4 * 4 = 16 <= 16)
        minquad(24) -> 16 (weil 4 * 4 = 16 <= 24)
        minquad(25) -> 25 (weil 5 * 5 = 25 <= 25)
        minquad(26) -> 25 (weil 5 * 5 = 25 <= 26)
    """
    return zahl

def dreieck(a, w):
    """zeichnet ein gleichseitiges Dreieck der Seitenlänge a, gedreht um
    den Winkel w. w = 0 bedeutet, dass die eine Seite horizional ist. 
    w = 90 bedeutet, dass das Dreieck nach LINKS um 90° gedreht ist, d.h.
    eine Seite ist vertikal.
    Das Dreieck soll rechts neben des angegebenen Punktes gezeichnet
    werden.
    """
    pass

def dreieck_an_pos(a, w, x, y):
    """zeichnet ein Dreieck mit Hilfe der Funktion dreieck(a, w) an der 
    Position x, y."""
    pass

Hier folgt ein Beispielaufruf für die Schaltjahrfunktion:

def test_ist_schaltjahr():
    for jahr in (1000, 1581, 1582, 1900, 1999, 2003):
        assert not ist_schaltjahr(jahr)
    for jahr in (1996, 2000, 2004):
        assert ist_schaltjahr(jahr)
    print("ist_schaltjahr ok")

Sollte ist_schaltjahr() richtig implementiert sein, dann müsste "ist_schaltjahr ok" ausgegeben werden. Andernfalls wird das Programm bei einer der assert-Anweisungen abgebrochen werden. assert verwendet man als Programmierer um Bedingungen zu prüfen, die, falls sie nicht erfüllt sind, auf einen Programmierfehler hinweisen. Als Bedingung kann alles rechts neben dem assert stehen, das True ("alles ok") oder False liefert. Die Testaufrufe für alle Funktionen sollten dann etwa so zusammengefasst werden:

def main():
    """Hauptprogamm zum Testen aller Funktionen"""
    test_ist_dreieck()
    test_ist_quadrat()
    test_ist_schaltjahr()
    test_fib()
    test_sum_3_5()
    test_minquad()
    test_dreieck()
    test_dreieck_an_pos()

Dieses main() muss natürlich auch erst aufgerufen werden (keine Einrückung):

main()

Wenn Sie das Programm laufen lassen, dann sieht sie Ausgabe, wenn alles funktioniert (sinngemäß) so aus:

ist_dreieck ok
ist_quadrat ok
ist_schaltjahr ok
fib ok
sum_3_5 ok
minquad ok

Die Funktionen test_dreieck() sowie test_dreieck_an_pos() bewirken eine Zeichnung der folgenden Art (je nach Aufrufe):
Hier waren es die Aufrufe:

def test_dreieck():
    reset()
    dreieck(60, 0)
    dreieck(60, 90)
    dreieck(60, -60)

def test_dreieck_an_pos():
    dreieck_an_pos(70, 0, 50, 50)
    dreieck_an_pos(70, 180, -50, -50)

Es ist also "optische Kontrolle" nötig.

Labels: Aufgabe, POS1-1, Python