情報基礎A 「Cプログラミング」（ステップ５）

このステップの目標

多重ループ構造の変数の動きを「シミュレーション」し、プログラムの挙動を予測できる。
入出力、式の計算、ループと条件分岐を組み合わせ、複雑な流れのプログラムを構成できる。

1. 多重ループ構造を持つプログラムの基本動作

ある程度実用的なプログラムは、反復する内容が反復処理になっている、言い換えると、多重のループ構造になっているケースが多い。少ない指示（プログラムの記述量）でひたすら繰り返し計算を行うのがコンピュータの使命だとしたら、これはある意味で必然である。そんな多重ループの簡単な例として、次のプログラム（の一部)の動作を考えてみよう：

for (i=1 ; i <= 3 ; i=i+1) {
   for (j=1 ; j <= 3 ; j=j+1) {
      printf("i=%d j=%d\n",i,j) ;
   }
}

変数iを動かしている「外側」のforループが反復する内容は、内側の変数jについてのfor文

for (j=1 ; j <= 3 ; j=j+1){
  printf("i=%d j=%d\n",i,j) ;
}

である。そうすると、まずiが1の状態で、内側のfor文が実行され、jが1から3までカウントアップされる。それが終わると、次にiが2になった状態で、再びjが1から3まで・・・・、という処理が繰り返される。（これらiやjは、ループ動作を司る変数という意味で、ループ変数と呼ばれる。）

この様子をまとめると、それぞれのループ変数の動きは以下のようになる：

i=1 j=1　　　　外側のループの１回目　内側のループの１回目
i=1 j=2　　　　　　　　　　　　　　　　　　　　　　２回目
i=1 j=3　　　　　　　　　　　　　　　　　　　　　　３回目
i=2 j=1　　　　外側のループの２回目　内側のループの１回目
i=2 j=2　　　　　　　　　　　　　　　　　　　　　　２回目
i=2 j=3　　　　　　　　　　　　　　　　　　　　　　３回目
i=3 j=1　　　　外側のループの３回目　内側のループの１回目
i=3 j=2　　　　　　　　　　　　　　　　　　　　　　２回目
i=3 j=3　　　　　　　　　　　　　　　　　　　　　　３回目

変数の変化を言葉で表すとすると、内側のjが外側のiよりも「はやく」（あるいは「先に」）動いている、と言えるだろう。

一般に、こうした多重ループでの変数の動きの基本的なイメージとして

多重ループは内側が「はやく」回る

を持つとよい。

試しに、上のプログラムをほんの少しだけ改変して（内側のループの継続条件に注目）

for (i=1 ; i <= 3 ; i=i+1) {
   for (j=1 ; j <= i ; j=j+1) {
       printf("i=%d j=%d\n",i,j) ;
   }
}

とすると、こんどは出力が

i=1 j=1　　　　外側のループの１回目　内側のループの１回目
i=2 j=1　　　　外側のループの２回目　内側のループの１回目
i=2 j=2　　　　　　　　　　　　　　　　　　　　　　２回目
i=3 j=1　　　　外側のループの３回目　内側のループの１回目
i=3 j=2　　　　　　　　　　　　　　　　　　　　　　２回目
i=3 j=3　　　　　　　　　　　　　　　　　　　　　　３回目

となる。内側のforでは for(j=1 ; j <= i ; j=j+1) となっているので、反復回数は変数 i が示す値になるわけだ。この例のように、内側のループでその「外側」のループ変数を使うプログラムもよく登場する。

こうしたループは何重にも入れ子にする（ネストする）ことができる。実用的な意味はないけれども、0000から9999までを一気にカウントアップしながら表示するプログラムは、以下のように書けるだろう。一番下の桁が、一番内側のループ変数に対応している点に注意：

"カウンター・プログラム"

右のプログラムを実行すると

のように表示される。


#include <stdio.h>
main()
{
  int d0,d1,d2,d3 ;
  for (d3=0; d3<=9; d3=d3+1) {
    for (d2=0; d2<=9; d2=d2+1) {
      for (d1=0; d1<=9; d1=d1+1) {
        for (d0=0; d0<=9; d0=d0+1) {
            printf("%d%d%d%d\n",d3,d2,d1,d0) ;
        }
      }
    }
  }
}

三角形を表示するプログラム

多重ループを使って、画面上に三角形を表示するプログラム例を以下に示す。

例題5(ex5.c)

*
**
***
****
*****
******
...

#include <stdio.h>
main()
{
   int i,j ;
   for (i=0; i<30 ; i=i+1) {
      for (j=0; j<i ; j=j+1) {
         printf("*") ;
      }
      printf("\n") ;
   }
}

プログラムの構造は、iとjをループ変数とする二重ループになっている。内側のループでは、アスタリスクを i 回プリントしており、おしまいに「改行」を出力している。外側のループでは、アスタリスクの個数に対応する変数 i が、0, 1, 2, 3,... ,29まで、順次変化する。その結果、行あたりの＊の個数が順に増えて、三角形に見えるわけだ。

　練習：三角形のバリエーション

以下の点について、頭の中でまず予想し、次いで、実際にプログラムを動かして確認してみなさい：

i < 30 の箇所を i < 10 に書き換えたら、結果はどのように変わるか
j < i の箇所を j < i*2 に書き換えたら、結果はどのように変わるか
三角形を逆向き（頂点が下向き）にするには、どこを変更したらよいか

亀場で練習：正６角形の繰り返し

タートルグラフィックスのページのページに紹介されている図形の例のうち、正６角形をずらして重ね合わせてできる図形を二重ループを使って描くプログラムを作成しなさい。

　ヒント

6角形の角度を60°ずつ変えながら、6回描けばよい。

2．二重ループを使った計算

