● 実習内容 今回は実習はありません

● 実習内容

今回は実習はありません.

● 前回の課題の解説

実習をやらないかわりに,

ユークリッドの互除法のプログラムを書きなさい.

のプログラムを書いていく手順の一例を紹介します. あくまで一例であって,他にも手順が何種類もありま す. また,最終的にできあがったプログラムも「一例」に過ぎません.

★ アルゴリズムを用いて実際に手で計算する

講義では「ユークリッドの互除法」のアルゴリズムは以下のように書いたはずです. （細部は多少違って いるかもしれない.）

アルゴリズム 1 (Euclidの互除法) ２つの正の整数a1,a2が与えられた時に,それらの最大公約数 を見つける.

1. i= 1とする.

2. a_i=q_ia_i+1+a_i+2 となる商q_i と剰余 a_i+2 を求める.

3. ai+2 = 0ならば,gcd(a1, a2) =ai+1 である. そうでなければ,i←i+ 1 として,上に戻る.

また,「雛形のプログラム」では, gcd(125,315)を求めると書いてあります. そこで,アルゴリズムにした

がってgcd(125,315)を計算すると以下のようになります.

315 = 125∗2 + 65 125 = 65∗1 + 60

65 = 60∗1 + 5 60 = 12∗5 + 0

ということは,求める答えはgcd(125,315) = 5であることがわかります. （まず,これを確認しておくこ とは重要.）

★ アルゴリズムを分析する

ここでいきなりプログラムを書きはじめても成功しません. 重要なことは,

手で計算した過程や結果とアルゴリズムを見比べて,必要な初期化,条件判断,繰り返しを見つけます.

といっても,いきなりプログラムを書き始めるのではなく,

• 「どのような変数が必要なのか？」

• 「ループの中でどの変数を入れかえていくのか？」

などを考える必要があります.

ユークリッドの互除法の「ステップ２」では, 入力データ a1, a2 に続いて, a3, . . . を求めていますが, (a₁, a₂)からa₃ を求めた後にはa₁ は不要になることがわかります. したがって,

(a1, a2)→(a2, a3)→ · · · というように,「ステップ２」の除算は常に

a=qb+r という形で求めればよいことがわかります.

したがって,最低限必要な変数としては

• 互除法の「ステップ２」で利用する a,b. （この２つの変数は互除法の入力データと共用できること がわかります.）

• 「ステップ２」で求める商 qと余りr.

であることがわかります.

また, これらの変数の型を考える必要があります. ここでは,「整数」に関する議論なので, とりあえず intを使うことにしましょう.

というわけで,プログラムの最初のバージョンを作成します. このバージョンでは,いきなりループをつ くるのではなく,「１段だけ互除法をやってみる」ということを行います.

/* Euclidean Algorithm */

/* Version 0.1 */

#include <stdio.h>

int a,b,q,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a, b) ; q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; return 0 ;

}

そこで,このプログラムを実行してみましょう. すると,

gcd(125,315) = q = 0, r = 125

という結果が得られます. この段階で,次の除算の準備を行いましょう.

ループの中では,「常にaをbで割る」という操作を行っています. 次の除算では,そこまでに得られた bをrで割るので,

• aにbを代入する.

• bにrを代入する.

という代入演算を行わない限り, 「ステップ２」を繰り返すことができません. これをプログラムすると, 次のバージョンができあがります.

/* Euclidean Algorithm */

/* Version 0.2 */

#include <stdio.h>

int a,b,q,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a, b) ; q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; a = b ;

b = r ;

printf("a = %d, b = %d\n", a,b) ; return 0 ;

}

このプログラムの実行結果は,

gcd(125,315) = q = 0, r = 125 a = 315, b = 125

となります.

「あれぇ？ 315と 125のままじゃん！なんで？」

よくプログラムをみてみましょう.

• 除算を行う前にはaの値は125,bの値は315.

• 除算を行った後には aの値は315,bの値は125.

となっていて,値が入れ替わっています.

「そんなぁ！入れ替えた記憶はないのにぃ...」

除算の部分をよくよくみてみると,「大きいものを小さいもので割らなければいけないのに, その逆をやっ

printf("gcd(%d,%d) = ", a, b) ;

if (a < b) { a = b ; b = a ; }

q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; a = b ;

b = r ;

printf("a = %d, b = %d\n", a,b) ; return 0 ;

}

このプログラムの実行結果は,

gcd(125,315) = q = 1, r = 0 a = 315, b = 0

