国际惯例,转载注明出处。大飞机: https://user.qzone.qq.com/16491848/blog/1551429397?source=namecardword

 1 static void Main(string[] args)
 2 {
 3     Console.WriteLine(CountDays(2019, 3, 3) - CountDays(1949, 10, 1));
 4     Console.ReadKey();
 5 }
 6 
 7 static int CountDays(int y, int m, int d)
 8 {
 9     if (m < 3)
10     {
11         y--;
12         m += 12;
13     }
14     return 365 * y + (y >> 2) - y / 100 + y / 400 + (153 * m - 457) / 5 + d - 306;
15 }
该算法先根据年月日求出该日期距离 0001年1月1日 的总天数,然后两个天数直接相减,即可求出日期差。

而求总天数的代码就是这个算法的核心,只有两行。我现在详细说说这个算法的原理:

 

计算日期差的算法,无论什么算法(除了故意浪费时间的算法),时间复杂度都是 O(1),这个没什么好说的。关键在于优化计算步骤。

 

日期差计算有两个难点:
1. 怎样解决闰年的 2 月天数问题
2. 怎样解决不同月份的天数不同问题(常规算法是使用数组记录每个月的天数)

 

为了解决这两个问题,该算法先把 1 月和 2 月当成上一年的 13 月和 14 月。然后,我们看一下每个月的天数:
月份:03-04-05-06-07;08-09-10-11-12;13-14
天数:31-30-31-30-31;31-30-31-30-31;31-30(28)
为了凸显规律,我将 5 个月分成了一组。

 

可以看到,将 1、2 月挪动后,月份与天数的规律就出来了:

5 个月一组,1-0-1-0-1,重复(先减去 30,好看清楚)。

 

在这个规律的基础上,为了后续计算的方便,先求出 m 月之前有多少天(以 3 月为第一个月),得到这样的序列(先减去 30,好看清楚):
0-1-1-2-2,3-4-4-5-5,6-7
比如说第 6 个数字 3,对应的是 8 月,表示 8 月之前一共有 3 + 30 * 5 = 153 天。(30 * 5,表示加上 3~7 月每月 30 天)

 

于是,找到这样的表达式(注意:C 语言整数相除的结果直接取整,并不做四舍五入):
(m * 3 – 7) / 5
可以得出前面提到的:
0-1-1-2-2,3-4-4-5-5,6-7
这样的规律序列。

 

再把每月 30 天加进去,得出表达式:
(153 * m – 457) / 5
该表达式求出 m 月之前一共有多少天。

例:
m = 3 时,3 月是第一个月,所以表达式值为 0;
m = 4 时,表达式值为 31,就是 3 月的总天数;
m = 7 时,表达式值为 3 ~ 6 月的总天数。
因为把闰月挪到了最后一个月,所以 m = 14 时(就是表示 2 月),计算结果只是 3 ~ 13 月的总天数,并不会受闰月影响。

 

以上,就是算法最难理解的一部分。

 

其他代码都简单了,
+ (y >> 2) – y / 100 + y / 400
是直接加上期间有多少闰年。y>>2 是 y / 4 等效的位移运算写法(效率更高)。

 

就是这么简单~

 

上面是转载内容。这里面有个难点,就是(m * 3 – 7) / 5这个公式是怎么来的。

 

 

其实,只要意识到,每个区间的第一个数是等差数列,是可以直接快速算出这个特定公式的

 

版权声明:本文为Pupa原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/Pupa/p/10467523.html