情報基礎A 「Cプログラミング」（ステップ４・反復処理）

このステップの目標

• 反復処理の流れと、変数の初期値、反復中の変化、終了の判定方法を的確に把握できる。
• for文を使って、ループを含む基本的な処理を記述できる。 特に、「総和」、および「条件が満たされるまで繰り返す」パターンを応用できる。

０．準備

反復処理のプログラムに間違いがあると、期待に反して「いつまで経ってもプログラムが終了しない」ことがある。アプリが「固まった」状態だ。そんな状態から脱し、処理を強制的に中断するには、TurtleEditの 中断 ボタンを押すこと。

TurtleEditを使わず、Linuxのターミナル（端末エミュレーター）で作業している場合は、プログラム実行中にキーボードの下段にあるコントロール（Ctrl）キーを押したまま、アルファベットのｃ（コントロールC, CTRL-C）を押せば、プログラムは強制終了になる。

1. 反復処理

コンピュータは、長大で人間には面倒な処理でもあっと言う間にこなすことができるから役に立つわけだが、その全てのステップを人間が書き下さなければならないとしたら、プログラムを記述する手間や時間が膨大となりすぎ、本末転倒だ。 コンピュータが役に立つには、少ないプログラムの記述量で、膨大な処理ステップをこなすことができる、そんな仕掛けが不可欠なのだ。

そのために必要となるのが、繰り返し処理、あるいは反復処理だ。その意味で、反復は自動化の要と言える。 反復をマスターしなければ、プログラミングを学ぶ意味が無い。

同じ内容を決まった回数だけ繰り返す

反復の中で最も単純なのは、全く同じ動作の繰り返しであろう。 ただし、繰り返しはどこかで止めないといけない（でないと、永遠に終わらない）ので、繰り返しの回数は決めておく必要がある。 例えば、画面に "Hello!" と10回表示するためのアルゴリズムは以下のように表現できる：

画面に"Hello!"と10回プリントするアルゴリズム

1: 繰り返しの回数をカウントする変数 n を用意する
2: n ← 1
3: もしも n ≤ 10 なら引き続き以下を行い、そうでなければ 7: に移る
4: "Hello!"とプリントする
5: n ← n + 1　（nの値を1つ増やす)
6: 3:に戻って繰り返す
7: 終了する

このアルゴリズムでは、0回目、1回目、2回目、とカウントするための変数 n を用意して、繰り返しの回数をコントロールしている。 一番最初に n を0にしておいてから、 "Hello!"をプリントする都度、n の値を1ずつ増やし、10以上になったら繰り返しを止める。 そうすれば、"Hello!"は全部で10回プリントされることになる。

このアルゴリズムは以下のように言い換えても、その「意味」は全く同じである：

1: 繰り返しの回数をカウントする変数 n を用意する
2: n を 1 から始めて、10 になるまで（つまり10以下のあいだ）間、nを1ずつ増やしながら 4: までを行う：
3:   "Hello!"とプリントする
4: 繰り返しここまで
5: 終了する

これをCのコードに翻訳すると、以下のようになる：

#include <stdio.h>
main()
{
	int n ;
	for (n=1 ; n<=10 ; n=n+1) {
		printf("Hello!\n") ;
	}
}

ここで for (n=1;n<=10;n=n+1){何々;} は繰り返しを表現するための文で、 アルゴリズムの『n を 1 から始めて、10になるまで（つまり10以下のあいだ）間、nを1ずつ増やしながら・・・を行う』に対応している。 このfor文の中の10という数を100に変えれば, "Hello!" が100回プリントされるし、1000にすれば1000回出力される。

　練習：繰り返し回数を変えてみる

上記のプログラムを修正して、画面に "Temptation" と 108回プリントしてみなさい。

内容を変えながら繰り返す

次に、全く同じことの繰り返しではなくて、「何かを変えながら繰り返す」処理を考えてみよう。

その例として、ここでは 1から10まで足し算をここでは取り上げる。 1+2+3+4+5+6+7+8+9+10 を、電卓のメモリー加算(M+)キーを使って計算する様子と対比させながら、それと同等な計算をCプログラムで書いてみたのが以下である。

#include <stdio.h>
main( )
{
    int sum ;                                  電卓で計算すると・・・
    sum = 0 ;                                    MC
    sum = sum + 1 ;                              1 M+
    sum = sum + 2 ;                              2 M+
    sum = sum + 3 ;                              3 M+
    sum = sum + 4 ;                              4 M+
    sum = sum + 5 ;                              5 M+
    sum = sum + 6 ;                              6 M+
    sum = sum + 7 ;                              7 M+
    sum = sum + 8 ;                              8 M+
    sum = sum + 9 ;                              9 M+
    sum = sum + 10 ;                             10 M+
    printf("１から１０までの合計： %d\n",sum) ;     MR 
}

