3 k = 2対してk2, k3, k4 の値を計算し、順に k, k2, k3, k4 の値を出力する。
4 k = 3対してk2, k3, k4 の値を計算し、順に k, k2, k3, k4 の値を出力する。
. . . .
11 k = 10対して k2, k3, k4 の値を計算し、順に k, k2, k3, k4 の値を出力する。
(プログラミング) 上記の手順〜2 は、11
k2, k3, k4 の値を計算し
順にk, k2, k3, k4 の値を出力する、
という処理をk = 1,2,3, ...,10に対して順に行ってい るだけである。それゆえ、流れ図においてはこの〜2
の部分を繰り返しの箱11 を用いて表すことが
できる。実際、k = 1〜10 の値を記憶するために k という名前の変数領域を用意することにすれば、行う べき処理は右図の様に書き表すことができる。
開始 出力 見出し
終了
出力
k , k , k , k True
False
k 1
k k+1 k ≦ 10
2 3 4
この処理を行うCプログラムと、これをコンパイル/実行している様子を次に示す。 (下 線部はキーボードからの入力を表す。)
[motoki@x205a]$ nl table-of-k-k2-k3-k4.c Enter
1 /* 整数 k=1〜10 について k^2,k^3,k^4 の値を計算し、*/
2 /* それらの結果を表の形に見易く出力するCプログラム */
3 #include <stdio.h>
4 int main(void) 5 {
6 int k;
7 printf(" k k^2 k^3 k^4\n"
8 "-- --- ---- ---\n");
9 for (k=1; k<=10; ++k)
10 printf("%2d %3d %4d %5d\n", k, k*k, k*k*k, k*k*k*k);
11 return 0;
12 }
[motoki@x205a]$ gcc table-of-k-k2-k3-k4.c Enter [motoki@x205a]$ ./a.out Enter
k k^2 k^3 k^4 -- --- ----
---1 1 1 1
2 4 8 16
3 9 27 81
4 16 64 256
5 25 125 625
6.2. 処理の規則的な繰り返し 65
6 36 216 1296 7 49 343 2401 8 64 512 4096 9 81 729 6561 10 100 1000 10000 [motoki@x205a]$
ここで、
• プログラム9行目 に現れる ++k は k=k+1 と同等の式である。 これと類似の k++,
--k, k-- という表現もC言語ではよく使われる。 これらの表現の中の ++ と -- を
それぞれ増分演算子,減分演算子 と言う。 (=⇒p.45を参照)
• プログラム9〜10行目 は for文と呼ばれる、繰り返しのための構文である。9行目は 流れ図における繰り返しの箱 に相当するもので、for に続く括弧の中には、
変数k の最初の値をどう設定するか
繰り返しを続けるための条件(i.e. どんなk の値まで繰り返すか) 1回の繰り返し処理が終った後に変数 k をどう更新するか
ということが書かれている。これらの記述によって、
k=1 という設定を行った後で 次の文(10行目)を k<=10 である間 繰り返す、
但し、次の文(10行目)の実行が終るたびに、
++k を実行 して変数k の保持する値を1だけ大きくする、
ということを表す。この場合、変数 k は処理の繰り返しを制御する働きをするので、
繰り返し制御の変数、ループ制御の変数、あるいは単に制御変数と言う。
• プログラムの10行目 の出力書式中の %2d, %3d, %4d, %5dは、それぞれ(半角) 2文字 分, 3文字分, 4文字分, 5文字分 の出力場所を確保し、そこに右詰めで出力すること
を表す。 '
&
$
% 繰り返しの見通し(e.g.回数)がはっきりしている場合は、
上の例題6.4のプログラムで例示した様に、
• 繰り返しを制御する変数を用意し
• その制御変数に関する操作を forに続く括弧の中に集めて for文を構成するのが良い。
なぜなら、そういったfor文だとforに続く括弧の中だけを見て、逆にそ こでどういう繰り返しが行われるかを容易に見通せるからです。
□演習 6.5 (k2, k3, k4, k5の表) 整数k = 0,5,10,15,20,25, ...,50についてk2, k3, k4, k5 の 値を計算し、それらの結果を表の形に見易く出力するCプログラムを作成せよ。
例題 6.6 (階乗;for文) 正整数データkを読み込み、その階乗値k! = 1×2×3×· · ·×k を整数として求めて出力するCプログラムを作成せよ。
(考え方) 我々が手で計算するとしたら、正整数 k が与えられたとき、次の様に計算を
進める。
(step 1) 1! = 1
(step 2) 2! = 1!×2 = 1×2 = 2 (step 3) 3! = 2!×3 = 2×3 = 6 (step 4) 4! = 3!×4 = 6×4 = 24 (step 5) 5! = 4!×5 = 24×5 = 120
...
(step k) k! = (k−1)!×k = ...
この計算をコンピュータに行わせれば良いわけであるが、この場合、どんな変数を用意す れば良いのだろうか? この計算の途中で出て来る 1!,2!,3!, ...,(k −1)!, k! の値は、計算 のいずれかの時点でどこかの変数に記憶しておく必要がある。しかし、だからと言って、
1!,2!,3!, ... 各々毎に別の変数を用意して
(step 1) 1! の値を保持する変数 ←− 1
(step 2) 2! の値を保持する変数 ←− 1! の値を保持する変数×2 (step 3) 3! の値を保持する変数 ←− 2! の値を保持する変数×3 (step 4) 4! の値を保持する変数 ←− 3! の値を保持する変数×4 (step 5) 5! の値を保持する変数 ←− 4! の値を保持する変数×5
...
(step k) k! の値を保持する変数 ←− (k−1)! の値を保持する変数×k
とするのでは、色々な k の値に対処するために際限のない個数の変数が必要になってし まう。
そこで、
次にi! の値を計算する時点では、
計算に必要な値は (i−1)! の値と iの値だけであり、
1!,2!, ...,(i−2)!の値はそれ以降も必要ない
ことに注目する。 i!の値が計算できてしまえばそれ以前に計算した1!,2!,3!,...,(i−1)!は 保持しておく必要はないので、1!,2!,3!,...を保持するために1つだけ共通のデータ格納領 域を用意し、
1 最初はそこに1!の値を保持する,
2 2!が計算できれば保持されていた1!の値は捨て代わりに 2!の値を保持する, 3 3!が計算できれば保持されていた2!の値は捨て代わりに 3!の値を保持する,
. . . .
ということにすれば良い。従って、1!,2!,3!,...の値を保持する変数 を用意して、次のアルゴリ ズムでコンピュータに計算させれば良い。
(step 0) 正整数 k を読み込む。
(step 1) 1!,2!,3!,...の値を保持する変数 ←− 1
(この時点で 1!,2!,3!,...の値を保持する変数 は1! の値を保持しているはず)
(step 2) 1!,2!,3!,...の値を保持する変数 ←− 1!,2!,3!,...の値を保持する変数 ×2
(この時点で 1!,2!,3!,...の値を保持する変数 は2! の値を保持しているはず)
(step 3) 1!,2!,3!,...の値を保持する変数 ←− 1!,2!,3!,...の値を保持する変数 ×3
(この時点で 1!,2!,3!,...の値を保持する変数 は3! の値を保持しているはず)
(step 4) 1!,2!,3!,...の値を保持する変数 ←− 1!,2!,3!,...の値を保持する変数 ×4
(この時点で 1!,2!,3!,...の値を保持する変数 は4! の値を保持しているはず)
6.2. 処理の規則的な繰り返し 67
(step 5) 1!,2!,3!,...の値を保持する変数 ←− 1!,2!,3!,...の値を保持する変数 ×5
(この時点で 1!,2!,3!,...の値を保持する変数 は5! の値を保持しているはず)
...
(この時点で 1!,2!,3!,...の値を保持する変数 は(k−1)! の値を保持しているはず)
(stepk) 1!,2!,3!,...の値を保持する変数 ←− 1!,2!,3!,...の値を保持する変数 ×k
(この時点で 1!,2!,3!,...の値を保持する変数 はk!の値を保持しているはず)
(step k+ 1) 1!,2!,3!,...の値を保持する変数の値を出力 (プログラミング) 上記の手順(step 2)〜(step k)は、
1!,2!,3!,...の値を保持する変数 ←− 1!,2!,3!,...の値を保持する変数 ×i
という処理を i = 2,3,4, ..., k に対して順に行っているだけである。それゆえ、流れ図に おいてはこの(step 2)〜(stepk)の部分を繰り返しの箱 を用いて表すことができる。
読み込んだ正整数を格納するために k という名前の変数を、1!,2!,3!,...の値を保持するた
めに factorial という名前の変数を、そしてi = 2〜k の値を記憶するためにi という
名前の変数を用意することにすれば、行うべき処理は次の流れ図の様に書き表すことがで きる。
開始 入力 k
終了 True
False
i 2
i i+1 i ≦ k
k は正整数と仮定
出力
k , "! = ", factorial factorial 1
factorial factorial × i この時点で factorial = i !
'
&
$
% 補足:
“factorial”は階乗という意味の英単語である。
=⇒階乗と何の関係のない計算に“factorial” という名前 の変数を用いてはならない。
実際には、整数型32ビットでは 13! は記憶できないので、
上記プログラムのようにint型で階乗値を正確に求めたい場 合は、入力変数kは12以下でなければならない。
この処理を行うCプログラムと、これをコンパイル/実行している様子を次に示す。 (下 線部はキーボードからの入力を表す。)
[motoki@x205a]$ nl factorial.c Enter
1 /* 正整数データ(12以下と仮定)を読み込み、 */
2 /* その階乗値を整数として求めて出力するCプログラム */
3 #include <stdio.h>
4 int main(void) 5 {
6 int k, i, factorial;
7 printf("何の階乗を求めますか?: ");
8 scanf("%d", &k);
9 factorial = 1;
10 for (i=2; i<=k; ++i){
11 factorial *= i; /* この時点で factorial = i! */
12 }
13 printf("%d! = %d\n", k, factorial);
14 return 0;
15 }
[motoki@x205a]$ gcc factorial.c Enter [motoki@x205a]$ ./a.out Enter
何の階乗を求めますか?: 10 Enter 10! = 3628800
[motoki@x205a]$
□演習 6.7 (総和Pk
i=1i) 正整数データ k を読み込み、1 から k までの総和 Pk i=1i = 1 + 2 + 3 +· · ·+k を整数として求めて出力するCプログラムを作成せよ。
□演習 6.8 (総和Pk
i=1i3) 正整数データ k を読み込み、総和 Pk
i=1i3 = 13 + 23 + 33 +
· · ·+k3 を整数として求めて出力するCプログラムを作成せよ。
□演習 6.9 (冪乗) 整数 a と 非負整数 k を入力し、これらを基に ak を計算して出力す るCプログラムを作成せよ。但し、ここでは簡単のため 00 = 1 と考えよ。
□演習 6.10 (階乗の表) 整数 k = 1〜12 について k! の値を計算し、それらを表の形に 見易く出力するCプログラムを作成せよ。
□演習 6.11 (Fibonacci数列) 一般に、初期値a0, a1 と漸化式 an=an−1+an−2 for each n ≥2
によって決まる数列 {an} をFibonacci数列という。45以下の非負整数 k を読み込んで 初期値が a0 =a1 = 1 のFibonacci数列の第(k+ 1)項 ak
を計算して出力するCプログラムを作成せよ。