少ない指示で計算機に沢山働いてもらう例として、素数のリストを作成するプログラムをここで作成してみよう。

そのために、まず、ある数nが素数かどうかを、プログラムで判定する方法を考えてみる。素数とは、自分自身と１以外では割り切れないような自然数だから、最も愚直な計算法（アルゴリズム）は

整数nが、2からn-1までの数(ここではmとしよう)で割り切れるかどうか順に調べ、割り切れる数（約数）の個数を数える。もし、約数の個数が０だったらnは素数である。

となるだろう。約数の個数を数え上げるには、もちろん、「総和のパターン」を使えばよい。

素数のリストを作成するには（n=1,2は自明だから、n=3から始め、n=1000の範囲まで調べるとすると）、次のような手順で計算を行えばよいはずだ。ここでcounterは、総和のパターンに従って約数の数を数え上げるために使う変数名とする。

n=3..1000まで繰り返す {
    counterを0にセット
    m=2..n-1まで繰り返す {
        もし、nがmで割り切れれば（約数が見つかったので）counterを1つ増やす
    }
    もし、counterが0だったら（約数の数が0だったら、nは素数なので）、nの値をプリント
}

つまり、プログラムの基本骨格は、nについてのループの中に、mについてのループが入り込んだ二重ループ構造となるはずだ。ここで、nが変化する都度、counterを0にセットしなければならない点にも、注意が必要である（さもないと、「以前」のnについてのcounterの値を引きずってしまう）。

　練習：素数探し

上に述べた手順に沿って、3から1000までの範囲で素数を探索し、一覧をプリントするプログラムを作成しなさい。

単にリストが表示されるだけではなく、「ヒント」を読んで、明らかに無駄な計算をしない工夫をプログラムに施すこと。

　ヒント

割り切れるかどうかのチェック

nがmで割り切れるかどうかを確認する作業をCのプログラムで記述すると、以下のようになるだろう（プログラムの一部分）：

	int n ;
	int m ;
	n=調べたい数 ;
	for (m=2 ; m<=n-1 ; m=m+1) {
	    if (n%m==0) { 
	    	printf("%d は %d で割り切れた\n",n,m) ;
	    }
	}

ここで、 n%m は「nをmで割った余り」である。つまり、条件文 if (n%m==0) は、「nがmで割り切れたなら（余りが０に等しければ）」という意味になる。

念のため、全体のプログラムのひな形を以下に示す：

#include <stdio.h>
main() {
    int n,m,flag ;
    setbuf(stdout,NULL) ;
    for (n=3 ; n<=1000 ; n=n+1) {
        ???????
        for (m=2 ; m<=n-1 ; m=m+1) {
            ??????
            ??????
            ??????
        }
        ???????
        ???????
     }
}

さらなるチューニング

上で述べた方法は、あまりスマートとは言えない。というのは、全てのnごとに、2からn-1までのmについて割り切れるかどうかを調べているからだ。もしもnの約数となるmが１つでも見つかったら、その時点でnが素数ではないことは分かってしまう。なのに、その先のmについても調べ続けるのは、明らかに無駄である。

ある条件（この場合は「割り切れた」）が満たされたことが分かったら、そのことを示す「印」を残して、反復を直ちに止めるうまい方法がある。変数（フラグ）とbreak;文を組み合わせるやり方だ。その基本的なパターンを以下に示す。

mを順に変えながら、（mに関係した）「条件」にマッチするかどうか、探索するプログラムのパターン。

	int m,flag ;
	flag=0 ; /* フラグをクリアしておく */
	for (m=から ; m<=まで ; m=m+1) {
	    if (条件) {
	        flag=1 ; /* フラグを立てて */
	        break ;  /* ループを抜ける */
	    }
	}
	
	if (flag==1) { /* フラグの値をチェック */
	   printf("条件に合致するmが見つかりました\n") ;
	} else {
	   printf("条件に合致するmは見つかりませんでした\n") ;
	}

break文

ループの中のif文の中で現れる break; は、for文の説明(無限ループ)でも登場した文で、「現在のループから脱出し、次のステップに移れ」という指示である。この例では、if文の条件が満たされれば、mが1000を超えるのを待たずに、ループの外（if (flag==1)...以降)に抜ける働きをする。

フラグの活用

一方、変数flagは、条件が満たされたかどうかを保持する役割（flagは旗を意味）。条件が満たされてループが終了したのか(flagの値は1）、あるいは、mが「まで」に達したためにループが終了したのか（flagの値は0）、を区別するためだ。最初に0にセットしておいて、「条件」が満たされた場合のみ1にセットする、という動作がミソである（条件が満たされなければ0のままである）。

「約数のカウントアップ方式」から、「約数が見つかったら打ち切る方式」にプログラムを改造するのは容易なので、ここまでを、この課題の要求水準とする。

その他の効率化のヒントを以下に挙げる：

2以上の偶数は素数ではないことは明らかなので、そもそも調べる必要がない。

nが約数mを持つ（すなわちn = k m）とすると、明らかにmはnの平方根よりも大きくなることはない。つまり、ある数mで割り切れるかどうかの判定の際、m <= (nの平方根) の範囲だけ調べれば十分。（nもmも正だから）この不等式は m*m <= n と等価。つまり、平方根を実際に計算する必要はない。

さらに効率的に素数をリスティングする方法として、エラトステネスのふるい(Sieve of Eratosthenes)と呼ばれるアルゴリズムが有名だ。また、大きな数が素数かどうか「当たりをつける」ための良く知られた方法にフェルマーテスト(Fermat primality test）がある。これらをキーワードに、ウェブ等で調べてみるとよい。大きな素数を探すこと自体が数学的な（意味のある）チャレンジであり、素数を効率的に見つける方法を巡って、奥が深い探求が続けられている。