となります.

「もっとダメダメじゃん！何で？」

この段階で「わかりません！」と聞いてはいけません！少しは自分のアタマを使ってください. Version 0.2

からVersion 0.3 への書き換えを行った部分に間違いがあるのは当然ですから,その辺りを狙って「デバッ

グ」を行います.

「値を入れ替えたところにバグがあるんだよな...」

それが正解なので,その前後で「きちんと入れ替わっているかどうか」を確かめてみます. というわけで,

Version 0.3を変更して実行すると,

/* Euclidean Algorithm */

/* Version 0.4 */

#include <stdio.h>

int a,b,q,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("a = %d b = %d\n", a,b) ; if (a < b) {

a = b ; b = a ; }

printf("a = %d b = %d\n", a,b) ; q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; a = b ;

b = r ;

printf("a = %d, b = %d\n", a,b) ; return 0 ;

}

a = 125 b = 315 a = 315 b = 315 q = 1, r = 0 a = 315, b = 0

となり,値が入れ替わっていないことがわかります.

よく考えてみると,値の入れ替えの部分で,a = bを行うとa,b ともに125となり,そのあとで b = a としているので,値の入れ替えに成功していないことがわかります. もう一度アタマを使うと,「値を入れ 替えるには, 入れ替える値の一方をどこかに保存しておかなければいけない」ということに気が付くはず です.

というわけで,この「一時的な値の保存をする変数」を追加して,値の入れ替えを行うと,

printf("a = %d b = %d\n", a,b) ;

if (a < b) {

/* t は一時的な保存の場所 */

t = a ; a = b ; b = t ; }

printf("a = %d b = %d\n", a,b) ; q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; a = b ;

b = r ;

printf("a = %d, b = %d\n", a,b) ; return 0 ;

}

a = 125 b = 315 a = 315 b = 125 q = 2, r = 65 a = 125, b = 65

となり,めでたく値の入れ替えに成功しました. （ここで,変数名tは temporaryの略です.）

この時,同時に商の値が2,剰余の値が65となり,次のステップに進むときのaの値が125,bの値が65 となっていることがわかります.

「ＯＫ！第一段は成功！」

と喜んでかまいません. そこで,めでたくループをつくる作業に入ることができます.

★ ループをつくる

ループをつくる際には,

• どこからどこまでをループにするか？

• どのループ制御を使うか？

• ループの終了条件は何か？

を考える必要があります.

Version 0.5をもとにすると, ifの前からreturnの直前までが,繰り返しの対象となっているので, そ

こがループの中身であることがわかります. もっとよくみてみると, Version 0.5では,

• 「ループに入る前段階」の作業は,a,bの大小関係について, 必要ならば入れ替えを行う.

• 「ループの次の段階に進む」作業は,a = b,b = rを行う.

• 「ループの中身」の作業は,q,rを求める.

と分類できるのですが,「前段階」と「後処理」の作業量が多いので,for文で書くのではなく,while文 で書くことが適当と思われます. （for文で書くと「式１」と「式３」が長くなり,きれいではなくなる.）

明らかに「ループ終了条件」は 「rが 0かどうか？」ですから,次のようなプログラムを書くことがで きます.

/* Euclidean Algorithm */

/* Version 0.6 */

#include <stdio.h>

int a,b,q,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("a = %d b = %d\n", a,b) ; while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

printf("a = %d b = %d\n", a,b) ; q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; a = b ; b = r ;

printf("a = %d, b = %d\n", a,b) ; }

return 0 ; }

a = 125 b = 315

「何かおかしい... 」

ループ内部にあるprintf関数からの出力が得られていないので,明らかにwhileループの中に一度も入っ ていないことがわかります. ここで,「一度はループに入るんだから,do文を使えばよい」という結論を勝 手に出してはいけません. 我慢してwhileループをよく見てみましょう.

「１回目のr の値が 0 になってるんじゃないの？」

という結論がわかればよいのです. （「すべての変数は使う（評価する）前に値を明示的に代入する」とい うことが原則です.）

「だったら,r を計算しておけばいいのね」

と思って,次のように書き直します.

printf("a = %d b = %d\n", a,b) ;

r = a%b ; while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

printf("a = %d b = %d\n", a,b) ; q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

printf("q = %d, r = %d\n", q,r) ; a = b ; b = r ;

printf("a = %d, b = %d\n", a,b) ; }

return 0 ; }

