● 先週の授業のキーポイント 【なぜ関数を利用するか？】

【なぜ関数を利用するか？】

•

プログラムを書く上では, 「同じ計算」や「同じ処理」を, 値を変えて何度も実行することが多 い. そのために「同じ計算」や「同じ処理」を何度も書くのではなく, 「関数」として実装する 方が効率的である.

•

プログラムを書く上では, プログラムを「小さなモジュール」に分割して, それらを組み合わせ るという考え方が重要となる. そのとき, 「小さなモジュール」を関数として実現しておくこと が望ましい. 一旦完成した関数は, その利用方法さえ理解しておけば, プログラム全体の構成上 は, その関数の中身の細部にわたっては忘れてしまっても構わない. このように, より効率的に, より正確にプログラムを書くためには, 適切な関数の構成と利用法が重要となる.

•

一つのプログラムを複数人で書くという場面では, 担当する部分を適切な関数として実現して, 他のプログラマに対して, 関数の意味や利用方法を伝えることが必要となる.

•

以上の理由により, 「関数の書き方や使い方がわからないから, 関数を使わずにプログラムを書 く」というのは間違った考え方である. わかりやすいプログラムを書くためには, 適切に関数を 構成・利用することが必要となる. （しかし, やり過ぎは禁物である.）

【関数】

• C

における関数の構成要素は以下のものである.

–

関数の識別子名 （関数の名前）

–

関数の引数とその型

–

関数の戻り値の型

–

関数本体

一般のプログラム言語においても, 関数（または, それに相当するもの）の構成要素は, 上のも のとほぼ同様である.

•

例えば, ２つの

int

型の値を和を取る関数は,

int sum(int a, int b) {

return a+b ; }

となり,

sum

が「関数の識別子名」であり, この関数は

a,b

の２つの

int

型の引数を取る. また, 先頭にある

“int”

が関数の戻り値の型をあらわす. 関数本体は中括弧で囲まれた部分である.

•

関数は,

sum(1,2)

または

sum(a,b)

のように, その識別子名（関数名）を（実）引数とともに 記述することで呼び出しが行われる.

•

呼び出された関数は, 関数本体の先頭から順次実行されるが,

return

文に出会うと, 関数の実行 が終了し, 制御が呼び出し側にもどされる. その際の関数の戻り値は

return

文で指定された式 の値となる.

• main

も関数の一つであり, C では, 常に

main

関数の先頭からプログラムが実行される.

•

これまでに利用してきた

printf

なども関数であり, その実体（関数本体のプログラム）は, シ

ステム内部の「ライブラリ」と呼ばれるファイルに格納されている. このような, C で標準的に

利用される関数群を「標準関数」と呼ぶ.

•

標準関数の仕様などを得るには, オンラインマニュアルを参照する. 仕様は処理系によって異な ることもあり, C の参考書等の記載と異なることもある. なお, オンラインマニュアルを参照す るには, 以下のように

man

コマンドを利用する.

Solaris (

研究科計算機室

)

の場合

% man -s 3c

関数名

Linux (

サテライトラボ

)

の場合

% man 3

関数名

ここで

3,3c

としているのは, オンラインマニュアルの「セクション番号」で, Section 3 は「ラ イブラリ関数」を示す. Solaris では

Section 3c

が「C ライブラリ関数」を示す.

【関数プロトタイプ宣言】

• C

では, 関数を記述する順序は, どのような順序でも構わない. すなわち, 変数とは異なり, 呼び 出しを行うより前に関数を定義する必要はない.

•

しかし, 呼び出しを行うより前に関数を定義していない場合, または, 「関数プロトタイプ宣言」

がない場合には, C の翻訳系は, 関数呼び出しにであうと, その関数の戻り値は

int

型であると 仮定して翻訳を実行する. その場合, その関数の戻り値が

int

型でなければ, 関数定義を読み出 した時点で「戻り値の型の不整合」が発生し, 処理系は「警告」を発する. 場合によっては, 正 しい実行結果を得られないこともある.

•

そのため, 関数を利用する場合には「関数プロトタイプ宣言」と呼ばれる, 関数の識別子名, 戻 り値の型, 引数の数と型を示した宣言文を関数の呼び出し前に記述する必要がある.

•

関数プロトタイプ宣言においては, （仮）引数の識別子名を記述する必要はない.

• “#include <stdio.h>”

という前処理命令は, 標準関数の関数プロトタイプ宣言などを含むファ

イル（ヘッダファイル）をインクルードする命令である. 標準関数を利用する際には, その関数 を宣言している適切なファイルをインクルードする必要がある. 例えば, 「数学関数」を利用す

る際には

math.h

をインクルードする必要がある. それぞれの標準関数を利用するために, どの

ヘッダファイルをインクルードする必要があるかは, K&R またはオンラインマニュアルに記述 されている.

• math.h

なしに数学関数を利用すると, 引数や戻り値が適切な型変換を受けなくなり, 正しい結

果を得られない場合が多い. また, 数学関数を使用したプログラムをコンパイルするには

% gcc -ansi -pedantic -Wall hoge.c -lm

などとして, 数学関数ライブラリ

(libm)

をリンクする必要がある.

•

関数プロトタイプ宣言は, 単に戻り値の型の整合性を取るためだけではなく, 引数の型の整合性, 引数の個数などのチェックも行うことができる.

【変数のクラス】

•

関数を記述する場合に, 関数内で利用する変数が, 他の関数からの影響を受けない, または, 他の 関数に影響を与えない必要があることが多い. 例えば, ループ制御変数は

i,j

など, 単純な識別 子名を持つ変数を利用することが多いが, それらの変数（同一の識別子名を持つ変数) が相互に 影響を与えない必要がある.

