frenchleave

基姆拉尔森计算公式

2020/12/18 JavaScriptAlgorithm

参考:

# 问题背景

一周中的第几天

给你一个日期, 请你设计一个算法来判断它是对应一周中的哪一天. 输入为三个整数: day、month 和 year, 分别表示日、月、年, 您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}

来自 LC: 1185.一周中的第几天 (opens new window)

# 土办法

var dayOfTheWeek = function (day, month, year) {
  const aWeekTxt = ["Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday", "Saturday"]
  return aWeekTxt[new Date(year, month - 1, day).getDay()]
};
1
2
3
4
5

你以为是在考验你是不是API战士吗？

# 聪明人的操作

基姆拉尔森计算公式（Kim larsen calculation formula）

# 最终结论

function getWeek(y, m, d) {
  // 把一月和二月看成是上一年的十三月和十四月
  if (m < 3) {
    m += 12;
    --y;
  }
  return (d + 1 + 2 * m + Math.floor(3 * (m + 1) / 5) + y +
    Math.floor(y / 4) - Math.floor(y / 100) + Math.floor(y / 400)) % 7;
}
var dayOfTheWeek = function (day, month, year) {
  const aWeekTxt = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
  return aWeekTxt[getWeek(year, month, day)];
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 推导

  1. 设定

    • y -- 年
    • m -- 月
    • d -- 日
    • w -- 星期
    • 初始日期: 1年1月1日 星期一

  2. 第一个月

    不出现任何年月变化

    w = d % 7

  3. 对于年

    • 不考虑闰年

      在不考虑闰年的情况下, 一年365天, 365 % 7 = 1, 就是说一年的第一天和最后一天是相同的

      等价于, 下一年的第一天星期几是会比这一年的最后一天 +1 的

      因为这里是从1年开始, 所以年份增加在星期上的偏移量就为 y - 1, 即每增加一年, 星期就增加 y - 1

      w = (d + y - 1) % 7

    • 考虑闰年

      因为闰年会多出来一天, 所以相当于, 计算当前年份前面有多少个闰年, 将日期数 w 额外 +1

      计算之前的闰年年数的公式为:

      Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400)

      即:

      w = (d + y - 1 + Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400)) % 7

  4. 对于其它月份

    假设每个月都是28天, 28 % 7 = 0, 也就是说每个月的 w 是相同的，按正常月份计算，一月是31天, 比28多3天, 也就是说, 2月的 w 值, 是应该比1月按28计算的往后推迟3天，三月的值, 因为二月刚好28天, 不影响, 相当于还是推后3天, 以此类推，因为12月已是最后一个月, 所以不用考虑12月的误差天数, 同理, 1月份的误差天数是0, 因为前面没有月份影响它

    误差表

    月 误差 累计 模7
    1 3 0 0
    2 0 3 3
    3 3 3 3
    4 2 6 6
    5 3 8 1
    6 2 11 4
    7 3 13 6
    8 3 16 2
    9 2 19 5
    10 3 21 0
    11 2 24 3
    12 3 26 5

    用数组记录偏移量 offset = [0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5]

    即:

    w = (d + y - 1 + Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400) + offset[m - 1]) % 7

    如果当前年是闰年, 并且月份在二月之后, 那么月份造成的偏移量需要加1

    offset[m - 1] + 1

var dayOfTheWeek = function (d, m, y) {
  const offset = [0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5]
  let week = (d + y - 1 + Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100)
    + Math.floor((y - 1) / 400) + offset[m - 1]) % 7
  if (m > 2 &&
    (y % 4 === 0 && y % 100 !== 0 || y % 400 === 0)
    && y !== 0) {
    week++
  }
  return week % 7
};
1
2
3
4
5
6
7
8
9
10
11

# 改进

计算闰年数的子项 Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400) 没有包含当年，如果将当年包含进去，则实现了如果当年是闰年，w 自动加1。

由此带来的影响是如果当年是闰年，只是2月份多一天，3月开始才是正常的，所以在前面的1,2月份的计算多的一天误差我们应该减去

var dayOfTheWeek = function (d, m, y) {
  const offset = [0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5]
  let week = (d + y - 1 + Math.floor(y / 4) - Math.floor(y / 100)
    + Math.floor(y / 400) + offset[m - 1]) % 7
  if (m > 3 &&
    (y % 4 === 0 && y % 100 !== 0 || y % 400 === 0)
    && y !== 0) {
    week--
  }
  return week % 7
};
1
2
3
4
5
6
7
8
9
10
11

