情報基礎A 「Cプログラミング」（ステップ５・ピタゴラス数探し）

このページの目標

• 多重ループ構造を含むプログラムが、その変数の動きとともに、理解できる。
• 問題解決に向けての複数のアルゴリズムの存在、およびそれらの効率（計算量）について意識し、それらをプログラムに反映できること。

１．効率的なアルゴリズムの選択

　 練習：ピタゴラス数探し

a,b,c を整数としたとき $$ a^2 = b^2 + c^2 $$ を満たすような組$(a,b,c)$をピタゴラス数と呼ぶ。 $0< a,b,c < 100$ の範囲のピタゴラス数を探すプログラムを作成し、その範囲のピタゴラス数を全て列挙してみなさい。

　ヒント

$n>2$の場合には$a^n = b^n + c^n$を満たす整数の組 a,b,c は存在しない、という有名なフェルマーの定理がワイルズによって証明されたのは（数学の歴史上は）つい最近のこと。これに触れている書籍なども多い（例えば、「数学ガール・フェルマーの最終定理」（結城浩・ソフトバンク））。 つまり、$n>2$の場合に、$(a,b,c)$の組を探そうとしても、それははじめから無理と「分かって」いる。 $n=2$の場合には、この等式を満たすような$(a,b,c)$が無限個存在することが証明でき、ピタゴラス数と呼ばれている。

ピタゴラスを探すもっとも素朴な方法は「a,b,cをそれぞれ1から100まで変化させてみて、実際に上の等式を満たすかどうかチェックし、もしそれを満たしたら画面のa,b,cの値をプリントする」というものだろう。そうすると、プログラムの骨格は

#include <stdio.h>
main( )
{
  int a,b,c ;
  for (aを１から１００まで変化) {
    for (bを１から１００まで変化) {
      for (cを１から１００まで変化) {
        if (等式が成り立つかどうか判定) {
           値をプリントして
        }
      }
    }
  }
}

のようになるだろう。for文が「三重ループ」になっている点に注目。

ただし、この方法はあまり効率が良くない。高々100までの範囲でも100×100×100=100万回の「チェック」をしなければならない。さらに大きな a,b,c にまで探索の範囲を拡大しようとすると、それなりの工夫が必要になるだろう。各自の技量と興味に応じて、計算方法（アルゴリズム）を考え、探索の範囲をさらなる拡大に挑戦してみよ。

考え方の例

• 等式が成り立つ場合には、a, b, cは直角三角形の辺の長さ（aが長辺）と解釈できるはず。すると、そもそも三角形を構成できないようなa,b,cの組については調べる必要がないはずだ。
• b,cがともに偶数であれば、aはかならず偶数。b,cがともに奇数の場合もaは必ず偶数。つまり、これらの場合に奇数のaを調べる必要はない。等々。
• 例えば、a = x + y , b = x - y のように変数変換してから考えてみると、新しい「作戦」を編み出せないだろうか。

0 < a,b,c < N の範囲で検索した場合、作製したプログラムを使うとおよそ何回のチェックが行われるのか（これを計算量と呼ぶ）を見積もってみなさい。

腕に覚えのある者は、a,b,cが互いに素（最大公約数が1）であるようなa,b,cの組（原始ピタゴラス数）のみを出力するよう、プログラムを改造してみなさい。 最大公約数を計算するためのよく知られたアルゴリズムとして、ユークリッドの互除法がある。詳しくは 情報基礎A講義ノート を参照。