a = 125 b = 315 a = 315 b = 125 q = 2, r = 65 a = 125, b = 65 a = 125 b = 65 q = 1, r = 60 a = 65, b = 60 a = 65 b = 60 q = 1, r = 5 a = 60, b = 5 a = 60 b = 5 q = 12, r = 0 a = 5, b = 0

「あっ！できた！」

何となくできているような気がしますね. そこで,「じゃまな出力」を削ってしまいましょう.

/* Euclidean Algorithm */

/* Version 0.8 */

#include <stdio.h>

int a,b,q,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("a = %d b = %d\n", a,b) ; r = a%b ;

while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ;

printf("a = %d, b = %d\n", a,b) ; }

return 0 ; }

a = 125 b = 315 a = 125, b = 65 a = 65, b = 60 a = 60, b = 5 a = 5, b = 0

「きちんとできてるじゃん！答えを出力しておしまい！」

というわけで,次のように書き直します.

printf("gcd(%d,%d) = ", a,b) ;

printf("a = %d b = %d\n", a,b) ; r = a%b ;

while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ;

printf("a = %d, b = %d\n", a,b) ; }

printf("%d\n", a) ; return 0 ;

}

gcd(125,315) = a = 125 b = 315 a = 125, b = 65

a = 65, b = 60 a = 60, b = 5 a = 5, b = 0 5

「これで完成！」

なんて思っている人はダメダメです！

プログラムとは一種の「ブラックボックス」ですから,「入力」を与えたとき,「答えだけを出力す る」ことが重要な意味を持ちます.

このプログラムでは,デバッグのための出力がいっぱい残っているので,それを削ることが必要になります.

というわけで,「完成品」は以下の通り. （「完成品」なので, Version番号を1.0にしちゃいましょう.）

/* Euclidean Algorithm */

/* Version 1.0 */

#include <stdio.h>

int a,b,q,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; r = a%b ;

while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

q = a/b ; /* 商を求める */

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ; }

printf("%d\n", a) ; return 0 ;

}

gcd(125,315) = 5

「よぉし！完成！簡単じゃん！」

ところが,このプログラムを送ると（または,このプログラム作成の過程をみていると）,担当教官（内藤）

から,

「ダメ！お話にならない！」

という冷酷なコメントが返ってきます. その理由は次の通りです.

• gcd(125,315)の答えを正しく出力することしか確認していませんよね？他の値の時にも正しく動作

するのですか？

• プログラムに「ムダ」はありませんか？

プログラムを書く時に以下のことを注意する必要があります.

示された仕様の入力に対して,必ず正しい結果を出力することを保証しなければいけない.

プログラムにはムダな部分があってはいけない.

前者は余りにも明らかなことです. これをサボると某Ｍ社のように,「バグがあっても『仕様です』と言い 逃れする」悪辣なソフトウェアを書くはめになります. もちろん, アルゴリズムを正しく実装していると 思っていても,それを保証することは非常に困難です.

ということを行います.

Version 1.0 では, この２つのムダがともに存在しています.

【使っていない変数を削る】 「使っていない変数」には次の２種類が存在します.

1. 一度も代入もされていない変数.

つまり「変数定義にだけ登場して,実行文中では登場しない変数」.

2. 一度も評価を受けていない変数.

「変数を使う」とは,その「変数の値を評価する」ことです. 「変数の値を評価する」とは,「変数の 値を取り出す」ことに他なりません. そのような場面は以下のものに分類されます.

• 代入式の「右辺」にあらわれるとき.

• 代入式以外の式にあらわれるとき.

• 関数（例えばprintfなど）で使うとき.

この基準で変数をみていくと, Version 1.0ではqは「代入式の左辺」に一度登場するだけです. したがっ て, qは「使っていない変数」に該当します.

そこでqを削ると,

/* Euclidean Algorithm */

/* Version 1.1 */

#include <stdio.h>

int a,b,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; r = a%b ;

while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ; }

printf("%d\n", a) ; return 0 ;

}

となります. 結局「ユークリッドの互除法」では,本質的には「商は使わない」ことがわかります.

次に「同じことを２度やっていないか」を確かめることにしましょう.

Version 1.1 で「同じことを２度やっている」部分があります. それは, “r = a%b”で剰余を求める部分

です. これを「ループに入る直前」と「ループ内部」で行っているので, このムダを何とかして省くこと が必要です. ところが,「ループに入る直前」にこの計算を行う必要性があったはずです. もしこの計算を やっておかない場合には,「ループの中に入ってくれない」ことが理由でした.