• C

における変数に付随する概念として,

–

記憶域存在期間（寿命）

と呼ばれる概念がある.

•

「スコープ」とは, 定義した変数が, プログラム内のどの部分から利用できるかという概念で ある.

•

「記憶域存在期間」とは, 定義した変数のメモリエリアが, プログラムの実行期間中のどの期間 で有効に存在しているかという概念である.

•

スコープと記憶域存在期間の別によって, C における変数は, （基本的には）次の２種類に分類 される.

–

【大域変数】

その変数が定義された後は, プログラム中のどの部分からでも可視であり, プログラムの実 行期間の全域において記憶域が存在する変数. どの関数にも属さない部分で定義された変 数は大域変数となる.

C

の仕様書においては「外部変数」と呼ばれる.

–

【局所変数】

関数本体の先頭部分（関数内）で定義された変数であり

¹,

定義されている関数内のみで可 視であり, その関数の実行期間のみで記憶域が存在する変数.

C

の仕様書においては「自動変数」または「内部変数」と呼ばれる.

•

大域変数と関数内局所変数が同一の識別子名を持つ場合には, その関数内では局所変数のみが可 視となる. すなわち, より狭いスコープを持つ変数によって, 広いスコープを持つ変数は隠蔽さ れる.

•

「記憶クラス指定子」“static” を局所変数に指定すると, スコープは変化しないが, 記憶域存 在期間が「静的」となる. なお, 外部変数に

static

宣言を行うこととは意味が全く異なるので 注意が必要である.

•

関数の仮引数も, 内部変数と同じ変数のクラスに属する.

• C

の変数は, 明示的な初期化を指定しない限り, 「静的」な変数のみが

Zero

による初期化を受 け, そうでない変数は初期化を受けない.

【関数呼び出しの実際】

•

関数が呼び出しが行われるとき, 実際には以下の手続きが行われる.

–

メモリ内の「スタック」と呼ばれる領域に, 関数呼び出しの実引数を格納するエリアとが確 保される.

–

関数呼び出しの実引数の値が上記のエリアにコピーされる.

–

関数本体の実行が行われる. この段階で, 関数内局所変数を格納するエリアが確保される.

–

関数本体の実行が終了すると, 局所変数, 実引数のエリアを破棄し, 呼び出し側に制御を戻す.

このように, 関数を呼び出す際に, 実引数の値を使って（コピーして）呼び出す関数呼び出しの 方法を「値渡し」

(call by value)

と呼ぶ.

1正しくは,「関数本体の先頭部分（関数内）など,ブロックの先頭部分で定義された変数」である.

• C

では, 関数呼び出しは

call by value

で行われるため, 関数呼び出しの実引数としては, 変数だ けでなく「式」を使うことが可能となる. 仮に実引数として変更可能なオブジェクト（変数な ど）を指定した場合に, 関数内でその値を変更しても, 呼び出し側では値が変更されるわけでは ない.

•

関数実引数や戻り値が, 関数プロトタイプと一致しない場合には, 可能であれば, 標準的な型変 換が行われる.

● 実習内容

【サンプルプログラム】

★

ex11-1.c

ここでつくっている関数は以下の仕様をみたすものである.

【形式】

double inner_product(double a[], double b[], unsigned int n)

【機能説明】

要素数

n

を持つ２つの

double

型の配列

a,b

に対して, それをベクトルと思って, その内 積の値

_n−1

i=0 a_ib_i

を返す.

この中で, 次のことに注意してもらいたい.

•

関数仮引数は

a[], b[]

という形をしていて, そこには「配列の要素数」は明示されてい ない.

•

「配列の要素数」

n

は, それを越えて配列要素へのアクセスが発生しないためだけに用い られている.

•

配列の初期化の方法で

– “a[]={1.0,2.0,3.0}”

とした場合には, 要素数は「初期化子」の個数となる.

– “b[3]={1.0,1.0}”

とした場合には, 要素数は配列宣言に規定された個数となり, 対応

する「初期化子」が無い要素に対しては

0

で初期化される. しかし, このような中途半 端な初期化はバグを作る原因となるので

,

できる限りやるべきではない.

•

このプログラム中には意図的に

inner(a,b,10),inner(a,b,10000)

という, 配列の要素 数を越えたアクセスが行われている. この時どのようなことが起るのかをためし, それはな ぜかを考えてみよう.

★

ex11-2.c

このプログラムは, 与えられた文字列の長さを出力するものである.

•

文字列は

char

型の配列であるが, 「文字列終端」を末尾に含むという構造を持っている.

したがって, 先頭から「文字列終端記号」までの要素数を数えれば, 文字列の長さを得るこ とができる.

★

ex11-3.c

ここでつくっている関数は以下の仕様をみたすものである.

【形式】

unsigned int _strlen(char s[])

【機能説明】

文字列

s

の長さを返す.

•

上記

ex11-2.c

を関数にしたものである.

size_t strlen(const char s[])

である. ここで型名

size_t

に関しては下の「注意」を参照のこと.

また

const

と宣言されたオブジェクトは「変更不可能」となる.

★

ex11-4.c

ここでつくっている関数は以下の仕様をみたすものである.

【形式】

void _strcpy(char t[], char s[])

【機能説明】

文字列

s

を文字列

t

にコピーする.

t

に

s

をコピーするだけの十分な要素数があるかどう かは配慮しない.

•

「文字列のコピー」を行う関数は標準関数の中に

strcpy,strncpy

がある.

•

これまでは, 関数に渡された実引数は, 関数内部でそれを変更しても

,

