Project Euler——Problem 19

daybreakcx posted @ 2009年7月21日 04:57 in Prject Euler , 1135 阅读

原题与答案：

Problem 19

14 June 2002

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Answer:171

分析与解答：

原题的意思是告诉了1900年1月1日是星期一，还有31日的月份，二月在闰年29天，平年28天，闰年是指年份被4整除，但是世纪年时必须被400整除的年份。最后根据这些已知的条件求20世纪（1901年1月1日到2000年12月31日）每个月第一天是星期天的数目。这题很简单，直接枚举就能得到解答，但是要注意题目中给定的是1900年1月1日是星期天，要转换为1901年1月1日开始，其实不难，只要加上1900年的天数365对7取余就得到1901年1月1日是星期几了，当然我们用0表示星期天。如下是我的源程序代码：

#include<stdio.h>
int days[12]={31,28,31,30,31,30,31,31,30,31,30,31},i,j,ans,cur;
int main()
{
ans=0;
cur=(1+365)%7;
for (i=1901;i<=2000;i++)
for (j=0;j<12;j++)
{
if (cur==0) ans++;
cur+=days[j];
if (j==1&&(i%400==0||(i%100!=0&&i%4==0))) cur++;
cur%=7;
}
printf("%d\n",ans);
return 0;
}