鏈接:
http://poj.grids.cn/practice/2964/
這本來就是一個簡單的題目,但是還是值得我用一篇文章的位置。大家都做過閏年的題目,這只是閏年的一個升級版。。。本來我不至于這么糾結(jié)這個題目的,一看到題目,
我就考慮到了一次次減去天數(shù)來加年數(shù)和月份,而且我還想在讀入數(shù)據(jù)之前初始化一個存儲2000-9999年每年有多少天得數(shù)組...這樣就可以避免循環(huán)時候計算每年的天數(shù)了...但是我還是怕時間不夠,所以我想到了個O(1)的算法...
那就是按照題目的說明,其實每400是一個周期的,但是我前面寫代碼的時候把4年當中一個小周期,100年當中一個中周期,400年當中一個大周期,同樣的處理了...
事實上,只能對400作為周期處理,其它的必須分類討論,雖然代碼寫出來很復雜,而且我也因為出現(xiàn)這個bug錯了無數(shù)次,但是我還是感覺非常值得的...因為這是我獨立思考的成果,耗費了多少時間和精力倒是無所謂...寫算法題,目的不僅僅應該是學習了多少個算法,而是在于能力的提高,個人的嚴謹性,思考問題的完整性等等...一直覺得自己思考問題時候有創(chuàng)意,但是完整性和嚴謹性很低...
下面貼我的代碼吧,只用了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個平年)
{
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;
}