Project Euler 問題19（日曜日を数える）を解いてみる

Project Euler で紹介されている問題19を解いてみました。その月の日数をカウントして解答を求めていきます。うるう年の処理もします。

Project Euler 問題19（日曜日を数える）

準備

1901年1月から2000年12月までの月初めの日の曜日を調べていく問題です。1900年1月1日からの日数を求めて、その日数が7で割り切れば月曜日となります。7で割って6余れば、日曜日となります。

うるう年によって、その月が持つ日数が変わります。それを二次元配列で表現しておきます。この表現は、「プログラミング言語C 第2版」（B.W.カーニハン/D.M.リッチー著 石田晴久監訳 共立出版 1989年）第5章の例を参考にしました。

int daytable [2][12] = {
	{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
	{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};

2次元配列の最初の添え字は、うるう年以外の場合は0、うるう年の場合は1となるように設定します。次の添え字を（調べたい月ー1）とすれば、その月が持つ日数となります。

うるう年の判断

うるう年の判断を間違うことによる不具合は、現実でも発生しています（「うるう年 バグ」で検索してみてください）。問題文の記述と逆に考えたほうが分かりやすいかもしれません。

1. 400で割り切れる年は、うるう年
2. それ以外で100で割り切れる年は、うるう年ではない。
3. それ以外で4で割り切れる年は、うるう年
4. それ以外の場合は、うるう年ではない。

うるう年以外の場合は0、うるう年の場合は1に変数を設定するには、比較演算子と論理AND演算子、論理OR演算子を使って、以下のように書けます。

leap = (year % 400 == 0)||((year % 100 != 0)&&(year % 4 == 0));

一方、1901年から2099年までは、以下のように書いても、結果的には正しくなります。今回は、1901年から2000年までのうるう年が判定できればよいので、簡明なこちらを採用する考えもあります。

leap = (year % 4 == 0);

解答例

準備で用意した材料を使って問題を解いてみます。1900年1月1日からの日数を変数 days に格納しています。Cでの実装となります。

#include <stdio.h>

int daytable [2][12] = {
	{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
	{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};

int main(void)
{
	int year, month, leap, days;
	int answer = 0;

	days = 365; /* 1 Jan 1901 */

	for (year = 1901; year <= 2000; ++year) {
		leap = (year % 400 == 0)||((year % 100 != 0)&&(year % 4 == 0));
		for (month = 0; month < 12; ++month) {
			if (days % 7 == 6) {
				++answer;
			}
			days += daytable[leap][month];
		}
	}

	printf("Problem019: %d\n", answer);

	return 0;
}

1900年1月1日からの日数（days）を7で割って6余れば日曜日となります。その条件で解答をインクリメントしています。

最後に

少し古い話ですが、「2000年問題」と呼ばれる問題が発生しました。古いシステムは西暦を下2桁しか保持しておらず、2000年1月1日を1900年1月1日（または別の年）と判断してしまい、システムが正しく動作しなくなるという問題です。

また、2000年はうるう年なので2000年2月29日は存在するのですが、うるう年の判定を間違えて、2月28日の次が3月1日になってしまう不具合も発生したようです。

次に問題になるのは、2100年です。この年はうるう年ではないので、2月28日の次は3月1日になります。人類が2100年をどう迎えるかは想像も難しいですが、この問題がどれくらい発生するかは、個人的には興味があります。

次回は、この問題の別解を紹介します。