「そんなぁ,これを省けってのはムリだよ！」

確かにそう思えます. そこで,while文をdo文に書き換えることを思いつきます. ところが,「待った！」

と声がかかるはずです. 「Ｃではdo文は使わない方が望ましい」と書いてある文献がありますから,何と かしてwhile文のままでのりきれるはずです.

もう一度「なぜrを先に計算しなければいけないのか？」を考えてみましょう. それは,rを計算しない と, whileループの１回目の評価でrが0 になってしまい,whileループに入らないことが原因でした.

それなら,

「ループに入る前に rを 0 以外の値で初期化しておけばいいじゃん！」

という結論に到達します. そのようにして書き換えると,

/* Euclidean Algorithm */

/* Version 1.2 */

#include <stdio.h>

int a,b,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; r = 1 ;

while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

t = a ; a = b ; b = t ; }

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ; }

printf("%d\n", a) ; return 0 ;

}

となり,その出力は

gcd(125,315) = 5

として正しい結果が得られたままです.

「これで文句ないだろう！」

えている部分が本当に利用されているかどうかを確かめます. そのためには,「その部分を通過するたびに 何かを出力する」ようにしてテストすればＯＫです.

/* Euclidean Algorithm */

/* Version 1.3 */

#include <stdio.h>

int a,b,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; r = 1 ;

while(r != 0) {

/* a < b ならば入れ替えを行う */

if (a < b) {

printf("IF を通過\n") ; t = a ; a = b ; b = t ; }

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ; }

printf("%d\n", a) ; return 0 ;

}

と書き換えて,出力をみると,

gcd(125,315) = IF を通過 5

となり, 最初の１回以外はif文の中を利用していないことがわかります. これは, 互除法の仕組みを考え れば当たり前のことです.

というわけで,aとbを入れ替えるif文はループの外に追い出すことができます. そのようにして書き 換えたものが

/* Euclidean Algorithm */

/* Version 1.4 */

#include <stdio.h>

int a,b,r,t ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; /* ここから互除法 */

if (a < b) {

/* a < b ならば入れ替えを行う */

t = a ; a = b ; b = t ; }

r = 1 ;

while(r != 0) {

r = a%b ; /* 剰余を求める */

/* 次の除算のために, a, b を入れ替える */

a = b ; b = r ; }

/* ここまで互除法. 答えは a */

printf("%d\n", a) ; return 0 ;

}

となります.

ところが, Version 0.2の出力を思い出してみましょう.

aが125,bが315の時（これはa < bになっている）に,除算を１回やるとaが 315,bが 125になり, 値が入れ替わっていました. ちょっと考えてみれば...

a < b が成り立つとき,その商 a/bは 0になり,剰余はaに等しい.

ということがわかります. （簡単な算数です.）互除法では商の値は本質的ではないので,a < bの時には 除算を１回余分にやれば,a > bかどうかを判定する必要がないことがわかります.

ここで, 次のような問題に直面します. 「除算１回を余分にやるか,条件分岐を１回判定するか？」この 答えは難しいものがありますが,所詮１回のことだけですから,「プログラムの単純さ」をとることが必要 です.

というわけで,aとbの値の入れ替えは必要がなくなります. 結局,以下のようなプログラムとなり,

printf("gcd(%d,%d) = ", a,b) ;

/* ここから互除法 */

r = 1 ;

/* a < b の時には１回除算をすれば値が入れ替わる */

while(r != 0) {

r = a%b ; /* 剰余を求めて a, b, r を入れ替える */

a = b ; b = r ; }

/* ここまで互除法. 答えは a */

printf("%d\n", a) ; return 0 ;

}

その結果も

gcd(125,315) = 5

というように正しい結果を出力します.

「よぉしっ！完成！」

と思って,次にプログラムのテストに入ります.

★ プログラムのテスト

プログラムはアルゴリズムを正しく実装したものであることはわかっています. その理由は, whileループの入り口では,毎回gcd(125,315) = gcd(a, b)が成り立っています. さらに,whileルー プの終了直前の除算では,

a=qb+ 0

が成り立っているので, a,bへの代入を行う直前には, gcd(125,315) =b であるはずです. したがっ て, 代入a = b を行った後にはgcd(125,315) =aとなります.

したがって,プログラムは正しく動作するはずですが,いくつかの例に関してそれをテストすることが必 要です.

問題は,「どのような値を入れてテストするか」ですが,「適当に値を入れればよい」というのは間違い です. プログラムのテストを行う場合には,次のような入力を与えることが必要です.

