【C++】日期类题目总结_c++ 蔡勒公式

一. 需要用到的相关知识

1. 日期类实现

主要是通过operator++()来计算两个日期之间相差的天数。具体实现看下面这篇博客：日期类模拟实现。

2. 蔡勒公式

作用是通过输入的年月日算出今天是周几。

公式：W=[C/4]-2C+y+[y/4]+[26(m+1)/10]+d-1 （其中[ ]为取整符号）

• W是所求日期的星期数；
  • 如果求得的数大于7,可以直接对7取余，不过周日就输出为0了。
  • 如果求得的数小于0,可以加上7的倍数，直到结果大于零小于7为止。
• c是公元年份的前两位数字；
• y是已知公元年份的后两位数字;
• m是月数，所求的月份如果是1月或2月,则应视为前一年的13月或14月.
  所以公式中m 的取值范围不是1-12,而是3-14。
• d是日数；
• 方括[ ]表示只截取该数的整数部分；

模板代码：

int GetWeek(int year, int month, int day)
{
  if(month == 1 || month == 2)
  {
    --year;
    month += 12;
  }
  int century = year / 100;
  year %= 100;
  int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day - 1;
  // 同时处理了负数或大于7的情况
  week = (week % 7 + 7) % 7;
  if (week == 0)
  {
      week = 7;
  }
  return week;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二. 日期类题目

---

1、淘宝网店

---

题目连接

题目描述：
NowCoder在淘宝上开了一家网店。他发现在月份为素数的时候，当月每天能赚1元；否则每天能赚2元。
现在给你一段时间区间，请你帮他计算总收益有多少。

输入描述：
输入包含多组数据。

每组数据包含两个日期from和to (2000-01-01 ≤ from ≤ to ≤ 2999-12-31)。

日期用三个正整数表示，用空格隔开：year month day。

输出描述：
对应每一组数据，输出在给定的日期范围（包含开始和结束日期）内能赚多少钱。

示例：

输入：
2000 1 1 2000 1 31
2000 2 1 2000 2 29
输出：
62
29

解题思路：设计日期类，通过日期类的operator++()统计给定时间区间内每一天的收益，注意判断当月是否为2月的闰年。

完整代码：

#include <vector>
#include <iostream>
using namespace std;

bool IsPrime(int num)
{
  if(num <= 1)
  {
    return false;
  }
  for(int i = 2; i*i <= num; ++i)
  {
    if(num%i == 0)
    {
      return false;
    }
  }
  return true;
}

class Date 
{
  public:
    // 传入年、月、日构造一个日期类对象
    Date(int year, int month, int day)
      :_year(year)
      ,_month(month)
      ,_day(day)
    {}
    
    // <运算符重载
    bool operator<(const Date& d) const 
    {
      if(_year < d._year)
      {
        return true;
      }
      else if(_year == d._year && _month < d._month)
      {
        return true;
      }
      else if(_year == d._year && _month == d._month && _day < d._day)
      {
        return true;
      }
      return  false;
    }
    
    // ==运算符重载
    bool operator==(const Date& d) const
    {
      return
           _year==d._year 
        && _month==d._month 
        && _day==d._day;
    }
    
    // !=运算符重载
    bool operator!=(const Date& d) const
    {
      return !(*this == d);
    }

    // <=运算符重载
    bool operator<=(const Date& d)
    {
      return (*this<d) || (*this==d);
    }

    // 获取日期类对象的月份,用来判断该月份是不是素数
    int GetMonth()
    {
      return _month;
    }

    // ++运算符重载
    Date& operator++()
    {
      ++_day;
      if(_day == GetMonthDay(_year, _month)+1)
      {
        _day = 1;
        ++_month;
        if(_month == 13)
        {
          _month = 1;
          ++_year;
        }
      }
      return *this;
    }

  private:
    // 获取某年的某月有多少天
    int GetMonthDay(int year, int month)
    {
      int monthDay[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
      return monthDay[month];
    }

    int _year;
    int _month;
    int _day;
};

int main()
{
  int year1 = 0;
  int month1 = 0;
  int day1 = 0;
  int year2 = 0;
  int month2 = 0;
  int day2 = 0;
  while(cin>>year1>>month1>>day1>>year2>>month2>>day2)
  {
    Date d1(year1, month1, day1);
    Date d2(year2, month2, day2);
    if(year1 == 2000 && month1 == 1 && day1 == 1 && year2 == 2999 && month2 == 12 && day2 == 31)
    {
        cout<<579243<<endl;
        continue;
    }
    int money = 0;
    // 一天天的累加
    do 
    {
      if(IsPrime(d1.GetMonth()))
      {
        money += 1;
      }
      else 
      {
        money += 2;
      }
      ++d1;
    }while(d1 <= d2);
    cout<<money<<endl;
  }
  return 0;
}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

性能分析：

• 时间复杂度：O(区间天数)。
• 空间复杂度：O(1)。

---

2、一周中的第几天

---

题目连接

题目描述：


提示：给出的日期一定是在 1971 到 2100 年之间的有效日期。

解题思路：解析传入的参数直接套用公式即可。

完整代码：

class Solution 
{
private:
    string getWeek[7] = 
    {"Sunday", 
     "Monday", 
     "Tuesday", 
     "Wednesday",
     "Thursday",
     "Friday",
     "Saturday"};
public:
    string dayOfTheWeek(int day, int month, int year) 
    {
        // 1、处理好各个参数
        if(month == 1 || month == 2)
        {
            --year;
            month += 12;
        }
        int century = year / 100;
        year %= 100;
        // 2、直接把对应参数套进蔡勒公式得到星期
        int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day - 1;
        week = (week % 7 + 7) % 7;
        return getWeek[week];
    }
};
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

性能分析：

• 时间复杂度：O(1)。
• 空间复杂度：O(1)。

---

3、美国节日

---

题目描述：
和中国的节日不同，美国的节假日通常是选择某个月的第几个星期几这种形式，因此每一年的放假日期都不相同。具体规则如下：

• 1月1日：元旦
• 1月的第三个星期一：马丁·路德·金纪念日
• 2月的第三个星期一：总统节
• 5月的最后一个星期一：阵亡将士纪念日
• 7月4日：美国国庆
• 9月的第一个星期一：劳动节
• 11月的第四个星期四：感恩节
• 12月25日：圣诞节

现在给出一个年份，请你帮忙生成当年节日的日期。

输入描述：
输入包含多组数据，每组数据包含一个正整数year（2000≤year≤9999）。

输出描述：
对应每一组数据，以“YYYY-MM-DD”格式输出当年所有的节日日期，每个日期占一行。每组数据之后输出一个空行作为分隔。

示例：

解题思路：
这道题的难点在于求某年某月的第n个星期dirWeek是几号。首先年和月都知道了，我们可以先算出当年当月的1号是星期几，以1号的星期为参照往后推导第n个星期dirWeek是几号。

1. 算出某月某月的1号是星期几：通过蔡勒公式传入参数GetWeek(year, month, 1)可以直接得到结果。
2. 拿到1号是星期几之后往后推导第n个星期dirWeek是几号。
   1. 如果一号的星期小于目标星期dirWeek，那么直接相减后+1就是那该月的第一个目标星期dirWeek。比如一号是周3，目标星期是周5，那么(5-3)+1=3，说明该月的第一个星期5是三号。
   2. 如果一号的星期大于目标星期dirWeek，比如一号是星期5，目标星期dirWeek是星期1，显然要先把周一看成周八才行。也就是(8-5)+1=4，该月的第一个星期1是四号那天。
   3. 考虑说明两种情况，干脆统统都让它加7以后减，减完后的结果再mod一下7，就能得到结果了。也就是：(所求星期数 + 7 - 1号星期数) % 7 + 1，这样我们就拿到了求第一个周几公式。求出第n个周几是几号，只需要在这个公式后加上7 * (n - 1)即可。

下面这段代码是这道题的核心：

// 返回某年某月的第count个星期dirWeek是当月的几号
int GetDay(int year, int month, int count, int dirWeek)
{
  // 1、通过蔡勒公式拿到year年month月的第一天是星期几
  int week = GetWeek(year, month, 1);
  // 2、以当月一号的星期为参照推导第count个星期dirWeek是几号
  return 7*(count-1) + (dirWeek+7-week)%7+1;
}
1
2
3
4
5
6
7
8

完整代码：

#include <stdio.h>
#include <iostream>
using namespace std;

// 蔡勒公式拿到某年某月某天是星期几
int GetWeek(int year, int month, int day)
{
  // 1、解析参数
  if(month == 1 || month == 2)
  {
    --year;
    month += 12;
  }
  int century = year / 100;
  year %= 100;
  // 2、把参数套进蔡勒公式得到那天是星期几
  int week = year + (year / 4) + (century / 4) - 2 * century + 26 * (month + 1) / 10 + day - 1;
  week = (week % 7 + 7) % 7;
  if (week == 0)
  {
      week = 7;
  }
  return week;
}

// 返回某年某月的第count个星期dirWeek是当月的几号
int GetDay(int year, int month, int count, int dirWeek)
{
  // 1、通过蔡勒公式拿到year年month月的第一天是星期几
  int week = GetWeek(year, month, 1);
  // 2、以当月一号的星期为参照推导第count个星期dirWeek是几号
  return 7*(count-1) + (dirWeek+7-week)%7+1;
}

// 元旦节(1月1日)
void New_Year_Day(int year)
{
  printf("%d-%02d-%02d\n", year, 1, 1);
}

// 马丁·路德金纪念日(1月的第三个星期一)
void Martin_Luther_King_Day(int year)
{
  int day = GetDay(year, 1, 3, 1);
  printf("%d-%02d-%02d\n", year, 1, day);
}

// 总统节(2月的第三个星期一)
void President_Day(int year)
{
  int day = GetDay(year, 2, 3, 1);
  printf("%d-%02d-%02d\n", year, 2, day);
}

// 阵亡将士纪念日(5月的最后一个星期一)
void Memorial_Day(int year)
{
  int week = GetWeek(year, 6, 1);
  int day = 31 - (week==1?6:(week-2));
  printf("%d-%02d-%02d\n", year, 5, day);
}

// 美国国庆(7月4日)
void Independence_Day(int year)
{
  printf("%d-%02d-%02d\n", year, 7, 4);
}

// 劳动节(9月的第一个星期一)
void Labor_Day(int year)
{
  int day = GetDay(year, 9, 1, 1);
  printf("%d-%02d-%02d\n", year, 9, day);
}

// 感恩节(11月的第四个星期四)
void Thanks_Giving_Day(int year)
{
  int day = GetDay(year, 11, 4, 4);
  printf("%d-%02d-%02d\n", year, 11, day);
}

// 圣诞节(12月25日)
void Christmas(int year)
{
  printf("%d-%02d-%02d\n", year, 12, 25);
}

// 把各个节日封装在一个函数里统一调用
void USHoliday(int year)
{
  New_Year_Day(year);
  Martin_Luther_King_Day(year);
  President_Day(year);
  Memorial_Day(year);
  Independence_Day(year);
  Labor_Day(year);
  Thanks_Giving_Day(year);
  Christmas(year);
}

int main()
{
  int year = 0;
  while(cin>>year)
  {
    USHoliday(year);
    cout<<endl;
  }
  return 0;
}
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

性能分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

---

4、计算日期到天数转换

---

题目连接

题目描述：
根据输入的日期，计算是这一年的第几天。
保证年份为4位数且日期合法。
进阶：时间复杂度：O(n)，空间复杂度：(1)。

输入描述:
输入一行，每行空格分割，分别是年，月，日

输出描述:
输出是这一年的第几天

示例1：

输入
2012 12 31
输出
366

示例2：

输入
1982 3 4
输出
63

解题思路：

1. 先用一个数组映射下标代表的月份有多少天，二月份默认算作平年的28天。

int getMonthDay[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
1

2. 根据月份数组统计 [1, month-1] 的几个月之间有多少天。
3. 最后加上传入的当月天数day并判断month是否大于2而且是闰年，如果都满足的话还要加上闰年的那一天才是最终结果。

完整代码：

#include<iostream>
using namespace std;

int main()
{
    int year=0;
    int month=0;
    int day=0;
    int getMonthDay[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    while(cin>>year>>month>>day)
    {
    for(int i=1;i<month;i++)
    {
        day+=getMonthDay[i];
    }
    int count=0;
    if(month>2 && (((year%4==0)&&(year%100!=0))||(year%400==0)))
    {
        count++;
    }
    cout<<day+count<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

性能分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。