呼び出し側に戻ると 変更は反映されないと解説した. しかし, 実引数が「配列」の場合には, 関数内部でそれを 変更すると

,

呼び出し側でもその変更が反映される. この理由は次回以降に解説するので, 今のところは「そんなもの」だと思っておこう.

•

ここでは

t1

として「わざと長さの足りない領域」を用意してコピーを行っている. この時, 他のオブジェクトはどうなってしまうのだろうか？

★

ex11-5.c

このプログラムは, プログラム内で配列のサイズをどのようにして知るかを示すもので

ある.

•

配列が定義されている関数内では,

sizeof(a)/sizeof(a[0])

のようにして, 配列のサイズ を得ることができる.

•

しかしながら, 配列を関数に渡してしまうと, 関数内では配列のサイズを知ることはでき ない.

★

ex11-6.c

このプログラムは

ex07-2.c

で考えた「バブルソート」を関数の形で実現したもので

ある.

•

ソートの対象となる配列要素の型は

int

型に限っている.

•

ソート関数内では配列サイズを知ることができないため, 関数に対して「配列サイズ」を引 数として渡す必要があることに注意.

•

ソート（特に「内部ソート」と呼ばれるもの）のアルゴリズムとは, ソーティングを行うた めに利用できる「一時的な記憶領域」のサイズがソート対象のデータのサイズには依存せ ず, 元々のデータ領域上でソーティングを行うものを指す.

★

ex11-7.c

ここでつくっている関数は以下の仕様をみたすものである.

【形式】

void _strcapitalize(char s[])

【機能説明】

文字列

s

に含まれる英文字の小文字を全て大文字にする.

•

各文字が「英文字の小文字」であるかどうかは, 標準関数

islower

を用いて判定している.

islower

のような「文字種別判定関数」は引数の型として

char

ではなく

int

を取ってい

ることに注意しよう.

•

大文字小文字変換は, 各文字に

’a’ - ’A’

を引く, または

’A’ - ’a’

を加えることで行っ

ている. すなわち, 文字コードが

ASCII

であることを仮定している.

★

ex11-8.c

ここでつくっている関数は以下の仕様をみたすものである.

【形式】

void _strrev(char s[])

【機能説明】

文字列

s

を逆転させる.

★

ex11-9.c

ここでは以下のようなプログラムを書いている.

int

型の要素数

N

の配列

a

を一変数 多項式

a₀+a₁x+a₂x²+· · ·+a_N−1x^N−1

と考え, その和を求める. ただし, 「桁あふれ」が生じると「イヤ」なので,

F₂

係数であると考 えている. （ここで,

Fp

とは位数

p

の有限体をあらわす.）

•

このプログラムが「イヤ」なところは, 各多項式の次数がわからないところである. そのた め, 次数を含めたデータを用いる方が後々でうれしいことがある.

•

次数を含めたデータにするための方法は次の２つのやり方が考えられる.

1. a[0]

に「次数」を入れておき, 多項式の係数

a_i

の値を

a[i+1]

に格納する方法. 簡単 な方法だが, プログラムのループ制御が一見してわかりにくくなる欠点を持つ.

2.

多項式を単純な「配列」としてあらわすことをあきらめ, 「係数」と「次数」からなる

「構造を持つデータ」としてあらわす方法. このようなデータを（Ｃ言語では）「構造 体」と呼び, 通常これを用いる.

★

ex11-10.c

ここでは以下のようなプログラムを書いている. 利用している処理系の

unsigned

int

または

unsigned long

であらわされる数値の範囲を越えて計算を行う. とりあえずここ

では

unsigned long

を用いずに

unsigned int

の範囲を越えて計算を行うことを考えてみる.

また,

unsigned int

は

32

ビットであることを仮定しておこう. そこで, 64 ビットの整数計算 を行うために, 一つの数値を「unsigned int 型の要素数

2

の配列」に格納する.

このプログラムでは, そのように表現された

64

ビット整数の和を計算している. （ただし, 結 果が

64

ビットを越えた場合の処理は行っていない.）

•

実際の数値

N

の格納方法は以下の通り.

– N

の下位

32

ビットを

a[0], – N

の上位

32

ビットを

a[1]

•

和は

N

の各ワード（各

32

ビット）を

16

ビットごとに和と繰上がりを計算することで得 られる. また, 戻り値として最終的な繰上がりの値を返している.

•

考えている整数体系は「64 ビット符号なし整数」である.

•

入出力は

10

進ではなく, 16 進で行っている. 10 進

- 16

進変換が非常に面倒であることが 理由である.

• #define N 2

の

2

を

4

に取り替えれば, 自動的に

32N= 128

ビットの計算が可能になる.

電子メールで「今日の講義の感想や意見」を送ってください. ただし「難しい」とか「課題が多い」とい

う感想・意見はやめてください. そんなことわかっているので....

/* $Id: ex11-1.c,v 1.2 2005-06-27 13:17:05+09 naito Exp $ */

#include <stdio.h>

double inner(double [], double [], unsigned int) ; int main(int argc, char **argv)

{

double a[]={1.0,2.0,3.0}, b[3]={1.0,1.0} ; /*

ダメ！

b[3] = {1.0,1.0,0.0}

と書 くべき

*/

printf("%f\n", inner(a,b,3U)) ;

printf("%f\n", inner(a,b,10U)) ; /*

一体何がおこるのか？

*/

printf("%f\n", inner(a,b,10000U)) ; /*

一体何がおこるのか？

*/

return 0 ; }

/*

ベクトルの内積を求める.

*

要素数は

n */

double inner(double a[], double b[], unsigned int n) {

unsigned int i ; double result=0.0 ;

for(i=0;i<n;i++) result += a[i]*b[i] ; return result ;

}

