Gesucht wird ein Algorithmus zur Jahrestagberechnung. Zu einem eingegebenen Datum (Tag, Monat, Jahr) soll ausgerechnet werden, um den wievielten Tag im Jahr es sich handelt.

Der erste Schritt ist natürlich immer das Nachdenken über die Problemlösung. Diese Phase sollte nicht zu kurz sein, denn oft findet sich eine optimale Lösung erst nach dem zweiten oder dritten Ansatz. Und kürzere Programme sind nicht nur schneller, sondern haben (rein statistisch betrachtet) auch weniger Fehler. Dann sollte man den Lösungsweg skizzieren und dabei auch überlegen, ob auch alle Randbedingungen und Ausnahmesituationen berücksichtigt wurden.

Oft hilft es, den Algorithmus zuerst anhand eines Beispiels durchzuspielen. Dabei werden einem oft Zusammenhänge und Fallstricke klar. Versuchen wir das gleich mit der Problemstellung von oben:

• Datum = 7.7.99
• Jahrestag (JT) = 31 + 28 + 31 + 30 + 31 + 30 + 7 = 188

Das Verfahren addiert also bis zum Juni die Monatslängen und zält dann noch die 7 Tage des Juli hinzu. Spätestens hier sollte einem einfallen, daß der Februar auch 29 Tage haben kann. Der Programmierer sollte sich hier eine Notiz machen: "Nachsehen, wann ein Jahr ein Schaltjahr ist".

Danach sollte eine problemnahe Darstellung des Algorithmus folgen. Diese sieht beispielsweise so aus:

1. Eingabe von Tag, Monat, Jahr.
2. Ermittle die Monatslänge des Februar (Schaltjahr?).
3. Addiere die Monatslängen der Vormonate (also bis Monat-1) und den Tageswert des eingegebenen Monats.
4. Gib das Ergebnis aus.

