● 実習内容【課題】

(1)

● 実習内容

【課題】

1.

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

2.

拡張されたユークリッドの互除法のプログラムを書きなさい. すなわち,正の整数a, b を与えたときに,

ax+by= gcd(a, b), aw+bz= 0

を満たす整数の組(x, y), (w, z)をそれぞれ一組求めるプログラムを書きなさい.

3.

２進互除法のアルゴリズムをプログラムしなさい.

電子メールで「今日の講義の感想や意見」を送ってください.

★

prog07.c

の内容

/* prog07.c */

/* ユークリッドの互除法 */

#include <stdio.h>

int a, b ;

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

a = 125 ; b = 315 ;

printf("gcd(%d,%d) = ", a,b) ; /* この部分で互除法の計算を行う */

return 0 ; }

(2)

● 前回の課題の解説

西暦１９００年から西暦２００３年までの閏年をすべて出力するプログラムを書きなさい.

/* prog06-1.c */

/* 西暦１９００年から西暦２００３年までの

* 閏年をすべて出力するプログラム

*/

#include <stdio.h>

int year ;

for(year=1900;year<=2003;year++) {

if ((year%4 == 0)&&((year%100 != 0)||(year%400 == 0))) { printf("%d\n", year) ;

} }

return 0 ; }

注意１：このようなプログラムでは,「１９００」と「２００３」という, 対象となる「定数」がプログラム内に明示的に書き込んであると,プログラムの意図が明確になる.

Ｃ言語の場合には,

for(year=1900;year<2004;year++)

でもある程度意図は伝わるだろう.

注意２：このプログラムでは,変数は「西暦の年数」という明確な意味を持った数値が代入されるので,単に変数名をiなどとするのではなく,yearという変数名にして,変数の値の意味がわかりやすくすることが望ましい.

注意３：このプログラムで,

(year % 4 == 0)&&((year % 100 != 0)||(year % 400 == 0)) を

(year % 4 == 0)&&(year % 100 != 0)||(year % 400 == 0) と書くと,

prog06-1.c:13: warning: suggest parentheses around && within ||

という「警告」がでる.

(3)

for文,while文,do文,それぞれを用いて, 1から10までの和を計算するプログラムを書きなさい.

/* prog06-2-1.c */

/* for 文で 1 から 10 までの和を計算するプログラム */

#include <stdio.h>

int i, j ;

j = 0 ;

for(i=0;i<10;i++) { j += i+1 ; }

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

}

/* prog06-2-2.c */

/* while 文で 1 から 10 までの和を計算するプログラム */

#include <stdio.h>

int i, j ;

i = 0 ; j = 0 ; while(i<10) {

j += i+1 ; i += 1 ; }

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

}

/* prog06-2-3.c */

/* do 文で 1 から 10 までの和を計算するプログラム */

#include <stdio.h>

int i, j ;

i = 0 ; j = 0 ; do {

j += i+1 ; i += 1 ; } while(i<10) ; printf("%d\n", j) ; return 0 ;

}

(4)

注意１：これらすべてのプログラムにおいて,「ループの制御変数」i と,「値を格納する変数」 jの２つの変数が必要になっていることに注意しよう.

「繰り返し文」を使う場合に,必ずしも「ループ制御変数」が明示的に必要になるわけではないが,この場合には「制御変数」と「値」を別の変数にする必要がある.

注意２：これらのいずれの場合にでも,「１から１０までの和をとる」という意図を明確にするには,「１０回の繰り返し」という意味または,「１０まで」という意味で10が明示的にプログラム中に書き込んであることが重要である.

注意３：Ｃでのfor文の使い方として,制御変数の値が0から始まるときには,

for(i=0;i<10;i++)

のように,ループ終了条件を<で書くことが多い. （「for文を使って「配列要素への値の代入」を行う場合に,このような書き方になるのが自然である」という理由に起因する.）

もし,問題が「１１から２０までの和」であれば,

for(i=11;i<=20;i++)

という書き方もあり得るだろう.

このような違いは,「どれが正しくて,どれが間違っている」という問題ではなく,「Ｃのプログラマにとってわかりやすいのは何か」という問題であるので,矛盾する内容も含むが,このような「わかりやすいプログラム」の書き方に習熟する必要がある.

注意４：while文（do文も同様）であれば,以下のようなものも考えられる.

i = 1 ;

while(i<=10) { j += i ; i += 1 ; }

i = 0 ; while(i<10) {

i += 1 ; j += i ; }

注意５：while文,do文はfor文とは異なり,ループ終了後に評価する式が存在しない. したがって,i+=1 などという,ループ制御変数の値を置き換える文を, 明示的にループの内部に書く必要がある.

i = 0 ; while(i<10) {

j += i ; }

のままであると「無限ループ」にはまってしまう.

(5)

摂氏の温度を−20^◦C から40^◦Cまでを10^◦C 刻みで,と華氏の温度に変換して表示するプログラムを書きなさい. ただし,表示は小数点以下２桁目を四捨五入しなさい.