★ ex11-2.c の内容

/* $Id: ex11-2.c,v 1.1 2005-06-26 13:31:15+09 naito Exp $ */

#include <stdio.h>

unsigned int _strlen(char []) ; int main(int argc, char **argv) {

int len = 0U ;

char s[]="This is a test string." ;

while(s[len++]) ;

printf("%u\n", len-1U) ; return 0 ;

}

★ ex11-3.c の内容

/* $Id: ex11-3.c,v 1.3 2005-06-27 13:17:37+09 naito Exp $ */

#include <stdio.h>

unsigned int _strlen(char []) ; int main(int argc, char **argv) {

char s[]="This is a test string." ; printf("%u\n", _strlen(s)) ;

printf("%u\n", _strlen("This is a test string.")) ; printf("%u\n", _strlen("これはテスト.")) ;

printf("%u\n", _strlen("This is a test\n

これはテスト.")) ;

return 0 ;

}

/*

文字列

s

の長さを返す

*/

unsigned int _strlen(char s[]) {

int len = 0 ; while(s[len++]) ; return len-1U ; }

/* $Id: ex11-4.c,v 1.1 2005-06-26 13:31:11+09 naito Exp $ */

#include <stdio.h>

void _strcpy(char [], char[]) ; int main(int argc, char **argv) {

char s0[]="This is a test string." ; char s1[]="これはテスト." ;

char t0[30] ; /* s0, s1

をコピーするために十分な長さの文字列領域を確保

*/

char t1[5] ; /*

ためしに短い文字列領域を取ってみる

*/

_strcpy(t0,s0) ; printf("%s\n", t0) ; _strcpy(t0,s1) ; printf("%s\n", t0) ;

_strcpy(t1,s0) ; printf("%s\n", t1) ; printf("%s\n", t0) ; return 0 ;

}

/*

文字列

s

を

t

にコピーする

*/

void _strcpy(char t[], char s[]) {

int i=0 ;

while((t[i] = s[i])) i++ ; return ;

}

★ ex11-5.c の内容

/* $Id: ex11-5.c,v 1.2 2005-06-27 13:18:44+09 naito Exp $ */ #include <stdio.h>

int foo(int []) ; int bar(int []) ;

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

int a[]={1,2,3} ;

printf("(main)\tsizeof a = %u\n", sizeof(a)/sizeof(a[0])) ; foo(a) ;

return 0 ; }

int foo(int a[]) {

int b[]={1,2,3} ;

printf("(foo)\tsizeof a = %u\n", sizeof(a)/sizeof(a[0])) ; printf("(foo)\tsizeof b = %u\n", sizeof(b)/sizeof(b[0])) ; bar(b) ;

return 0 ; }

int bar(int a[]) {

printf("(bar)\tsizeof a = %u\n", sizeof(a)/sizeof(a[0])) ; return 0 ;

}

/* $Id: ex11-6.c,v 1.1 2005-06-26 13:38:51+09 naito Exp $ */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N (10)

#define K (20)

#define M (100)

void bubble_sort(int [], int) ; int main(int argc, char **argv) {

int a[N], b[K], i ; srand(time(NULL)) ;

for(i=0;i<N;i++) a[i] = rand()%M ; bubble_sort(a, N) ;

for(i=0;i<N;i++) printf("%d\t", a[i]) ; printf("\n") ;

for(i=0;i<K;i++) b[i] = rand()%M ; bubble_sort(b, K) ;

for(i=0;i<K;i++) printf("%d\t", b[i]) ; printf("\n") ; return 0 ;

}

void bubble_sort(int a[], int width) {

int i, j, temp ;

for(i=0;i<width-1;i++) { /* a

をソート

*/

for(j=0;j<width-1-i;j++) { if (a[j+1] < a[j]) {

temp = a[j+1] ; a[j+1] = a[j] ; a[j] = temp ; }

} }

return ; }

★ ex11-7.c の内容

/* $Id: ex11-7.c,v 1.2 2005-06-27 13:19:30+09 naito Exp $ */

#include <stdio.h>

#include <ctype.h>

void _strcapitalize(char []) ; int main(int argc, char **argv) {

char s[]="This is a test string." ; _strcapitalize(s) ;

printf("%s\n", s) ; return 0 ;

}

/*

文字列

s

に含まれる英文字の小文字を全て大文字にする. */

void _strcapitalize(char s[]) {

int i=0 ; while(s[i]) {

if (islower((int)s[i])) s[i] += ’A’- ’a’ ; i++ ;

}

return ; }

/* $Id: ex11-8.c,v 1.1 2005-06-26 13:30:55+09 naito Exp $ */

#include <stdio.h>

#include <strings.h>

void _strrev(char []) ;

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

char s[]="This is a test string." ; _strrev(s) ;

printf("%s\n", s) ; return 0 ;

}

/*

文字列

s

を逆転させる

*/

void _strrev(char s[]) {

int l=0, r ; char c ;

r = strlen(s) - 1 ; while(l < r) {

c = s[r] ; s[r] = s[l] ; s[l] = c ; l++; r-- ;

}

return ; }

★ ex11-9.c の内容

/* $Id: ex11-9.c,v 1.2 2005-06-27 13:21:11+09 naito Exp $ */

#include <stdio.h>

#define N 3

void polynomial_add(int [], int [], int []) ; void polynomial_print(int []) ;

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

int a[N]={1,1,0}, b[N]={1,0,1}, c[N] ; polynomial_add(c,a,b) ;

polynomial_print(c) ; printf("\n") ; return 0 ;

}

/* F_2[x]

の和

*/

