Project Euler 問題28（スパイラルの対角線上の数）を解いてみる

Project Euler で紹介されている問題28を解いてみました。並ぶ数字の法則性をみつけて解きます。

Project Euler 問題28（螺旋に並ぶ対角線上の数）

解答例

対角線上にある数を並べます。

　1
　→ 3 → 5 → 7 → 9 　ここまで差分は2、次の数は4加える。
　→ 13 → 17 → 21 → 25　ここまで差分は4、次の数は6加える。
　→ 31 → 37 → 43 → 49　ここまで差分は6、次の数は8加える。

螺旋の周回が1周増えると、対角線上に並ぶ数の差分は2増えます。これは周の一辺が2増えるためです。100Ⅰ×1001の螺旋の場合、差分は1000となります。

この法則に従って、対角線上の数字を加えていきます。以下は、C のプログラム例です。答えとなる和は、あるふれる可能性があるため、long long int 型にしました（結果的に、和は32ビット整数の範囲に入っていました）。

#include <stdio.h>

int main(void)
{
	int i, next, diff;
	long long int sum;

	next = 1;
	diff = 2;
	sum = 1;
	while (diff <= 1000) {
		for (i = 0; i < 4; ++i) {
			next += diff;
			sum += next;
		}
		diff += 2;
	}

	printf("Problem028: %lld\n", sum);

	return 0;
}

法則が明確なため、プログラムはすっきり書けています。

最後に

この問題は、その前の問題26、27と比較して多くの人が解いていました。螺旋状に並べた数字列をみていると法則が分かるため、取り組みやすいのかもしれません。

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