1. 標準的だと考えられる入力データ.

今回の場合には,

(a) 互いに素ではなく,その値自身が最大公約数とはならないデータ. 特に最大公約数が素数ではな い場合.

(b) 互いに素ではなく,その値自身が最大公約数とはならないデータ. 特に最大公約数が素数となる 場合.

(c) 互いに素であるデータ.

2. ちょっと特別なデータ.

今回の場合には,

• 互いに素ではなく,その値自身が最大公約数となってしまうデータ.

3. おもいっきり特別なデータ.

今回の場合には,

(a) ２つの入力が等しい場合.

(b) 片方が1 の場合.

(c) 両方が1 の場合.

と言うデータすべてに対してテストを行います.

そこで,データを以下のように作成して, gcd(a, b), gcd(b, a)の結果が正しいことを確認します.

1. (a) a= 2∗3∗5∗7,b= 2∗5∗11.

(b) a= 2∗3∗5∗7,b= 3∗11.

(c) a= 2∗3∗5∗7,b= 11∗13.

2. a= 2∗3∗5,b= 2∗5.

3. (a) a= 11∗17,b= 11∗17.

(b) a= 11∗17,b= 1.

(c) a= 1,b= 1.

これらのデータすべてに対してテストをしましょう. 最も簡単な方法は,「互除法の部分を何度もコピーし て一度にテストしてしまう」方法です. （このソースコードはのせません. 長くなってしまうから.）その 結果は,

gcd(210,110) = 10 gcd(110,210) = 10 gcd(210,33) = 3 gcd(33,210) = 3 gcd(210,143) = 1 gcd(143,210) = 1 gcd(30,10) = 10 gcd(10,30) = 10 gcd(187,187) = 187 gcd(187,187) = 187 gcd(187,1) = 1 gcd(1,187) = 1

gcd(1,1) = 1 gcd(1,1) = 1

となり,すべて正しく動作しました.

「今度こそ完成！ これで文句ないだろう！」

すると,

「ようやくここまで来ましたね. まあこの程度ならＯＫとしましょう」

なんてコメントしか返ってきません. 私の本音は

rを計算してしまえばよい」ことがわかります.

このアイデアを使って書き直すと,

/* Euclidean Algorithm */

/* Version 1.7 */

#include <stdio.h>

int a,b,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; /* ここから互除法 */

while((r = a%b)) { /* 剰余が 0 でないかぎりループを実行 */

a = b ; b = r ; }

/* ここまで互除法. 答えは a */

printf("%d\n", a) ; return 0 ;

}

となります. その結果は....

gcd(125,315) = 60

「あれぇ... おかしくなった... さっきまで動いていたのにぃ....」

「よくあることです. メゲずにデバッグしましょう.」

プログラムはきれいになったのですが,結果が異なってしまいました. こうなると,正しく動作していたと ころまで戻って,どこが違っているのかを調べる必要があります.

正しく動いていたものは Version 1.5です. Version 1.5とVersion 1.7 の両方にデバッグのための出力 を付け加えましょう. （それぞれ, Version 1.5.1 と Version 1.7.1とします. printf 関数を付け加えた場 所に注意してください.）

/* Euclidean Algorithm */

/* Version 1.5.1 */

#include <stdio.h>

int a,b,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

/* ここから互除法 */

r = 1 ;

/* a < b の時には１回除算をすれば値が入れ替わる */

while(r != 0) {

printf("a = %d, b = %d\n", a, b) ;

r = a%b ; /* 剰余を求めて a, b, r を入れ替える */

a = b ; b = r ; }

/* ここまで互除法. 答えは a */

printf("a = %d, b = %d\n", a, b) ; printf("%d\n", a) ;

return 0 ; }

a = 125, b = 315 a = 315, b = 125 a = 125, b = 65 a = 65, b = 60 a = 60, b = 5 a = 5, b = 0 5

/* Euclidean Algorithm */

/* Version 1.7.1 */

#include <stdio.h>

int a,b,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

/* ここから互除法 */

while((r = a%b)) { /* 剰余が 0 でないかぎりループを実行 */

printf("a = %d, b = %d\n", a, b) ; a = b ; b = r ;

}

/* ここまで互除法. 答えは a */

printf("a = %d, b = %d\n", a, b) ; printf("%d\n", a) ;

return 0 ; }

a = 125, b = 315 a = 315, b = 125

は whileループには入りません.