void polynomial_add(int c[], int a[], int b[]) {

int i ;

for(i=0;i<N;i++) c[i] = a[i]^b[i] ; return ;

}

/* F_2[x]

の表示

*/

void polynomial_print(int a[]) {

int i, flag = 0;

for (i=0;i<N;i++) { if (a[i]) {

if (flag) printf(" + ");

flag = 1;

switch (i) { case 0:

printf("1");

break;

case 1:

printf("x");

break;

default:

printf("x^%d", i);

break;

} } }

if (!flag) printf("0");

return ; }

/* $Id: ex11-10.c,v 1.2 2005-06-27 13:22:28+09 naito Exp $ */

#include <stdio.h>

#define N 2

#define L (0x0000FFFF)

#define H (0xFFFF0000)

#define HALFBITS (16) typedef unsigned int uint32 ; void print_uint32(uint32 []) ;

uint32 _sum(uint32 [], uint32 [], uint32[]) ; int main(int argc, char **argv)

{

uint32 a[N] = {0xFFFFFFFF, 0x00000000} ; uint32 b[N] = {0xFFFFFFFF, 0x00000001} ;

uint32 c[N] ;

_sum(c,a,b) ;

print_uint32(a) ; printf("\n") ; print_uint32(b) ; printf("\n") ; print_uint32(c) ; printf("\n") ; return 0 ;

}

uint32 _sum(uint32 c[], uint32 a[], uint32 b[]) {

uint32 al, ah, bl, bh, cl, ch, carry=0U ;

int i ;

/*

各ワードの和を計算する

*/

for(i=0;i<N;i++) {

al=a[i]&L ; ah=(a[i]&H) >> HALFBITS ; bl=b[i]&L ; bh=(b[i]&H) >> HALFBITS ; cl = al + bl + carry ;

carry = (cl&H) >> HALFBITS ; cl &= L ; ch = ah + bh + carry ;

carry = (ch&H) >> HALFBITS ; ch &= L ; c[i] = (ch << HALFBITS) + cl ;

}

return carry ; }

void print_uint32(uint32 a[]) {

int i ;

for(i=N-1;i>=0;i--) printf("%08X", a[i]) ; return ;

}

【課題】 以下の課題では, 必要に応じて関数を作ってプログラムを書くこと. また, 「標準関数」は自由に 利用してかまわないが, 当然, その問題自身の目的になっている標準関数は利用してはならない. （必 要なものは

stdio.h,ctype.h,strings.h

に含まれるものだけであると考えられる.）

★

exercise-11-1

配列に格納された

int

型の数値の中から最大の数を選びだすプログラムを書き

なさい.

☆

exercise-11-2

与えられた

unsigned int

型の数値の素因数を全て求めるプログラムを書きな さい. 例えば, 8 の素因数分解の結果は

{2,2,2}

であるとします. これは, 「全ての素因数を配 列で戻してこい」と言っているのだが,

int

の最大値が

2^N −1

であることから, あらかじめ用 意する配列の要素数が最大どれだけあるかはアプリオリに知ることができる.

☆

exercise-11-3

与えられた文字列に含まれる単語の頭文字を大文字に変換するプログラムを書

きなさい. ただし, 「単語」の区切り文字は「英数字」以外の文字とします.

☆

exercise-11-4

次の仕様をみたす関数をつくりなさい.

【形式】

int arraycmp(int a1[], int a2[], int size)

【機能説明】

同じ要素数

size

個を持つ

int

型の配列

a1,a2

に対して,

{i∈[0,size−1] :a1[i]=a2[i]}

を返す.

▽

exercise-11-5

データ列

{a_i}^k_i=1

をソートするアルゴリズムのうち, 「単純挿入法」とは, 以下 のアルゴリズムで示されるものである.

fori:= 2 to ndo begin

x:=a_i ;a₀:=x;j:=i−1 whilef(x)< f(a_j)do begin

a_j+1 :=a_j ;j:=j−1 end

a_j+1 =x end

単純挿入法を利用したソーティングのプログラムを書きなさい.

▽

exercise-11-6

データ列

{a_i}^k_i=1

をソートするアルゴリズムのうち, 「単純選択法」とは, 以下 のアルゴリズムで示されるものである.

fori:= 1 to n−1 do begin

k:=i;x:=a_i forj:=i+ 1tondo

iff(a_j)< f(x)then begin

k:=j ;x:=a_j

a_k :=a_i ; a_i:=x end

単純選択法を利用したソーティングのプログラムを書きなさい.

☆

exercise-11-7

「単純挿入法」, 「単純選択法」, 「単純交換法」 （バブルソート）に対して,

n

個のデータをソートするために必要な計算量を求めなさい.

★

exercise-11-8

与えられた文字列の中で指定の文字が最初にあらわれる場所が先頭から数えて

何文字目かを求める関数, 与えられた文字列の中で指定の文字が最後にあらわれる場所が先頭か ら数えて何文字目かを求める関数を書きなさい. ただし, 先頭に指定の文字があらわれた場合に は

0

を返すこととします. また, その文字が文字列中にあらわれない場合には

-1

を返すことと します.

★

exercise-11-9 F2

係数の２つの一変数多項式

f,g

に対して, その剰余を求めるプログラムを書 きなさい.

△

exercise-11-10 F₂

係数の２つの一変数多項式

f,g

に対して, その最大公約多項式

gcd(f, g)

を 求めるプログラムを書きなさい.

【例１】

f(x) =x⁴+x³+x²+x,g(x) =x²+x

に対しては, gcd(f, g) =

x²+x.

【例２】

f(x) =x³+x²+ 1,g(x) =x⁴+x³+x²+ 1

に対しては, gcd(f, g) =

x³+x²+ 1.

★