変数 sum が電卓の「メモリー」に対応することは一目瞭然である。 そして、ここで繰り返されているのは 『sum = sum + 加える数』 のパターンであるが、加える数 そのものは 1, 2, 3,... と1ずつ規則的に変化していることに気づくだろう。 つまり、パターンは反復されているものの、その内容は、毎回少しずつ（ただし規則性をもって）変わっている。

　練習：電卓で地道に計算

スマートフォン等にインストールされている電卓アプリを開き、上の手順に従いメモリーキーを使って、1から10までの足し算を試してみなさい。

数の足し上げのアルゴリズム

１から１０までの総和の計算を、上記の電卓の操作を振り返りながら、繰り返しの記法を使ってまとめると

1: メモリーを0にする (MC)
2: 加える数(nとする）を 1 から 10 まで 1ずつ増やしながら、以下を繰り返す:
3: 　　メモリーにnを加えた数を、新しくメモリーにセットし直す (n M+)
4: 繰り返しここまで
5: メモリーの値を表示する (MR)

となる。 そして、これをCに翻訳したのが，次の例題4aである：

#include <stdio.h>
main( )
{
     int n, sum ;
     sum=0 ;
     for (n=1 ; n<=10 ; n=n+1) {
        sum = sum + n ;
     }
     printf("１から１０までの合計： %d\n",sum) ;
}

例題4aで 変数 n は、繰り返しの「カウンター」の役割に加え、反復の都度変化する部分、すなわち「加える数」を表すことにも使われている。

ここで、プログラム中の n=n+1 という書き方を今一度確認しておこう。n=n+1は、『現在のnの値に1を加えた値をnに代入する』操作を表すので、すなわち『nを1増やす』操作になる。このパターンはCプログラムでは頻出するので、n+=1 あるいは n++ という「短縮形」を使うこともできる。 同様に『nを1減らす』は n=n-1 となり、それを n-=1 や n-- と記述してもよい。

まずは動作を確認するため、このプログラム(ex4a.c）をコンパイルして、実行してみよう。

　for文による反復処理の記述

色々な問題に関係したアルゴリズムで、繰り返しのパターン：

がしばしば登場する。これをC言語に「翻訳」するやり方はいくつかあるが、 中でも for文はこのパターンの記述に好適である。 このパターンをfor文を使って表現すると、

for ( Xという状況から始めて ; Yという条件が成り立つあいだ ; 毎回Zにより更新しながら) {
    繰り返しの内容
}

となる。例題4aで、これに対応する箇所は

for (n=1 ; n<= 10 ; n=n+1 ) {
	sum = sum + n ;
}

である。

for文の丸括弧の中の２箇所のセミコロンは各パーツの区切りを示すために必ず必要である。 また、「繰り返しの内容」の箇所には 文１;文２;文３;・・・;　のように、繰り返したい内容を複数列挙しても構わない。

例題4aのfor文の箇所を、さらに細かな手順にまで分解し、流れ図で示したのが左図である。for文の基本形との対応関係は：

• Xという状況から始めて（反復の前に一度だけ実行される文）：n=1 ;
• Yという条件が成り立つあいだ（繰り返しの継続条件：if文の条件式の書き方と同様）： n<=10
• 毎回Zにより更新しながら（各回の反復の都度行う処理）： n=n+1 ;
• 繰り返しの内容： { sum=sum+n ; }

となる。図から、プログラムの流れがループ構成しており、その流れは変数nによってコントロールされているのわかるはずだ。 そのため、このnはループ変数と呼ばれる。

ここで大切なのは、for文のパターンに従って、文法的に正しく記述できるだけでなく、 処理の各ステップで、変数（特にループ変数に影響される変数）の値がどのように変化してゆくのかをきちんと頭の中でシミュレーションができるようになることだ。 その様子を別ページに示したので確認しておくこと。

　練習：奇数の和と階乗の計算

例題4aをひな形にして、

1. 1から100までの奇数のみの合計($1+3+5+\cdots+99$)を計算するプログラムを作成せよ。
2. 1から10をかけ合わせた結果（10の階乗:$10!=1 \times 2 \times \cdots 10$）計算するプログラムを作成せよ。

　ヒント

$10!$ が計算できたら、もっと大きな数の階乗も計算させてみよう。
検算用の値: $10!=3628800, \ \ 20!=2432902008176640000, \ \ 30!=265252859812191058636308480000000$.

2. for文を使いこなす

　forを使った「定型文」

Cの構文の中ではおそらくfor文がいちばん複雑ではないかと思う。 けれども、いくつかの典型的なパターンに当てはめながら使う場合がほとんどなので、 それらをしっかりと押さえておけば、大抵の問題に対処できるだろう。

for (i= から ; i <= まで ; i=i + ずつ) {
   反復内容
} 

for (i= から ; i >= まで ; i=i - ずつ) {
   反復内容
} 

float x ;
for (x= から ; x < を超えないで ; x=x + ずつ) {
   反復内容
} 

s=0 ;
for (n= から ; n <= まで ; n=n+1) {
  n番目の値の計算・・・;
  s = s + n番目の値 ;
} 

for (;;) {
  ・・・ ; 
  if (条件) break ; 
  ・・・ ;
}

同じ結果を得るためのプログラムの書き方は何通りもある。 例題4aのプログラムを上記の「無限ループ」の定型を使って書き直すと、以下のようになる。 for文のパーツを ( ; ; ) の中から取り出したような格好だ。

#include <stdio.h>
main( )
{
     int n, sum ;
     sum = 0 ;
     n = 1 ;
     for (;;) {
        if (n>10) break ;
        sum = sum + n ;
        n = n + 1 ;
     }
     printf("１から１０までの合計： %d\n",sum) ;
}

　練習：ゼータ関数の値の評価

リーマンのゼータ関数(Riemann zeta function) $$ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} $$ は、数学の問題の各所に関係した大変に興味深い対象である。例えば、$\zeta(2)$の値は、以下のように、円周率と関係の あることがわかっている： $$ \zeta(2) = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \cdots = \frac{\pi^2}{6} $$

C言語の「総和の計算」のパターンに、ゼータ関数を当てはめることで、ζ(2)の値を数値的に評価してみなさい。

　ヒント

#include <stdio.h>
#include <math.h>
main( )
{
  int n ;
  float s,zeta2 ;
  s=???
  for (n=?? ; ?? ; ??) {
     ?????? ;
  }
  
  zeta2 = M_PI * M_PI / 6.0 ;
  
  printf("総和によって求めた zeta(2)= %f\n",s) ;
  printf("数学的な結果 =%f\n",zeta2) ;  
}

　練習：べき乗の計算

キーボードから実数($x$とする)と整数($n$とする)を入力すると、forループを使って$x^n$を計算し、出力するプログラムを作成しなさい。

まずは、$n\gt0$に対応できれば十分であるが、技量に応じて、$n=0$、$n\lt0$の場合にも対応できるように工夫してみなさい。

　ヒント

総和のパターンを応用して、$x$に$x$を$n-1$回掛ければよい（$n \gt 0$の場合）。以下にひな形を示す：

#include <stdio.h>
main( )
{
  int n,i ;
  float x,p ;
  printf("x=") ;
  scanf("%f",&x) ;
  printf("n=") ;
  scanf("%d",&n) ;
  p=??? ;
  for (i=?? ; ?? ; ??) {
     ?????? ;
  }
  
  printf("%f^%d = %f\n",x,n,p) ;  
}

3. 条件が満たされるまで反復する計算

ここでは「人類最大の発明」と言われる複利(compound interest)について考えてみよう

複利で運用される積立があったとしよう。 $x$ 円の元本があったとすると、年利率が$r$ %であったすると、1年目後の積立額は $x \times (1 + r/100)$、 2年目は $x \times (1 + r/100)^2$, そして $n$年目には $x \times (1 + r/100)^n$ となる。

簡単のため、税金や利息端数の切り捨てなどは考えないことにすると、 『年利率(%)を入力して元本が2倍を越えるまでに要する年数を計算するプログラム』は以下のように書ける：

#include <stdio.h>
main()
{
	int n ;
	float r,p ;
	printf("年利(%%):") ;
	scanf("%f",&r) ;
	n=1 ;
	p=1 ;
	for (;;) {
		p = p * (1.0+r/100.0) ;
		if (p>2.0) break ;
		n=n+1 ;
	}
	printf("%d年目に元本は2倍を超えます\n",n) ;
}

例題4bの見どころ

利率計算のアルゴリズムについては、特に説明の必要は無いだろう。 for文の無限ループのパターンfor(;;) {何々;}を使って、元本が何倍になっているのかを表す変数 $p$ が2を越えた時点でループを抜け、繰り返しの回数 $n$ を出力して終了する。

printf("年利(%%):");の%%の箇所に注意。%は書式(%dや%f)の設定に用いる特別な文字なので、それ自体はプリントされない。ところが%%と書けば % が1文字出力される、というルールになっている。

　練習：ローンの計算

元利均等返済の月利1.5%のローンを組んで100万円を借り入れ、利子も含め毎月2万円ずつ返済したい。各月毎の借入残高をプリントし、借入残高が0になったら停止するプログラムを作成しなさい。

　ヒント

#include <stdio.h>
main()
{
   int n ;
   float d = 100 ;
   for (;;) {
      ???
      ???
      ???
      printf("%d 月後の借入残高 %f 万円\n",n,d) ;
    }
}

　反復を応用した連分数の計算

以下は、黄金比(golden ratio)と呼ばれる「有理数から最も遠い無理数」( $\phi = (1+\sqrt{5})/2 = 1.618033988\cdots$)を連分数表示したものである。

この連分数を、定義に従って「そのまま」数値計算してみよう。 計算にあたっては、「下」から攻めてみるのが良さそうだ。$k$ステップ目の計算値を$\phi_k$とすると、次のステップの値は $$ \phi_{k+1} \leftarrow 1 + \frac{1}{\phi_k} $$ となるはず（下図参照）。

そうすると、この計算を繰り返すことで値が評価できそうだ。 このように、「現在の値」を使って「次の値」を計算する、という手順の繰り返しは、反復処理の典型的なパターンだ。

ここで、$\phi_k$を変数 a、$\phi_{k+1}$を変数 b に対応づけて、もう少し具体的にアルゴリズムをまとめたのが以下である：

Input: 計算の打ち切り精度 eps
Output: 連分数の近似値
1: aに初期値を設定する
2: 以下を反復
3:   b←1+1/a
4:   もし |a-b|<eps ならばループを抜けて7:へ
5:   a←b
6: 反復ここまで
7: aの値をプリントして停止

さらにこれを「無限ループ」の定型に当てはめて、Cのプログラムに翻訳すると以下のように書ける。 プログラム中で、ループを何回繰り返すかは陽には指定されておらず、「前」の値と「後」の値の差が十分小さく なったところで繰り返しを抜けるように書かれている。

#include <stdio.h>
#include <math.h>
main()
{
    float a,b ;
    a=1.0 ;
    for (;;) {
        b = 1+1/a ;
        if (fabs(a-b)<0.0001) break ;
        a = b ;
    }
    printf("計算結果= %f\n",a) ;
    printf("数学的な結果= %f\n",(1.0+sqrt(5.0))/2.0) ;
}

　練習：連分数の計算

黄金比のプログラム例を参考に、$\sqrt{2}$または$\sqrt{3}$の値を以下の連分数を使って評価するプログラムを作成しなさい。

　ヒント

繰り返しの「単位」を上手に見極めること。いずれも「最後の１回分」だけ、式のパターンが異なる点に注意。

　練習：最大公約数

教科書 例題2.12の最大公約数を求めるプログラムをC言語で記述しなさい。 アルゴリズムとして、教科書で説明されているユークリッドの互除法（Algorithm 2）を用いること。

Input: 整数 a,b
Output: a,bの最大公約数 gcd(a,b)
1: b≠0の間は2:-4:を繰り返す
2:   aをbで割った余りをrとする
3:   aに現在のbの値を代入する
4:   bに現在のrの値を代入する
5: 反復ここまで
6: b=0になったら、この時点でのaの値を出力して停止する

　練習：自然数の「ひっくり返し」

教科書　例題2.11のプログラム(Algorithm 1)をC言語によって記述し、動作を確認しなさい。

• 自然数$n$をひとつ入力する。
• $n$を10進で逆から読んだ自然数を出力する。例えば$n=7463$なら、出力は$3647$になる。

Input: 自然数 n
Output: nを逆から読んだ自然数
1: 変数 ans を用意し、0にセットしておく
2: 以下を反復する:
3:   nの１の位の数字を求めて、それを変数oneにセットする
4:   ansの末尾に 3:で求めたoneを追記する
5:   nの１の位を削除する
6: この時点でnが0でなければ2:に戻る。そうでなければ反復を終了する。
7: この時点でのansの値を出力して停止する

　ヒント

10進で表されている自然数 $n$ の1の位は、剰余演算を使って、n%10 で得られる。$n$の桁を1つ右にシフトする（ずらす）には n = n/10 ;、左にシフトするには n = n * 10 ;すればよい。 例えば、n=1234;とすると、n/10は123なので、 nの桁をひとつ右にずらし、1桁目を削除したことになる。 また、n*10は12340なので、桁をひとつ左にずらし、1桁目に0を追記したことに相当する。

（殆どの処理系で）int型で表現できる数の範囲は -2147483648〜2147483647 なので、計算結果がその範囲を越える場合は注意が必要である。

ついでながら、2進数での桁のシフト操作はしばしば必要になるので、C言語には専用の演算子が用意されている。$n$を$k$ビット右シフトした値はn>>k、$k$ビット分左シフトはn<<k と記述できる。nが正の整数ならば、n << 1は、n*2と同じ結果を与える。

亀場で練習：正多角形の描画

タートルグラフィックスのページの前半部分をよく読み、反復処理を用いて、半径100の円に内接する大きさの正7角形を描画するプログラムを作成しなさい（ただし、円は描かなくてよい）。