与前一段代码相比，我们简化了 w 的计算部分。实际上还可以进一步将常数 -1 合并到误差表中，但我们暂时先不这样做。

现在我们推导出了自己的计算星期的算法了，但还不能称之为公式。

所谓公式，应该给定年月日后可以手工算出星期几的，但我们现在的算法需要记住一个误差表才能进行计算，所以只能称为一种算法，还不是公式。

下面，我们试图消掉这个误差表

# 消除闰年判断的条件表达式

由于闰年在2月份产生的误差，影响的是后面的月份计算。如果2月是排在一年的最后的话，它就不能对其它月份的计算产生影响了。可能已经有人联想到了文章开头的公式中为什么1,2月转换为上年的13,14月计算了吧

就是这个思想了，我们也将1,2月当作上一年的13,14月来看待。

由此会产生两个问题需要解决：

  • 一年的第一天是3月1日了，我们要对 w 的计算公式重新推导
  • 误差表也发生了变化，需要得新计算
  1. 推导 w 计算式

用前面的算法算出 1年3月1日是星期4

第一个月（即3月）

w = (d+3) % 7

扩展到每一年的三月份

w = (d + 3 + y - 1 + Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400)) % 7

即：

w = (d + 2 + y + Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400)) % 7

误差表

月 误差 累计 模7
3 3 0 0
4 2 3 3
5 3 5 5
6 2 8 1
7 3 10 3
8 3 13 6
9 2 16 2
10 3 18 4
11 2 21 0
12 3 23 2
13 3 26 5
14 0/1 29 1

用数组记录偏移量 offset = [0, 3, 5, 1, 3, 6, 2, 4, 0, 2, 5, 1]

扩展到其他月份

w = (d + 2 + y + Math.floor((y - 1) / 4) - Math.floor((y - 1) / 100) + Math.floor((y - 1) / 400) + offset[m - 3]) % 7 (3 <= m <= 14)

将y-1简化：

w = (d + 2 + y + Math.floor(y / 4) - Math.floor(y / 100) + Math.floor(y / 400) + offset[m - 3]) % 7 (3 <= m <= 14)

这个式子如果当年是闰年，会造成多1的误差，但我们将1,2月变换到上一年的13,14月，年份要减1，所以这个误差会自动消除，所以得到下面的算法：

var dayOfTheWeek = function (d, m, y) {
  const offset = [0, 3, 5, 1, 3, 6, 2, 4, 0, 2, 5, 1]
  if (m < 3) {
    m += 12
    y--
  }
  return (d + 2 + y + Math.floor(y / 4) - Math.floor(y / 100) + Math.floor(y / 400) + offset[m - 3]) % 7
};
1
2
3
4
5
6
7
8

我们可以看到这个方法和前面的几乎是一样的，仅仅是误差天和一个常数的差别，常数的区别是由起始日期的星期不同引起的，1年1月1日星期一，1年3日1日星期四，有三天的差别，所以常数也从 -1 变成了 2。

现在，我们成功的消除了繁琐的闰年条件判断。

# 消除误差表

假如存在一种 m 到 offset 的函数映射关系，使得

offset[m-3] = f(m)

则我们就可以用 f(m) 取代 offset[m-3]，也就消除了误差表。

由于误差表只有12个项，且每一项都可以加减 7n 进行调整，这个函数关系是可以拼凑出来的。结果如下：

for (let m = 1; m <= 14; m++) {
  console.log((-1 + 2 * m + Math.floor((3 * (m + 1)) / 5)) % 7);
}
1
2
3

输出结果后面的12项刚好和误差表一样

现在就简单的，将 f(m) = -1 + 2 * m + Math.floor((3 * (m + 1)) / 5) 代入公式，得到

w = (d + 2 + y + Math.floor(y / 4) - Math.floor(y / 100) + Math.floor(y / 400) + -1 + 2 * m + Math.floor((3 * (m + 1)) / 5)) % 7

约束条件: m = 1, m = 2 时 m = m + 12, y = y - 1;

化简得到：

w = (d + 1 + 2 * m + Math.floor((3 * (m + 1)) / 5) + y + Math.floor(y / 4) - Math.floor(y / 100) + Math.floor(y / 400)) % 7

# 验证公式的正确性

一个月中的日期是连续的，只要有一天对的，模7的关系就不会错，所以一个月中只须验证一天就可以了，一年需要验12天。由于扩展到年和月只跟是否闰年有关系，就是说至少要验证一个平年和一个闰年，也就是最少得验证24次。

最近更新: 2023年03月21日 14:47:21

LeetCode之买卖股票问题