exercise-11-11 F₂

係数の２つの一変数多項式

f,g

に対して,

fu+gv= gcd(f, g),fw+gz= 0

をみたす多項式

u,v,w, z

を求めるプログラムを書きなさい.

★

exercise-11-12 exercise-11-9

から

exercise-11-11

の内容を

Fp

係数の一変数多項式に対 して行うプログラムを書きなさい. ただし

p

は素数としますが, 処理系から量に依存するある上 限の数

N

よりも小さいものとします. この時,

N

としてはどのような値とするとプログラムが 比較的簡単になるかを考えてプログラムしなさい.

★

exercise-11-13 ex11-10.c

で使った方法を用いて, 64 ビット整数の差を求めるプログラムを書 きなさい.

★

exercise-11-14 ex11-10.c

で使った方法を用いて, 64 ビット整数の積を求めるプログラムを書 きなさい.

★

exercise-11-15 ex11-10.c

で使った方法を用いて, 64 ビット整数の商・剰余を求めるプログラ ムを書きなさい.

△

exercise-11-16 ex11-10.c

で使った方法を用いて, 64 ビット整数に関するユークリッドの互除 法を書きなさい. すなわち, ２つの

64

ビット整数

a,b

に対して, その最大公約数

gcd(a, b)

を 求めるプログラムを書きなさい.

【例１】

a= (0F000A22 FFFF0000)₁₆

= (1080875056008986624)₁₀, b= (E00000B0 7FFF0A00)₁₆

= (16140901822557522432)₁₀, gcd(a, b) = (600)₁₆= (1536)₁₀.

【例２】

(128

ビット整数だけど... )

a= (F0000A22 10000A22 0F000A22 FFFFFFFC)₁₆

= (319014924511185179507681935478472310780)₁₀, b= (000000B0 020000B0 E00000B0 7FFFFFE0)₁₆

= (13944775575792933965396623491040)₁₀, gcd(a, b) = (14)₁₆= (20)₁₀.

★

exercise-11-17 ex11-10.c

で使った方法を用いて, 64 ビット整数の平行根の整数部分を求める プログラムを書きなさい.

★

exercise-11-18 ex11-8.c

で作った「文字列反転関数」を

EUC-JP

日本語文字コードによる日 本語文字列に対応するように拡張しなさい. なお

EUC-JP

日本語文字コードは, ２バイトで日 本語文字１文字をあらわし, その上位・下位バイトともに

MSB

（最上位ビット）は

1

となって いる. これによって文字列の要素が

ASCII

文字なのか, EUC-JP 日本語文字コードの構成要素 なのかを判定することができる.

「☆」, 「▽」, 「△」のついた問題を

7

月

11

日深夜までに提出してください. （ 「▽」及び「△」は, それ ぞれの中から１問を選択してください. もちろん両方でもかまいません.）7 月

13

日の講義の際に, 一部の 問題の解答例を配布します.

● 課題の解答例

はじめに, 全体的なコメントを....

•

プログラムが冗長で複雑だと思われます. もっと単純に書けるものばかりを課題としているはずなの で, 一度書いたプログラムを自分で見直すようにしてください. １日以上たって, 自分で書いたプロ グラムが何をやっているのかわからないようであれば, または, 他人に見せて何をやっているかわか らないようであれば, もっと改良の余地がある可能性があります.

•

プログラムの記述が「きれい」ではありません. 括弧の付け方, 空白の取り方などを, サンプルや

K&R

のサンプルプログラム等と比較してください.

実際には, それなりに動作するプログラムが提出されているのですが, 単に課題を提出すればよいという程 度のプログラムであれば, 提出したとは見なさない可能性もあります.

★

exercise-05-4

２つの

unsigned int

型のオブジェクト

a,b

に対して,

a/b

の値（この場合は「商」

となる）と剰余を, 加減算とビット演算のみで求めるプログラムを書きなさい. このプログラムでは

unsigned int

型と

int

型のオブジェクトが

32

ビットであることを仮定してよい. また, 除数

b

は

0x10000

未満（16 ビット以内）であることを仮定する.

★ 方針 通常の

10

進の割り算の筆算と同じことをすればよい. 割り算の筆算は以下のように行われ ている.

1. b

の桁が

a

と揃うように左に桁移動する.

2.

以下の手続きを, 左に桁移動した回数だけ繰り返す.

(a) a

から

b

が何回引き去ることが可能かを調べ, それを商とする. （10 進の場合, 0 回か

ら

9

回の間となる.）さらに, 引き去った結果を

a

と置きなおす.

この手続きを

2

進で行えばよい. ただし, 以下の点が異なることに注意する.

•

最初の桁移動回数は

16

回に固定する. これは,

b

と

a

の桁を数えるのが面倒なためである.

• a

から

b

が何回引き去ることが可能かを調べる際に, 2 進であることから

0

回または

1

回 しか引き去れないので,

a,b

の大小関係を調べればよい.

★ 解答例 上の方針を使えば, 解答例としては次のプログラムになる.

/* $Id: exer-05-4.c,v 1.5 2005-06-28 17:20:46+09 naito Exp $ */

#include <stdio.h>

#define BITS 32 /* int

のビット数

*/

#define H_BITS ((BITS) / 2) /* int

のビット数の半分

*/

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

unsigned int a, b, q, r;

int bits;

b = 8; a = 10124 * b + 4;

printf("%u / %u = ", a, b);

q = 0; r = a;

b <<= H_BITS;

for (bits = 0; bits <= H_BITS; bits ++) { /*

繰 り 返 し 回 数

H_BITS + 1

回

*/

q <<= 1; /*

商を左に

1bit

シフト

*/

/* r >= b

ならば商のビットを立て、余りから

b

を引く

*/

if (r >= b) { q |= 1; r -= b; } b >>= 1;

}

