Mittwoch, 15. Dezember 2010
Dynamische Speicherverwaltung in C (PR: 5A, 5B)
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
Erstellen Sie eine weitere Version des Moduls
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
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
Organisieren Sie sich in Kleingruppen und versuchen Sie die einzelnen Funktionen gemeinsam zu entwerfen und zu programmieren. Welche Hilfsfunktionen braucht z.B. das
Erweitern Sie die Speicherverwaltung um eine "Garbage Collection", die freie Speicherbereiche, die hintereinanderliegen zusammenfasst.
Erstellen Sie eine geeignete Verzeichnisstruktur und verwenden Sie
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
Beantworten Sie weiters folgende Fragen (die Antworten müssen in der Datei
Geben Sie einen Ausdruck der ausgearbeiteten Fragen ab!
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ößesize
void hfree(void *p);
zum Freigeben des Speichers, auf den der Zeigernp
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. OKn+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): - Was passiert, wenn man einen String der Länge n alloziert und einen String der Länge n speichert?
- Was passiert, wenn man einen String der Länge n alloziert und einen String der Länge n + 1 speichert?
- 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). - Welche Speicheranforderungen benötigen mehr Speicher - 10 Strings der Länge 100 oder 100 Strings der Länge 10? Begründen Sie die Antwort.
- Wie könnten Sie im Modul
heap
sicherstellen, dass bei einem Aufruf vonhfree(p);
der Parameterp
tatsächlich auf einen mithalloc()
allozierten Speicherbereich zeigt?
heap.txt
muss auch die Liste der Testfälle mit ihren Ergebnissen enthalten. Geben Sie einen Ausdruck der ausgearbeiteten Fragen ab!
Freitag, 10. Dezember 2010
Diagramm erstellen (POS1: 2AHIF, 2CHIF)
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:
Wählen Sie einen passenden Maßstab. Das erste Datum soll der Null-Punkt auf der X-Achse sein.
Verwenden Sie die Turtle-Grafik (
Damit Sie passende Testdaten bekommen, schreiben Sie auch einen Testdatengenerator, der 3 Parameter auf der Kommandozeile hat:
Nennen Sie das Projekt
10.9.2010 70 11.10.2010 36 10.11.2010 50 11.11.2010 70 1.12.2010 30Auf 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:
- Name der Datei
- Anfangsdatum
- Anzahl der Datensätze
Nennen Sie das Projekt
2x-name-python-diagramm
, den Testdatengenerator testdaten.py
und das Diagramm diagramm.py
.Labels: Aufgabe, POS1-2, Python
Freitag, 3. Dezember 2010
Wurzelberechnung (POS1: 1BHIF)
Man kann die Wurzel einer Zahl berechnen mit folgender Formel
xn = (xn-1 + a / xn-1) / 2
Man beginnt damit, dass a und x0 gleich der Zahl, aus der man die Wurzel ziehen will, setzt und x1 berechnet. Dann berechnet man x2 usw. bis sich die beiden letzten Werte nur mehr gering unterscheiden (z.B. die Differenz kleiner 0,0000001 ist).
Schreiben Sie eine Funktion
Erstellen Sie ein Programm
xn = (xn-1 + a / xn-1) / 2
Man beginnt damit, dass a und x0 gleich der Zahl, aus der man die Wurzel ziehen will, setzt und x1 berechnet. Dann berechnet man x2 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
Musterlösung zu Übungsbeispiele für Python vom 1.12.2010 (POS1: 1BHIF)
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.
False leifern muss und wenn
Hier ist zu
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 TrueMan 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 retOder 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 > bBei 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 quadratOder 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 > 0Die 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 schaltjahrJahre 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 < 4Die 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 "Zusätzlich kann ein Text als Fehlermeldung angegeben werden:", line 1, in assert 3 > 4 AssertionError
>>> assert 3 > 4, "3 ist nicht größer als 4" Traceback (most recent call last): File "Angewendet auf obige Testfunktion bedeutet das, dass immer, wenn", line 1, in assert 3 > 4, "3 ist nicht größer als 4" AssertionError: 3 ist nicht größer als 4
assert not ist_schaltjahr(jahr)
die Funktion ist_schaltjahr(jahr)
den Wert 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 fFü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 55Die 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 summeDie 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 i2. 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))) ** 2Die 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) -4Wenn 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
Donnerstag, 2. Dezember 2010
Datum in C selbst gebastelt
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
Here comes the Source...
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); } }
Mittwoch, 1. Dezember 2010
Übungsbeispiele für Python (POS1: 1BHIF)
Vervollständigen Sie die folgenden Funktionsdefinitionen und schreiben Sie passende Testaufrufe.
Hier waren es die Aufrufe:
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.""" passHier 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 okDie 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
Abonnieren Posts [Atom]