したがって,whileループから脱出したときのa,bの値が１回分異なっています.

ここで,「教訓」として,「ループのところでバグがでている場合には,まず最初に,ループの『最後 の１回』の処理を疑う.」ということを覚えておきましょう.

これでバグの元がわかったので,正しいプログラムに直すと以下のようになります.

/* Euclidean Algorithm */

/* Version 2.0.a */

/* Final Version */

#include <stdio.h>

int a,b,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; /* ここから互除法 */

while((r = a%b)) { /* 剰余が 0 でないかぎりループを実行 */

a = b ; b = r ; }

/* ここまで互除法. 答えは b */

printf("%d\n", b) ; return 0 ;

}

gcd(125,315) = 5

もちろん,このFinal Versionに対しても十分なテストを行うことが必要です.

「今度こそ完成！」

「よくできました. これなら文句は（この段階であれば）ありません.」

★ もっとマトモなプログラムにする（方法Ｂ）

実は,「方法Ａ」以外にも改良の方法があります. やはり,問題は「ループの判定条件」のところにあり ます.

プログラムが「きれいではなくなっている」原因は,ループ判定条件にrを用いていることが原因です.

一方, whileループの終了時には, それまでのr の値はbに代入されています. したがって, ループ判定 条件に b を使うことができることに気が付きます. これに気が付くと,以下のように書き直すことができ ます.

/* Euclidean Algorithm */

/* Version 2.0.b */

/* Final Version */

#include <stdio.h>

int a,b,r ;

int main(int argc, char **argv) {

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; /* ここから互除法 */

while(b != 0) { /* 判定条件を b に変えた */

r = a%b ; a = b ; b = r ; }

/* ここまで互除法. 答えは a */

printf("%d\n", a) ; return 0 ;

} 結果は

gcd(125,315) = 5

となり,正しい結果を出力していることがわかります. もちろん,「方法Ａ」と同様に十分なテストを行う ことが必要です.

「今度こそ完成！」

「よくできました. これでも当然文句は（この段階であれば）ありません.」

【注意】 ここで,判定条件としてa != 0と慌てて書いてしまうと,

Floating exception

という「実行時エラー」が発生します. これは,最後の１回で「0で割る」という操作が発生していること が原因です.

★ まとめ

このように「正しくてわかりやすいプログラムを書く」ことは容易なことではありません.

アルゴリズムを正しく理解して,アルゴリズムの全体の流れ,細部の条件判定などを精密に調べるこ とが必要です.

この作業の中で重要な手順は,

• アルゴリズムを一度は紙の上や頭のなかで動かしてみる.

つながります.

ここに書いた「考え方」は,単にプログラムを書くためのテクニックではなく,数学の研究や勉強を する場合にも適用できますし,仕事の上で「システムを構築」する場合にも全く同じ手順を行ってい きます.

【補足】 Final Versionをこれ以上改良しようとすれば,次のような改良が考えられます.

• 入力データは「正の整数」と仮定されているので,利用する変数の型をintではなくunsigned int にする. これによって, 計算できる値の範囲が広くなります.

または, 「負の整数」でも対応するという方向に改良することも考えられます.

• Final Versionのいずれであっても,入力データの少なくとも一方が0の場合の「エラー処理」を行っ

ていません. 互除法に入る前に,入力データが0 かどうかを判定して,片方でも0 の場合には何らか の「エラーメッセージ」を出力することが必要な場合も考えられます.

いずれも意味がある改良です.

• プログラムがより一般の入力データに対して機能するような改良は,大きな意味を持ちます.

• 「マトモなアプリケーション」を作成する場合,プログラムの大半は,「予期しない入力データに対 するエラー処理」で費やされることがあります. 逆に,「予期しない入力データに対するエラー処理」

が完全でないアプリケーションは「バグだらけじゃん！」という評価を受けてしまいます.

なお,今後「関数」を勉強した後には,このFinal versionをさらに改良することを考えます.

【おまけ】 ちなみに, Final versionに至るまでの所要時間は,最初は「９０分」といったところでしょう.

なれてくると,アルゴリズムの理解とプログラムの書き方がわかってくるので,かなり速くプログラムを書 くことができるようになります. 最終的には,このくらいのプログラムが「１５分」程度で書けるようにな れば,

「まあ,『Ｃのプログラムが書けます』と言ってもウソじゃないよね.」

と思います. 最後に独り言を...

「互除法なんて,まともなプログラマなら５分だぜ！」