printf("%u ... %u\n", q, r);

return 0;

}

★ 提出されたプログラムに対するコメント

•

全体にプログラムが冗長である. 例えば, 上のプログラム例で言えば,

if (a > b) { d |= 1 ; a -= b ; b >>= 1 ; }

else { b >>= 1 ; }

のような書き方をしているものが多い. “b >>= 1” の部分は,

if

節に入る場合でも, そう でない場合でも, 同じように実行される.

•

条件判断, シフト演算等が非常に複雑な記述をしていて, 何をしているのかわからないもの が多い. 自分のプログラムを再度見直してみて, 何をしているのかわからないものはダメだ と思って欲しい.

•

上記の解答例のように, プログラム中に「何をやっているのかのコメント」を付けてほしい.

☆

exercise-06-2

２つの正の整数の最大公約数を求めるプログラムを「ユークリッドの互除法」を用い

て書きなさい.

★ 方針と解答例 次の

Section

を参照してください.

★ 提出されたプログラムに対するコメント これは比較的よくできていたとおもいます.

☆

exercise-06-4

２つの正の整数

a,b

に対して, 拡張されたユークリッドの互除法を用いて

ax+by= gcd(a, b)

をみたす

(x, y)

を一組求めるプログラムを書きなさい. ただし,

xy= 0

をみたすこと.

★ 方針 単にユークリッドの互除法を改良するだけです.

★ 解答例

/* $Id: exercise-06-4.c,v 1.6 2005-06-25 15:33:17+09 naito Exp $ */

#include <stdio.h>

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

int a, a1, a2, b, b1, b2, k, k1, k2 ; int r, q ;

a = 40920 ; b = 24140 ; /********************/

k = k1 = k2 = 0 ; a1 = 1 ; a2 = 0 ; b1 = 0 ; b2 = 1 ; while(b) {

k = a%b ; q = a/b ; k1 = a1 - q*b1 ; k2 = a2 - q*b2 ;

a = b ; a1 = b1 ; a2 = b2 ; b = k ; b1 = k1 ; b2 = k2 ; }

while((a1 == 0)||(a2 == 0)) { a1 += b1 ; a2 += b2 ; }

printf("%d, %d\n", a1,a2) ; printf("%d, %d\n", b1,b2) ; printf("gcd=%d\n", a) ;

return 0 ; }

もし, 配列を使えるのであれば, 以下のような記述も可能です.

#include <stdio.h>

#define M (3)

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

int a, b ;

int a0[M]={0,1,0}, b0[M]={0,0,1}, k[M]={0,0,0} ; int r, q, i ;

a = 40920 ; b = 24140 ; /********************/

a0[0] = a ; b0[0] = b ; while(b0[0]) {

k[0] = a0[0]%b0[0] ; q = a0[0]/b0[0] ; for(i=1;i<M;i++) k[i] = a0[i] - q*b0[i] ;

for(i=0;i<M;i++) { a0[i] = b0[i] ; b0[i] = k[i] ; } }

while((a0[1] == 0)||(a0[2] == 0)) { a0[1] += b0[1] ; a0[2] += b0[2] ; }

printf("%d, %d\n", a0[1],a0[2]) ; printf("%d, %d\n", b0[1],b0[2]) ; printf("gcd=%d\n", a0[0]) ;

return 0 ; }

★ 提出されたプログラムに対するコメント 本質的にユークリッドの互除法そのものなので, 比較的 マトモだったと思いますが....

•

変数名の付け方が悪い人が多い. “i,j,k,l,m,n,...” などと安易な変数名の付け方はダメ です. このプログラムでは, 変数に「意味」があるので, それがわかるような変数名にすべ きです.

•

最後の条件「ただし,

xy= 0

をみたすこと」をみたしていないプログラムが少なからずあ りました. まあ, 見落としだとは思いますが....

☆

exercise-06-6

２つの正の整数の最大公約数を求めるプログラムを「２進互除法」を用いて書きなさい.

★ 方針 アルゴリズムそのものをきちんと記述するだけです.

★ 提出されたプログラムに対するコメント 私が予想したよりはマトモなプログラムが提出されてい ました. しかし, 一部には「２進互除法の意味」を理解していないと思われるものも少なからず ありました. その意味は以下のようなことです.

•

「２進互除法」の本質は「除算を使わないこと」です. gcc では, “a/2” と書いても, 実際 には

a

を左にシフトする命令に置き換えられる可能性があります. このことは

gcc

の「最 適化処理」に依存している内容なので, 「２進互除法」でこのような記述をすることは望ま しくありません.

というよりも, レポートとして提出した場合には, 「２進互除法の意味がわかっていない」と判

断されても文句は言えないと思います.

☆

exercise-07-1

標準入力から入力されたテキストデータに含まれる「アルファベットの各文字」の頻 度を, 大文字と小文字を区別せずに求めるプログラムを書きなさい.

★ 方針

ex07-3.c

をちょっと変更するだけです.

★ 解答例 上の方針を使えば, 解答例としては次のプログラムになる.

/* $Id: exercise-07-1.c,v 1.4 2005-06-28 16:51:38+09 naito Exp $ */

#include <stdio.h>

#define NUM_OF_ALPHABETS (26) int main(int argc, char **argv) {

int a[NUM_OF_ALPHABETS], i, c ;

for(i=0;i<NUM_OF_ALPHABETS;i++) a[i] = 0 ; while((c = getchar()) != EOF) {

if ((c >= ’A’)||(c <= ’Z’)) a[c - ’A’] += 1 ; else if ((c >= ’a’)||(c <= ’z’)) a[c - ’a’] += 1 ; }

