STEP BY STEP

POJ百练 - 2964:日历问题

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

链接: [http://poj.grids.cn/practice/2964/]

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

下面贴我的代码吧,只用了10ms,如果采用第一种方法则需要60ms-70ms…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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;
}

相关文章