Project Euler

Project Euler 問題39(整数の直角三角形)を解いてみる

760x428_Euler_039

Project Euler で紹介されている問題39を解いてみました。辺の長さが整数である直角三角形を求めていく問題です。

Project Euler 問題39(整数の直角三角形)

辺の長さが整数である {a,b,c} の直角三角形を考えて、その周囲の長さを p とします。p = 120 の解は以下の3通りが存在します。

{20, 48, 52}、{24, 45, 51}、{30, 40, 50}

p ≤ 1000 の範囲で、解の個数が最大になる p を求めよ。

考察

問題9で、p = 1000 の場合を解きました(解の個数は 1個でした)。この問題で作ったプログラムをベースにします。

解がある最小の p は 12 で、辺が {3, 4, 5} の場合に直角三角形になります。これから、p は、12 から 1000 の範囲で調べれば良いことが分かります。

解答例

ベースにしたプログラムは、a < b となるようにループさせています。これは、a = b の場合、二等辺三角形となり、斜辺が a の $\sqrt{2}$ 倍となり整数にならないからです。辺の合計 p を先に決めているため、c は、ループさせる必要がありません。結果的に3重ループとなりました。

以下は、C のプログラムです。

#include <stdio.h>

int main(void)
{
	int p, a, b, c;
	int result = 0;
	int max_solutions = 0;
	int temp_solutions;

	for (p = 12; p <= 1000; ++p) {
		temp_solutions = 0;
		for (a = 1; a <= (p/3); ++a) {
			for (b = a + 1; b <= (p/2); ++b) {
				c = p - (a + b);
				if (b < c) {
					if (a * a + b * b == c * c) {
						++temp_solutions;
					}
				}
			}
		}
		if (temp_solutions > max_solutions) {
			max_solutions = temp_solutions;
			result = p;
		}
	}

	printf("Problem039: %d\n", result);
//	printf("Problem039: %d has %d solutions\n", result, max_solutions);

	return 0;
}

コメントアウトしている29行を実行すると、8通りの解があることが分かります。

最後に

この問題は、中学生でも理解できますが、実際に解くにはプログラムが必要となります(筆算では計算量的に難しい)。このような問題がプログラミング導入に良いのかもしれません。

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

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA