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 の問題を紹介していきます。
