usaco：星期五的十三错误 [英] usaco: friday the thirteen error
问题描述
我目前正在USACO网站上处理问题（第13个星期五），并且我编写了一个程序，给出一个数字N，该程序计算从1月1日起，每周的第13天登陆的频率， 1900年至1900年12月31日，N + 1。该算法的灵感来自一种心理计算技巧： http://www.jimloy.com/math/day-week.htm
注意事项：
1900年1月1日在星期一。
三十天分别是9月，4月，6月和11月，其余所有31天，其中2月除外，其中2月有28个，但years年只有29个。
每年被4整除的年份是is年（1992 = 4 * 498，因此1992年将是leap年，但1990年不是is年）
上述规则在世纪年内不成立。被400整除的世纪年是leap年，其他所有年份都不是。因此，世纪1700、1800、1900和2100不是leap年，而2000是is年。*
该程序运行良好，除非N = 256（ 1900年至2156年）
我的程序输出：
440438439439439437439440
在USACO上有：
440 439 438 438 439 439 439 439
程序将包含N的文件（friday.in）作为输入，并输出七个空格分隔的整数，分别表示每天的出现次数（
我为调试目的放置了多个cout。
代码如下：
/ *
ID：freebie1
PROG：friday
LANG：C ++
* /
#include< fstream>
#include< vector>
#include< iostream>
使用命名空间std;
班级日期
{
public：
Date（int month = 0，int year = 0）：m_month（month），m_year（year）
{
}
int monthDiff（）
{
if（m_month< = 3）
{
if（m_month == 1 ）
{
返回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）
返回60+（31 * int（m_month / 2.6）+ 30 *（int（m_month / 2.6）-1））;
else
返回60+（61 * int（m_month / 3.5））;
}
else if（m_month> = 9）
{
if（m_month％2 == 0）
返回91 + 61 *（m_month / 3）;
else
返回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
返回59+（61 * int（m_month / 3.5））;
}
else if（m_month> = 9）
{
if（m_month％2 == 0）
返回90 + 61 *（m_month / 3）;
else
返回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 jumpDays；
if（m_year％4 == 0&& m_year！= 1900）
jumpDays = int（（m_year-1900）/ 4）-1;
else if（m_year> 2100）
jumpDays = int（（m_year-1900）/ 4）-1;
else if（m_year> 2200）
jumpDays = int（（m_year-1900））/ 4-2;
else
jumpDays = int（（m_year-1900））/ 4;
int days = 13 + leapDays;
int res = daysInYears + daysInMonths + days;
cout<< MonthDiff：< this-> monthDiff（）<<年：<< daysInYears<<天：<< days< <;
返回res％7;
}
私人：
int m_month;
int m_year；
};
int main（）
{
ifstream fin（ friday.in）;
的流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（sMonth + j，sYear + i）;
day = date.tellDay（）;
date.show（）;
cout<< day<< endl;
switch（day）
{
case 0：
weekDays [1] + = 1;
休息时间；
情况1：
weekDays [2] + = 1;
休息时间；
情况2：
weekDays [3] + = 1;
休息时间；
情况3：
weekDays [4] + = 1;
休息时间；
情况4：
weekDays [5] + = 1;
休息时间；
情况5：
weekDays [6] + = 1;
休息时间；
情况6：
weekDays [0] + = 1;
休息时间；
}
}
}
for（int i（0）; i <6; i ++）
{
fout<< weekdays [i]<;
}
fout<< weekDays [6]<< endl;
}
返回0；
}
您从205得到了错误的结果年，即从2104年开始。
if（m_year％4 == 0&& m_year！= 1900 ）
jumpDays = int（（m_year-1900）/ 4）-1;
对于被4整除的年份，您不减去非the年2100、2200、2300
修复：
if（m_year％4 == 0&& m_year！= 1900）
jumpDays = int（（m_year-1900）/ 4）-1 +（m_year-1604）/ 400-（m_year-1904） / 100;
减去它们。这样会导致错误的leaves年计数在2300年之后不能被4整除，您可以通过添加类似的更正来进行更正（然后不需要多个分支）：
else
jumpDays = int（（m_year-1900）/ 4）+（m_year-1600）/ 400-（m_year-1900）/ 100;
该公式将确定在之间 1900年过去的years年数和 m_year 。如果 m_year 不是4的倍数，则简单的 4的倍数是leap年得出的计数为（m_year-1900）/ 4 。但这没有考虑到100的倍数通常不是not年，因此我们减去在这之间相隔的年数，-（m_year-1900）/ 100 。但是，现在也减去了 leap年的400的倍数，因此加回它们的计数， +（m_year-1600）/ 400 （这里的基准年是1600，不是1900年以后的400的最大倍数。）
对于4的倍数，我们必须纠正以下事实：当前年份不是在当前年份之前是
更好的解决方法是： leap年计数统一（无分支）：
int jumpDays =（m_year-1901）/ 4 +（m_year-1601）/ 400-（m_year-1901）/ 100;
I'm currently working on a problem (Friday the thirteenth) on the USACO site and I've coded a program which, given a number N,computes how often the 13th lands on each day of the week from Jan 1st,1900 to Dec 31st,1900+N-1.The algorithm is inspired from a mental calculation trick : http://www.jimloy.com/math/day-week.htm
Things to keep in mind: January 1, 1900 was on a Monday. Thirty days has September, April, June, and November, all the rest have 31 except for February which has 28 except in leap years when it has 29. Every year evenly divisible by 4 is a leap year (1992 = 4*498 so 1992 will be a leap year, but the year 1990 is not a leap year) The rule above does not hold for century years. Century years divisible by 400 are leap years, all other are not. Thus, the century years 1700, 1800, 1900 and 2100 are not leap years, but 2000 is a leap year.*
The program works well except when N=256 (1900 to 2156) My program outputs : 440 438 439 439 437 439 440
while on USACO, there is: 440 439 438 438 439 439 439
The program takes a file (friday.in) containing N as input and outputs seven space separated integers representing the number of occurrences of each day (starting by Saturday) on one line in another file(friday.out).
I've put several cout for debugging purposes.
Here's the code:
/*
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;
}
You get wrong results from 205 years on, that is from the year 2104.
if(m_year%4==0 && m_year!=1900)
leapDays=int((m_year-1900)/4)-1;
For years divisible by 4, you don't subtract the non-leap years 2100, 2200, 2300, 2500, ... from the count.
Fix:
if(m_year%4==0 && m_year!=1900)
leapDays=int((m_year-1900)/4)-1 + (m_year-1604)/400 - (m_year-1904)/100;
subtract them. That leaves the wrong leap year count for years not divisible by 4 after 2300, you can correct that by adding a similar correction (and that doesn't need multiple branches then):
else
leapDays=int((m_year-1900)/4) + (m_year-1600)/400 - (m_year-1900)/100;
The formula shall determine the number of leap years that have passed between 1900 and m_year. If m_year is not a multiple of 4, the simple "multiples of 4 are leap years" gives that count as (m_year - 1900)/4. But that doesn't take into account that multiples of 100 are not leap years in general, so we subtract the number of such years that have passed in between, - (m_year - 1900)/100. However, now the multiples of 400 that are leap years have been subtracted too, so add their count back, + (m_year - 1600)/400 (base year here is 1600, the largest multiple of 400 not after 1900).
For multiples of 4, we have to correct for the fact that the current year is not a leap year before the current year, so I let the correction take place only after and shift the base years.
Better fix, making the leap year count uniform (no branches):
int leapDays = (m_year - 1901)/4 + (m_year-1601)/400 - (m_year-1901)/100;
这篇关于usaco：星期五的十三错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