はっきり言って,「出題ミス」である.

華氏の温度を−20^◦F から40^◦F までを10^◦F 刻みで,と摂氏の温度に変換して表示するプログラムを書きなさい.

と出すべきであった.

/* prog06-3-1.c */

/* 摂氏の温度を -20 C から 40 C までを 10 C 刻みで,

* と華氏の温度に変換して表示するプログラム

* ただし, 表示は小数点以下２桁目を四捨五入

*/

#include <stdio.h>

int cersius ; double fahrenheit ;

for(cersius=-20;cersius<=40;cersius+=10) { fahrenheit = cersius*9.0/5.0 + 32.0 ;

printf("%1.f C = %.1f F\n", (double)cersius, fahrenheit) ; }

return 0 ; }

/* prog06-3-2.c */

*/

#include <stdio.h>

int cersius ;

for(cersius=-20;cersius<=40;cersius+=10)

printf("%d.0 C = %.1f F\n", cersius, cersius*9.0/5.0 + 32.0) ; return 0 ;

}

これら２つの例では,摂氏の温度をint型変数としてループを実行し,ループ内部でdoubleの演算を行っている. （計算の部分で9.0/5.0としていることに注意しよう.）

while文を使うならば次の例のようになる.

(6)

/* prog06-3-2.c */

*/

#include <stdio.h>

int cersius ;

cersius = -20 ; while(cersius<=40) {

printf("%d.0 C = %.1f F\n", cersius, cersius*9.0/5.0 + 32.0) ; cersius += 10 ;

}

return 0 ; }

これらの例では,摂氏温度を表す変数がint型で,華氏温度を表す変数がdouble型になっている. これが「美しくない」と考える場合には次のような例もあり得るだろう.

/* prog06-3-2.c */

*/

#include <stdio.h>

double cersius, fahrenheit ; int main(int argc, char **argv) {

cersius = -20.0 ;

while(cersius<40.0+0.005) {

fahrenheit = cersius*9.0/5.0 + 32.0 ;

printf("%.1f C = %.1f F\n", cersius, fahrenheit) ; cersius += 10.0 ;

}

return 0 ; }

ここで,ループ終了条件として

cersius<40.0+0.005

を用いている理由は以下の通りである. 変数 cersiusは double 型の変数であるため, 初期値-20.0から 10.0を６回加算したときの値は 40.0と本当に等しいかどうかわからない. そのため, 「少々の誤差」

を見込んで「40.0 + 0.005未満の場合にはループを実行」する条件文をおくことが望ましい. （実際には,10.0を加えているため,cersius <= 40.0でも正しく動作するが,0.10を加えていくと正しく動作しなくなる.）なお,「誤差」をどのくらいにとればよいかは難しい問題であるが,doubleが１０進１３桁程度の精度を持っているので, 加算する値に比べて数桁小さい値を使えばよいだろう. また,Ｋ＆Ｒの第１章ではcersius <= 40と同値な評価式を用いている（Ｋ＆Ｒ, １５ページ）. これは,「初心者のための解説」,「10.0を加えるので,誤差が生じない」などの理由が裏に隠れていることに注意しよう. すなわち,

(7)

以下のprob06.cは switch文を利用して,0から12までの整数が２,３,６の倍数かどうかを判定している. ところが, 実行してみればわかる通り, 正しい結果を出力しない. どこにバグがあるのかを調べ,正しい結果を出力するように修正しなさい.

バグフィックスしたものは以下の通り.

/* prob06.c */

/* 非負整数が 6, 3, 2 の倍数かどうかを判定する. */

#include <stdio.h>

unsigned int n, mod, mod_2, mod_3 ; int main(int argc, char **argv) {

for(n=0;n<=12;n++) { mod_2 = n&1 ; mod_3 = n%3 ;

mod = !mod_2 + (!mod_3<<1) ; switch(mod) {

case 3:

printf("%d は６の倍数\n", n) ; break ;

case 2:

printf("%d は３の倍数\n", n) ; break ;

case 1:

printf("%d は２の倍数\n", n) ; break ;

default:

printf("%d は３の倍数でも２の倍数でもない\n", n) ; break ;

} }

return 0 ; }

バグは２ヶ所に存在していた.

• case 2: のところにbreakが抜けていた.

• modの計算式に括弧を挿入した.

ここで用いている演算子 !,<<,+の優先順位は, 高い順から!,+,<<となっている.

プログラムの意図は,２の倍数かどうかの判定「フラグ」を modの１ビット目,３の倍数かどうかの判定フラグをmodの２ビット目にセットすることであったので,上のように括弧をつける必要がある.

なお,次のような書きかえも考えられる. （これなら括弧は必要ない.）

mod = !mod_2 | !mod_3<<1 ;

この他にも,

• default: のところにbreakをいれた方がよい.

という改良を加えている.

● 実習内容 【課題】

● 実習内容

prog07.c

● 前回の課題の解説

● 実習内容【課題】