LexOpen   - Dit online leksikon

  Forside        


Gregorianske kalender (algoritme)
Skal man til at beregne ugedag, eller antal dage mellem to datoer i den gregorianske kalender, vil en algoritme kun give fornuftige data, såfremt man tager hensyn til hvilket land det drejer sig om, og datoen for den gregorianske kalenders indførelse, samt hvilken dato man foretog justeringen.

Opbygning af algoritmen
Det første man opdager ved at se på kalenderen er at den er opbygget af år, måneder, og dage, hvor der ikke umiddelbart ser ud til at være nogen pæn lineær sammenhæng. Et brute-force kodet program til ugedags beregning vil derfor kunne komme til at bestå af mange "if/case" kontruktioner til at tage højde for de forskellige regler.
For at undgå dette indser man at der må laves en anden skala, for eksempel antal dage siden et »fiktiv« år 0. Dette er meget nemmere at udregne, idet reglerne i den gregorianske kalender er meget klare. Så antallet af dage fra år 0 til den 0. januar kan så beregnes på følgende måde:

/* der benyttes heltals divison ! */
Faktor = 365*ÅR + (ÅR-1)/4 - (ÅR-1)/100 + (ÅR-1)/400 ;

Forkortes lidt fås:
Faktor = 365*ÅR + (ÅR-1)/4 - ((ÅR-1)/100)*3/4 ;

Næste problem bliver februar, som kan være på enten 28 eller 29 dage. Alle andre måneder har et fast antal dage. Det nemmeste er at flytte årets start til marts, idet februar så kommer sidst, så behøves der ikke at tages hensyn til om det er skudår eller ej, når den aktuelle »faktor« skal udregnes for en given dato. Nu mangler der så kun, at få lavet en linær sammenhæng mellem dag i året og aktuel måned og dag. Hvis man starter med at tælle fra marts får man følgende tabel:

Måned Antal dage Dag i året-
Marts 31 0
April 30 31
Maj 31 61
Juni 30 92
Juli 31 122
August 31 153
September 30 184
Oktober 31 214
November 30 245
December 31 275
Januar 31 306
Februar 28/29 337
I alt 365/366

Nu kunne en sådan tabel løsning være ideel, og de fleste ville nok kunne stille sig tilfreds her. Algoritmen ville komme til at se ud som følgende:

/* der benyttes heltals divison ! */
if (Måned < 3 ) {
/* da skuddagen er den 29/2, skal skuddag ikke medregnes i jan/feb */
/* så derfor benyttes ÅR-1 */
Faktor = 365*ÅR + (ÅR-1)/4 - (((ÅR-1)/100)*3)/4 + tabel[Måned] + Dag.
} else {
Faktor = 365*ÅR + ÅR/4 - ((ÅR/100)*3)/4 + tabel[Måned] + Dag.
}

Tabellen kan forenkles noget. Plotter man tabellen ind på millimeterpapir, og gives Januar og Februar henholdsvis månedsnummeret 13 og 14, vil man opdage, at man (næsten) kan tegne en ret linje i gennem de plottede punkter. Ved enten at aflæse, eller ved at benytte lineær regression, kan man få hældningskoefficient (m) og skæring med Y-aksen (b):

m = 30,6013986 , b = -91,77855478 .
Ved beregningen fremkom korrelationskoefficienten 0,999996, som er ganske godt, da 1,00 ville være fuldkommen korrelation. Tabellen fra før kan derfor erstattes med:
round ( Måned*30,60 - 91,78 )
= Int ( Måned*30,60 - 91,78 + 0,5 )
= Int ( Måned*30,60 - 91,28 )
For ikke at skulle benytte reelle tal (float), udregnes det hele i en heltal udgave, og samtidig forenkles beregningen ved Januar og Februar. Den færdige rutine bliver så:
/* ------------------- factor -----------------------------*/
#define LONGWORD unsigned int
LONGWORD factor(RTCtime *tm)
{
WORD y,m;
y = tm->year;
m = tm->month;
if ( tm->month < 3 ) { y--; m += 12; }
return 365UL*y + y/4UL - ((y/100+1)*3)/4 + (m*3060-9135)/100 + tm->day + 59;
}
Datastrukturen for RTCtime er lavet for at holde lidt styr på dag, måned og år.

Beregning af ugedag
Der er 7 dage i en uge, og dagene gentager sig hele tiden, så beregning af ugedag kan nemt gøres ved modulus 7. Ønskes derudover at søndag er ugedag nr. 0, skal der først adderes 6 til faktoren.
/*------------------- weekday ------------------------------*/
/* returns weekday, sun=0, mon=1,..... : */
int weekday(RTCtime *tm)
{
return (int) ( (factor(tm)+6) % 7UL );
}
Beregning af antal dage mellem to datoer
Denne kan gøres meget enkel med factor():
Dage = labs ( factor(Dato1) - factor(Dato2) ).
C-funktionen labs() udregner den absolute værdi.
Kontrol af om en dato er ok
Ved indtastning af datoer er der ofte behov for at kontrollere om datoen er gyldig, så f.eks. datoer som d. 29. februar 1995 eller 31. april ikke accepteres. Året kontrolleres på sædvanlig vis, evt. suppleret med, at det for Danmark skal være fra og med marts 1700. Måneden er nem at kontrollere, idet det selfølgelig er et tal fra 1 til 12. Antallet af dage i måneden kan med factor() let beregnes, idet den fremgår som antallet af dage mellem den første i den aktuelle måned og den 1. i næste måned. En simpel procedure til at foretage en sådan kontrol er date_ok().
/*------------------- date_ok ------------------------------*/
int date_ok(RTCtime *t)
/* returns 0 if date not ok, else days in month is returned */
{
LONGWORD f1;
RTCtime tmp;
if ( (t->year < 1) || (t->year >9998) ) return 0;
if ( (t->month < 1) || (t->month > 12) ) return 0;
if ( t->day < 1 ) return 0;
tmp = *t; tmp.day=1;
f1 = factor(&tmp);
tmp.month++;
if ( (f1 = factor(&tmp)-f1) < t->day ) return 0;
else return (int) f1; /* if ok return days in month */
}
Adder N dage til en dato, og udregn den nye dato
Det nemmeste er at udregne factor() for datoen og addere de N dage:
F = factor(dato) + N ;
Derefter divideres med 365.2425, og det fremkomne tal skulle gerne være årstallet:
ÅR= F * 10000UL / 3652425UL;
Som kontrol udregnes F1 = factor( 1.jan.ÅR), og F2 = factor( 1.jan.(ÅR+1). Hvis der på grund af afrundingsfejl ikke gælder uligheden:
F1 <= F < F2
Må ÅR korrigeres med +/- 1.
Måneden findes lettes ved at udregne Fm = factor(1.MD.ÅR) for alle måneder startende med MD=1, indtil Fm > F. Dagen kan så findes som differencen mellem Fm og F.