Dabei wird davon ausgegangen, daß die Eingabe korrekt ist (also nicht z. B. der 35.13.19999 eingegeben wird. Eine Optimierungsmöglichkeit des Algorithmus ist gegeben, wenn man für Werte von Monat, die kleiner als 2 sind, die Schaltjahresberechnung wegläßt.

Für die Schaltjahresberechnung brauchen wir noch einen Teilalgorithmus. Selbst bei diesem recht einfachen Beispiel zeigt sich also schon ein Grundsatz der strukturierten Programmierung, die Zelegung einer Aufgabe in kleinere und damit überschaubare Teilaufgaben. Nach dem Gregorianischen Kalender handelt es sich um ein Schaltjahr,

• wenn die Jahreszahl ohne Rest durch 4 teilbar ist.
• nicht aber, wenn die Jahreszahl ohne Rest durch 100 teilbar ist.
• jedoch schon, wenn die Jahreszahl ohne Rest durch 400 teilbar ist.

Das Jahr 2000 ist also ein Schaltjahr (was viele Programme nicht richtig machen). Der Alogorithmus lautet also:

1. Eingabe Jahr.
2. Falls (Jahr mod 4) != 0: Ausgabe "NEIN" und ENDE.
3. Falls (Jahr mod 100) != 0: Ausgabe "JA" und ENDE.
4. Falls (Jahr mod 400) = 0: Ausgabe "JA" sonst: Ausgabe "NEIN".

Anmerkungen: mod sei der Modulo-Operator = Rest der Ganzzahligen Division. != bedeutet "ungleich".

Nun steht der Jahreszahlberechnung eigentlich nichts mehr im Weg. Die einzige Schwierigkeit liegt noch darin, daß die Monatslängen unterschiedlich sind:

Jan.	Feb.	März	April	Mai	Juni	Juli	Aug.	Sept.	Okt.	Nov.
31	28/29	31	30	31	30	31	31	30	31	30

Nun ließe sich ein Algorithmus niederschreiben, der 11 WENN-DANN-Abfragen enthät, welche die Tagessumme der Vormanate berechnen:

1. Eingabe Tag, Monat, Jahr.
2. Wenn Monat = 1 dann Jahrestag = Tag und ENDE.
3. Wenn Monat = 2 dann Jahrestag = 31 + Tag und ENDE.
4. Wenn Monat = 3 dann Jahrestag = 31 + 28 + Tag.
   Wenn Schaltjahr, erhöhe Jahrestag um 1.
   ENDE.
5. Wenn Monat = 4 dann Jahrestag = 31 + 28 + 31 + Tag.
   Wenn Schaltjahr, erhöhe Jahrestag um 1.
   ENDE.
6. Wenn Monat = 5 dann Jahrestag = 31 + 28 + 31 + 30 + Tag.
   Wenn Schaltjahr, erhöhe Jahrestag um 1.
   ENDE.
7. ....

Damit ist die Aufgabe sicher zufriedenstellend gelöst.

Es stellt sich die Frage, ob es nich einfacher, kürzer und "eleganter" geht. Denn es ist nicht immer der erste Lösungsweg der einem einfällt, auch der beste und effizienteste Weg. Setzt man versuchsweise alle Monate mit 31 Tagen an, werden ab März zuviele Tage genommen, und zwar:

März	April	Mai	Juni	Juli	Aug.	Sept.	Okt.	Nov.	Dez.
3	3	4	4	5	5	5	6	6	7

Nach einigem Nachdenken und/oder Probieren kommt man vielleicht auf eine höchst interessante Korrekturformel:

Y = 0,4 * Monat + 2,3

Diese Formel liefert die Werte:

März	April	Mai	Juni	Juli	Aug.	Sept.	Okt.	Nov.	Dez.
3,3	3,9	4,3	4,7	5,1	5,5	5,9	6,3	6,7	7,1

Der ganzzahlige Teil der Ergebnisses stimmt offensichtlich mit den Fehlerwerten der vorhergehenden Tabelle überein. Mit dieser Formel kann man den Jahrestags-Algorithmus folgendermaßen definieren (INT nimmt den Ganzzahlanteil einer Zahl):

1. Eingabe Tag, Monat, Jahr.
2. Jahrestag = Tag + 31 * (Monat -1).
3. Falls Monat > 2 ist:
   1. Vermindere Jahrestag um INT(0,4 * Monat + 2,3).
   2. Falls Schaltjahr = "JA" erhöhe Jahrestag um 1.
4. Ausgabe Jahrestag.

Wie man leicht sieht, ist dieser Algorithmus wesentlich kürzer als der erste Ansatz - sowohl von der Laufzeit,als auch von Speicherbedarf her. Nachteilig gegenüber dem ersten Ansartz ist nur, daß dieser Algorithmus dem Leser nicht sofort einleuchtet und daher sorgfältig dokumentiert werden muß.

Untersuchen wir einen zweiten Fall:

Gesucht wird ein Algorithmus, der feststellt ob eine gegebene Zahl eine Primzahl ist.

Eine positeve Zahl X ist genau dann eine Primzahl, wenn sie nur durch sich selbst und durch 1 teilbar ist. Ein erste Lösungsansatz ist:

1. Setze den Teiler T auf 2.
2. ist X ohne Rest durch T teilbar, gib "nicht prim" zurück und beende.
3. erhöhe T um 1.
4. ist T < X, fahre fort bei Schritt 2.
5. gib "prim" zurück und beende.

                                       T = 2;                    /* Schritt 1 */
                                       do
                                         {
                                         if ((X % T) == 0)       /* Schritt 2 */
                                           {
                                           printf("nicht prim"); 
                                           return 0; 
                                           }
                                         T++;                     /* Schritt 3 */
                                         }
                                       while (T < X);          /* Schritt 4 */
                                       printf("p r i m");         /* Schritt 5 */
                                       

Dieser Algorithmus ist (hoffeltlich) effektiv, d. h. er leistet das Gewünschte. Ist er aber auch effizient, d. h. leistet er das Gewünschte bestmöglich? Die Antwort ist natürlich ein dickes "NEIN". Es werden nämlich unnötig viele Zahlen getestet. Bereits durch kleine Modifikationen kann man den Aufwand für den Primzahlentest deutlich verringern:

• Ersetze den Test T => X durch T * T >= X, denn der kleinste Teiler einer Nicht-Primzahl muß sicher kleiner als deren Quadratwurzel sein.
• Statt jede Zahl zu testen, testet man den Teiler 2, dann den Teiler 3 und erhöht danach den Teiler um 2, denn 2 ist die einzige gerade Primzahl.

                                       #include<stdio.h>
                                       
                                       int X, T;
                                       
                                       int main(void)
                                       /* optimierter Entwurf */
                                         {
                                         scanf("%d",&X);           /* X einlesen */
                                         if ((X % 2) == 0)         /* Zahl gerade? */
                                           {
                                           printf("nicht prim, gerade\n"); 
                                           return (0);             /* Programmende */ 
                                           }
                                         T = 3;   
                                         do
                                           {
                                           if ((X % T) == 0)
                                             {
                                             printf("nicht prim, Teiler = %d\n", T); 
                                             return (0);         /* Programmende */ 
                                             }
                                           T = T + 2;
                                           }
                                         while (T*T < X); 
                                         printf("p r i m!\n");
                                         return (0);            /* Programmende */ 
                                         }
                                       

Zurück

Inhaltsverzeichnis

Nächste

Diplomarbeiten zum Runterladen: