方法一:
模拟法:
$\color{red}{从1900年开始,按天递推到最后一天。}$
$\color{red}{中间根据年份,月份算出每个月的天数。}$
$\color{red}{遍历一边,如果日期是 13 号,对应的星期数 加 1。}$
//cpp
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a[7] = {0};//记录星期出现次数
int week = 1;
for (int y = 1900; y < 1900 + n ; y++)
{
for (int m = 1; m <= 12; m++)
{
int d;
if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12)//根据年与月算该月有多少天
{
d = 31;
}
else if (m == 2)
{
if ((y % 100 != 0 && y % 4 == 0) || (y % 400 == 0))
d = 29;
else d = 28;
}
else
d = 30;
for (int i = 1; i <= d; i++)
{
week++;
if (i == 13)//如果是 13 号,对应的星期出现次数加 1
a[week % 7] ++;
}
}
}
for (int i = 0; i < 7; i++) cout << a[i] << " ";
cin >> n;
}
时间复杂度 O(365n)
方法二:
$\color{red}{基母拉尔森公式:}$ https://baike.so.com/doc/2738265-2890169.html
W= (d+2m+3(m+1)/5+y+y/4-y/100+y/400+1)%7 //C++计算公式
在公式中d表示日期中的日数,m表示月份数,y表示年数。
注意:在公式中有个与其他公式不同的地方:
把一月和二月看成是上一年的十三月和十四月,例:如果是2004-1-10则换算成:2003-13-10来代入公式计算。
输入年月日到公式,返回当天的星期数。
//cpp
#include <iostream>
using namespace std;
int week(int y, int m, int d)
{
if (m == 1 || m == 2)
m = m + 12, y--;
return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400 + 1) % 7;//公式
}
int main()
{
int n = 0;
cin >> n;
int weekday[7] = {0};//存储星期的天数
for (int y = 1900; y < 1900 + n; y++)
for (int m = 1; m <= 12; m++)
{
int w = week(y, m, 13);//公式计算每一年,每一月的13号是星期几
weekday[w]++;//对应星期天数加 1
}
for(int i = 6; i < 6 + 7; i++)
cout << weekday[i % 7] << " ";
return 0;
}
时间复杂度 O(12n)
有问题直接评论即可
欢迎点赞`
方便理解
蓝桥杯押题
哇!居然还有公式……%%%
厉害,第二个公式闻所未闻
----- 来自一个AC SABER输在了这题的屑
O(12n)中12必须省略吧
tql
这个还有公式,神了!
一个公式,就能在数学界留名了