for(i=0;i<NUM_OF_ALPHABETS;i++) printf("%c\t%5d\n", ’A’+i, a[i]) ; return 0 ;

}

★ 提出されたプログラムに対するコメント 入力されたデータの取り扱いが理解できれば易しいプロ グラムですので, 提出されたものについては, 比較的マトモであったと思われます. ただし, 一部 のプログラムで,

DIGIT

というマクロ定義を

ex07-3.c

からそのまま利用しているものがあり ました. “DIGIT” とは「数字」という意味の単語ですから, アルファベットの個数を表すため には不適切な単語です.

実習などで「英語はわからない」と言っている学生諸君を多々見かけますが, 「わからないから 間違った用語を使ってもよい」わけではありません. 英語がわからないのであれば, わかるよう に努力してください. これもプログラミングの内容の一部です！

☆

exercise-07-2

エラトステネスのふるいを用いて, 100000 以下の全ての素数を求めるプログラムを書

きなさい.

★ 方針 この問題は解答例を掲載しません. 以下の方針にしたがって, 各自で再度自分の書いたプロ グラムを見直してください. （これは, 最も安易な方法で, 改良点が大量にあります.）以下では,

M = 100000

とします.

•

基本的な方針は,

int

型の

M+ 1

個の要素を持つ配列

prime

を用意し,

prime[i]

が

1

で あることが,

i

が素数であることを表すこととします.

•

最初に,

prime[i]

を

1

で初期化し,

prime[0],prime[1]

に

0

をセットします. また,

index

(変数名は何でもよい)

を

2

にセットし, これをふるいの先頭の

index

とします.

•

あとは,

index

の２乗が

M

以下である間, ふるいを実行します.

ふるいを実行する際には, 「倍数を除く際には, 乗算は必要ない」ことに注意が必要です.

★ 提出されたプログラムに対するコメント

★ 改良の方針 上の方法では, いくつかのムダが生じる可能性があります.

ることが可能.

•

「倍数を除く」際には, 既に除かれている可能性のある部分を省くことによって, その操作 を半分程度にすることが可能.

•

「index の２乗が

M

以下」の判定を行う際に乗算なしで判定可能. これは,

√

M

を計算す

るのではなく,

(n+ 1)²=n²+ 2n+ 1

を使って, 「index の２乗」を順次計算することで解決可能.

と言うわけで....

exercies-06-6,exercise-07-2

については, 各自で自分のプログラムを見直して, 必要

であれば再度提出してください.

● プログラムの書き方（互除法における例）

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

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

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

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

アルゴリズム

1 (Euclid

の互除法) ２つの正の整数

a₁,a₂

が与えられた時に, それら の最大公約数を見つける.

1. i= 1

とする

.

2. a_i=q_ia_i+1+a_i+2

となる商

q_i

と剰余

a_i+2

を求める.

3. a_i+2 = 0

ならば,

gcd(a₁, a₂) =a_i+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

であることがわかります. （まず, これを確認しておくこ とは重要.）

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

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

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

プログラムを書く際には, 「同じ計算をしている部分を繰り返しで表現する」のが原則なので, まず, 繰り 返し部分を探します.

ユークリッドの互除法では「ステップ２」で同じ計算をしていることがわかるので, 「ステップ２の部分

をループにすればよい」ことがわかります. また, 「ループ終了条件」として「余りが０になったら終了す

る」ということも見て取れます.

ここまで来たら, とりあえずプログラムを書いてみましょう.

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

•

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

•

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

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

ユークリッドの互除法の「ステップ２」では, 入力データ

a₁, a₂

に続いて,

a₃, . . .

を求めていますが,

(a₁, a₂)

から

a₃

を求めた後には

a₁

は不要になることがわかります. したがって,

(a₁, a₂)→(a₂, a₃)→ · · ·

というように, 「ステップ２」の除算は常に

a=qb+r

という形で求めればよいことがわかります.

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

•

互除法の「ステップ２」で利用する

a,b.

（この２つの変数は互除法の入力データと共用できること がわかります.）

•

「ステップ２」で求める商

q

と余り

r.

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

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

int

を使うことにしましょう.

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

/* Euclidean Algorithm */

/* Version 0.1 */

#include <stdio.h>

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

int a,b,q,r ; 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 main(int argc, char **argv) {

int a,b,q,r ; 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.

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

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

...」

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

というわけで, 除算を始める前に大小関係を比較して, 値の入れ替えをする必要があることに気が付きま

す. そこで, その部分をプログラムに追加すると,

#include <stdio.h>

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

int a,b,q,r ; a = 125 ; b = 315 ;

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 main(int argc, char **argv) {

int a,b,q,r ; 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

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

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

#include <stdio.h>

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

int a,b,q,r,t ; a = 125 ;

b = 315 ;

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 main(int argc, char **argv) {

int a,b,q,r,t ; 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

を計算しておけばいいのね」

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

#include <stdio.h>

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

int a,b,q,r,t ; 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 ; }

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 main(int argc, char **argv) {

int a,b,q,r,t ; 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

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

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

#include <stdio.h>

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

int a,b,q,r,t ; a = 125 ;

b = 315 ;

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 main(int argc, char **argv) {

int a,b,q,r,t ; 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)

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

するのですか？

•

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

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

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

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

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

プログラムにムダがあると, 「後からみたときに何をやっているかわからない」プログラムになったり,

その部分にバグが潜んだりする可能性があります. もちろん, 余りにムダを省きすぎると, 何をやっている

かひと目ではわからないプログラムになるので, その辺りは程度問題ですが...