我目前正在处理 USACO 网站上的一个问题(十三号星期五),我编写了一个程序,给定一个数字 N,计算从 1900 年 1 月 1 日到 12 月的一周中的每一天,第 13 号降落的频率31st,1900+N-1. 该算法的灵感来自心算技巧:http ://www.jimloy.com/math/day-week.htm
要记住的事情:1900 年 1 月 1 日是星期一。30 天有 9 月、4 月、6 月和 11 月,其余的都有 31 天,除了 2 月有 28 天,闰年有 29 天。每年能被 4 整除的是闰年(1992 = 4*498 所以 1992将是闰年,但 1990 年不是闰年)以上规则不适用于世纪年。能被 400 整除的世纪年是闰年,其他都不是。因此,世纪年 1700、1800、1900 和 2100 不是闰年,但 2000 年是闰年。*
该程序运行良好,除非 N=256(1900 到 2156)我的程序输出:440 438 439 439 437 439 440
在 USACO 上,有:440 439 438 438 439 439 439
该程序将包含 N 的文件 (friday.in) 作为输入,并在另一个文件 (friday.out) 的一行中输出七个空格分隔的整数,表示每天(从星期六开始)出现的次数。
我已经放了几个 cout 用于调试目的。
这是代码:
/*
ID: freebie1
PROG:friday
LANG: C++
*/
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
class Date
{
public:
Date(int month=0,int year=0):m_month(month),m_year(year)
{
}
int monthDiff()
{
if(m_month<=3)
{
if(m_month==1)
{
return 0;
}
else if(m_month==2)
{
return 31;
}
}
if(m_month>=3)
{
if((m_year%4==0 && m_year%100!=0)||(m_year%100==0 && m_year%400==0))
{
if(m_month<9)
{
if(m_month%2==0)
return 60+(31*int(m_month/2.6)+30*(int(m_month/2.6)-1));
else
return 60+(61*int(m_month/3.5));
}
else if(m_month>=9)
{
if(m_month%2==0)
return 91+61*(m_month/3);
else
return 91+(31*int(m_month/2.75)+30*int(m_month/3.6));
}
}
else
{
if(m_month<9)
{
if(m_month%2==0)
return 59+(31*int(m_month/2.6)+30*(int(m_month/2.6)-1));
else
return 59+(61*int(m_month/3.5));
}
else if(m_month>=9)
{
if(m_month%2==0)
return 90+61*(m_month/3);
else
return 90+(31*int(m_month/2.75)+30*int(m_month/3.6));
}
}
}
}
void show()
{
cout<<m_month<<"/"<<m_year<<": ";
}
int tellDay()
{
int daysInYears=int((m_year-1900))*365;
int daysInMonths=this->monthDiff();
int leapDays;
if(m_year%4==0 && m_year!=1900)
leapDays=int((m_year-1900)/4)-1;
else if(m_year>2100)
leapDays=int((m_year-1900)/4)-1;
else if(m_year>2200)
leapDays=int((m_year-1900))/4-2;
else
leapDays=int((m_year-1900))/4;
int days=13+leapDays;
int res=daysInYears+daysInMonths+days;
cout<<"MonthDiff: "<<this->monthDiff()<<" In years: "<<daysInYears<<" days: "<<days<<" ";
return res%7;
}
private:
int m_month;
int m_year;
};
int main()
{
ifstream fin("friday.in");
ofstream fout("friday.out");
if(fin)
{
int n(0),day(0),sMonth(1),sYear(1900);
fin>>n;
vector<int> weekDays(7,0);
for(int i(0);i<n;i++)
{
for(int j(0);j<12;j++)
{
Date date(sMonth+j,sYear+i);
day=date.tellDay();
date.show();
cout<<day<<endl;
switch(day)
{
case 0:
weekDays[1]+=1;
break;
case 1:
weekDays[2]+=1;
break;
case 2:
weekDays[3]+=1;
break;
case 3:
weekDays[4]+=1;
break;
case 4:
weekDays[5]+=1;
break;
case 5:
weekDays[6]+=1;
break;
case 6:
weekDays[0]+=1;
break;
}
}
}
for(int i(0);i<6;i++)
{
fout<<weekDays[i]<<" ";
}
fout<<weekDays[6]<<endl;
}
return 0;
}