『Cプログラミング専門課程』目次第0章準備

準備 ■アルゴリズムの格差


ピタゴラスの定理は知っているでしょう。直角3角形の斜辺の長さの2乗は、 他の2辺の長さの2乗の和になる、という定理です。さらに、3辺の長さを整 数に限定しましょう。きちんと書くと、

a*a + b*b == c*c ( a>0, b>0, c>0 さらに a,b,cは互いに素 )

を満たす整数の組を求める問題です。(3,4,5),(5,12,13)のような組がありま す。(6,8,10)は全ての数を2で割ることにより(3,4,5)になるので、このような 公約数のある場合は除きます。こういう3整数の組を「ピタゴラス数」と呼び ます。

次のプログラムは、1000以下の整数の組でできるピタゴラス数を求めていま す。はっきりいって、極めて下手なプログラムです。正しく動作しますが、極 めて遅い。1000以下ならば、まだ全組み合わせが求まるまで待つ気にもなるで しょうが、10000以下の場合にはとてもできません。このプログラムは、改善 するとどのくらい高速になるでしょうか。解答例は巻末に掲載していますが、 すぐ見ずに、自分で改良してみるなり、数学書を捜すなりしてみてください。

サンプルプログラム pythago1.c ピタゴラス数(低速版)


Copyright1996 Hirofumi Fujiwara. No reproduction or republication without written permission
『Cプログラミング専門課程』目次第0章準備