鏈接:
http://poj.grids.cn/practice/2964/
這本來(lái)就是一個(gè)簡(jiǎn)單的題目,但是還是值得我用一篇文章的位置。大家都做過(guò)閏年的題目,這只是閏年的一個(gè)升級(jí)版。。。本來(lái)我不至于這么糾結(jié)這個(gè)題目的,一看到題目,
我就考慮到了一次次減去天數(shù)來(lái)加年數(shù)和月份,而且我還想在讀入數(shù)據(jù)之前初始化一個(gè)存儲(chǔ)2000-9999年每年有多少天得數(shù)組...這樣就可以避免循環(huán)時(shí)候計(jì)算每年的天數(shù)了...但是我還是怕時(shí)間不夠,所以我想到了個(gè)O(1)的算法...
那就是按照題目的說(shuō)明,其實(shí)每400是一個(gè)周期的,但是我前面寫(xiě)代碼的時(shí)候把4年當(dāng)中一個(gè)小周期,100年當(dāng)中一個(gè)中周期,400年當(dāng)中一個(gè)大周期,同樣的處理了...
事實(shí)上,只能對(duì)400作為周期處理,其它的必須分類(lèi)討論,雖然代碼寫(xiě)出來(lái)很復(fù)雜,而且我也因?yàn)槌霈F(xiàn)這個(gè)bug錯(cuò)了無(wú)數(shù)次,但是我還是感覺(jué)非常值得的...因?yàn)檫@是我獨(dú)立思考的成果,耗費(fèi)了多少時(shí)間和精力倒是無(wú)所謂...寫(xiě)算法題,目的不僅僅應(yīng)該是學(xué)習(xí)了多少個(gè)算法,而是在于能力的提高,個(gè)人的嚴(yán)謹(jǐn)性,思考問(wèn)題的完整性等等...一直覺(jué)得自己思考問(wèn)題時(shí)候有創(chuàng)意,但是完整性和嚴(yán)謹(jǐn)性很低...
下面貼我的代碼吧,只用了10ms,如果采用第一種方法則需要60ms-70ms...
#include <stdio.h>
#define SMALL (365 * 3 + 366)
#define MID (SMALL * 25 - 1)
#define BIG (MID * 4 + 1)
char* pszWeekdays[7] =
{
"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
};
int nDaysOfMon[2][13] =
{
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
void GetMonthAndDay(int nDays, bool bIsLeap, int* nMon, int* nDay)
{
int nChoose = 0;
int i = 0;
if (bIsLeap)
{
nChoose = 1;
}
*nMon = *nDay = 0;
i = 1;
while (nDays > nDaysOfMon[nChoose][i])
{
nDays -= nDaysOfMon[nChoose][i];
++i;
}
*nMon = i;
*nDay = nDays;
}
void CountSmall(int* pnDays, int* pnPastYears, int* pnMon, int* pnDay)
{
if (*pnDays >= 3 * 365)//4
{
*pnPastYears += 3;
*pnDays -= 365 * 3;
GetMonthAndDay(*pnDays + 1, true, pnMon, pnDay);
}
else//1-3
{
*pnPastYears += *pnDays / 365;
*pnDays %= 365;
GetMonthAndDay(*pnDays + 1, false, pnMon, pnDay);
}
}
int main()
{
int nPastDays = 0;
int nPastYears = 0;
int nYear = 0, nMon = 0, nDay = 0;
while (scanf("%d", &nPastDays), nPastDays != -1)
{
int nTemp = nPastDays;
nPastYears = 0;
if (nTemp < 366)
{
GetMonthAndDay(nTemp + 1, true, &nMon, &nDay);
nPastYears = 0;
}
else
{
nPastYears++;
nTemp -= 366;
nPastYears += (nTemp / BIG) * 400;
nTemp %= BIG;
if (nTemp >= MID * 3)//301-400年(以4為周期)
{
nTemp -= MID * 3;
nPastYears += 300;
nPastYears += nTemp / SMALL * 4;
nTemp %= SMALL;
CountSmall(&nTemp, &nPastYears, &nMon, &nDay);
}
else//1-300年
{
nPastYears += nTemp / MID * 100;
nTemp %= MID;
if (nTemp >= SMALL * 24)//97-100年(4個(gè)平年)
{
nTemp -= SMALL * 24;
nPastYears += 4 * 24;
nPastYears += nTemp / 365;
nTemp %= 365;
GetMonthAndDay(nTemp + 1, false, &nMon, &nDay);
}
else//1-96年
{
nPastYears += nTemp / SMALL * 4;
nTemp %= SMALL;
CountSmall(&nTemp, &nPastYears, &nMon, &nDay);
}
}
}
printf("%d-%02d-%02d %s\n", nPastYears + 2000, nMon, nDay, pszWeekdays[nPastDays % 7]);
}
return 0;
}