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

前回は、Project Euler で紹介されている問題19を解いてみました。今回は、別解として汎用的な方法（ツェラーの公式）を紹介します。

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

準備（ツェラーの公式）

前回は、1900年1月1日が月曜日であることを使って解きました。ツェラーの公式を使えば、年と月と日が分かれば直接曜日が分かります。

ツェラーの公式は、いろいろな表現があるようです。この記事では、英語版の Wikipedia に掲載されている式を採用しました。

$$h = \left(q + \left\lfloor \frac{13(m+1)}{5} \right\rfloor + K +
\left\lfloor \frac{K}{4} \right\rfloor +
\left\lfloor \frac{J}{4} \right\rfloor -\, 2J \right) \bmod 7$$

• h は曜日を表します。日曜日=0、月曜日=1、…、土曜日=6 となります。
• q は日を表します。
• m は月を表します。ただし、1月は前の年の13月、2月は前の年の14月とします。
• K は西暦の下2桁を表します。
• J は西暦を100で割った値を表します。
• $\lfloor$ と $ \rfloor$ は、整数の切り捨てを表します。
• $\bmod 7$ は、7で割った余りを表します。

この式は、グレゴリオ暦（1582年以降）であれば使えます。グレゴリオ暦に切り替わる前のユリウス暦の場合は、公式が異なるため注意が必要です。

解答例（別解）

ツェラーの公式を忠実に実装して、1901年1月から2000年12月までの月初めの曜日を求めて、日曜日の場合は、解答（answer）をインクリメントします。以下は、Cでの実装となります。

#include <stdio.h>

int day_of_week(int year, int month, int day)
{
	int K, J;

	if (month <= 2) {
		month += 12;
		--year;
	}
	K = year % 100;
	J = year / 100;

	return (day + (13 *(month + 1))/ 5 + K + K / 4 + J / 4 - 2 * J) % 7;
}

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

	for (year = 1901; year <= 2000; ++year) {
		for (month = 1; month <= 12; ++month) {
			if (day_of_week(year, month, 1) == 0) {
				++answer;
			}
		}
	}

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

	return 0;
}

ツェラーの公式を使っているため、main の実装は簡単なものになっています。

最後に

ツェラーの公式を調べる中で、ユリウス暦とグレゴリオ暦について理解することができました。

簡単に言うと、ユリウス暦はうるう年を4年に1回としていたため、実際の太陽年を考慮すると、うるう年が多くなりすぎます（グレゴリオ暦のうるう年については前回の記事をご覧ください）。このため16世紀末には10日ほどずれることになりました。このため、1582年10月4日（木）の翌日を10月15日（金）としたようです。

日本でも、太陰暦を太陽暦に切り替えたため、明治5年（西暦1872年）12月2日の翌日を明治6年1月1日としました（明治改暦）。

いま、このような改暦を行うと、コンピュータシステムの影響がとんでもないことになりそうです。

引き続き、Project Euler の問題を紹介していきます。