链接:
http://poj.grids.cn/practice/2964/
这本来就是一个简单的题目,但是还是值得我用一篇文章的位置。大家都做过闰年的题目,这只是闰年的一个升级版。。。本来我不至于这么纠结这个题目的,一看到题目,
我就考虑到了一次次减去天数来加年数和月份,而且我还想在读入数据之前初始化一个存储2000-9999年每年有多少天得数组...这样就可以避免循环时候计算每年的天数了...但是我还是怕时间不够,所以我想到了个O(1)的算法...
那就是按照题目的说明,其实每400是一个周期的,但是我前面写代码的时候把4年当中一个小周期,100年当中一个中周期,400年当中一个大周期,同样的处理了...
事实上,只能对400作为周期处理,其它的必须分类讨论,虽然代码写出来很复杂,而且我也因为出现这个bug错了无数次,但是我还是感觉非常值得的...因为这是我独立思考的成果,耗费了多少时间和精力倒是无所谓...写算法题,目的不仅仅应该是学习了多少个算法,而是在于能力的提高,个人的严谨性,思考问题的完整性等等...一直觉得自己思考问题时候有创意,但是完整性和严谨性很低...
下面贴我的代码吧,只用了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;
}