ピタゴラスの定理

[えんぱ]

ピタゴラスの定理を満たすa,b,cを求める問題で、条件はbとcは100未満でｂ＜ｃの関係を持つことなんですが、
一度考えてみたのですが、２重ループを使えばいいのはわかるのですが、aをどのようにすればうまく求めることが出来ますか？

#include<stdio.h>
int main(void)
{
int a, b, c;

for (a = 0; a < 100; a++){
for (b = 1; b < 100; b++){
for (c = 0; c < 100; c++){
if (a*a == b*b + c*c);
printf("a=%d,b=%d,c=%d", a, b, c);
}
}
}
return 0;
}

[みけCAT]

二分探索をするのがいいでしょう。

コード:

#include<stdio.h>

int sqrti(int x)
{
	int l, r, m;
	l = 0; r = x;
	while (l <= r){
		m = (l + r) / 2;
		if (m*m == x){
			return m;
		} else if (m*m < x){
			l = m+1;
		} else{
			r = m-1;
		}
	}
	return -1;
}

int main(void)
{
	int a, b, c;

	for (b = 1; b < 100; b++){
		for (c = b+1; c < 100; c++){
			a = sqrti(b*b + c*c);
			if (a >= 0)
				printf("a=%d,b=%d,c=%d\n", a, b, c);
		}
	}
	return 0;
}

[YuO]

ピタゴラスの定理を満たすa,b,cを求める問題で、条件はbとcは100未満でｂ＜ｃの関係を持つことなんですが、
一度考えてみたのですが、２重ループを使えばいいのはわかるのですが、aをどのようにすればうまく求めることが出来ますか？

えーっと，a, b, cに他の条件はないのでしょうか。
少なくとも，b, cについて整数という条件が付いていないと無限に解が出てくるのですが。

とりあえず，

• a, b, cがすべて正整数
  ※三角形の辺の長さが0以下はありえない
• aが直角三角形の斜辺

という条件を付けます。

この条件下で，まず，b と cの取り得る値の範囲は簡単に定まります。
つまり，

• b : 1 以上 100 未満 の 整数
  ※実質的には99未満
• c : b より大きく 100 未満 の 整数

です。

次に，aは三角形の性質から取りうる値の範囲を決定できます。
直角三角形の斜辺ですから，a > b と a > c の両方を満たします。
b < c ですから，a > c > bとなります。
また，残り2辺の長さの和以上になると三角形になりませんから，a < b + cも満たす必要があります。
つまり，

• a : c より大きく b + c 未満 の 整数

です。

aは確かにbとcから計算で求める事が出来ますが，範囲が定まっているので，その範囲内をループで回す事で探す事ができます。
再度条件を書くと，

• a : c より大きく b + c 未満 の 整数
  →a の範囲は b と c に依存する
• b : 1 以上 100 未満 の 整数
  →b の範囲は確定している
• c : b より大きく 100 未満 の 整数
  →c の範囲は b に依存する

となっていますから，三重のfor文をb, c, aの順で書き，ピタゴラスの定理を満たすかどうかを判別する事で，aを回りくどいですが求める事が出来ます。