Break 文
for 文、while 文、do 文の繰り返し処理を、途中で中断したい場合がある
break 文は、繰り返し文中で、繰り返し本体の実行を終了させる
while( ... ){
...
if( ... )
break;
...
}
/* breakにより、ここに実行が移る */
途中でループを抜けるのに用いる
ループ中で break 文が実行されると、そ
れを囲む繰り返し文(この例の場合は
while 文)が終了。
for 文、do 文でも同じ。
1
Continue 文
ループ本体中に書かれた continue 文は、それ以降の処理をスキップし、繰り
替えし式の評価から繰り返しをやり直す。
for( 式1; 式2; 式3 ){
...
if( ... )
continue;
...
/* continueにより、ここに実行が移る */
}
break 文、continue 文を使うことで、柔軟な繰り返し処理(式による繰り返し判定+
例外処理)が可能になる。
2
Continue 文
i=0;
while( i<10 ){
...
if( ... )
continue;
...
i++;
}
for(i = 0; i < 10; i++){
...
if( ... )
continue;
...
}
while文でcontinueを使った場合、最後の i++;
が実行されない事に注意。
3
Goto 文とラベル
goto文を使うと、もっと自由に次に実行する文を選べる。
構文は、
goto ラベル名
ラベルの指定は(名前にコロン: を付ける)
ラベル名:
goto文を使うとプログラムの実行を自由に走査出来てしまうので、動作
を理解することが難しくなる。あまり使わない方がよい。。
while( 式 ){
i=0;
...
while( i<10 ){
while (…) {
...
if( ... )
if( ... )
goto cont;
指定したラベルに移動する。
goto owari ;
...
...
cont:
ラベルの指定
}
i++;
}
}
owari:
4
Switchの中でのContinue文
1 文字ずつ読み取り、各アルファベットの出現回数を数えるプログラム
int count_a, count_b, ...
int a;
while( (a=getchar()) != EOF ){
switch( a ){
case 'a': count_a++; break;
case 'b': count_b++; break;
....
default: continue;
}
count_char++;
continue 文は、ループ中から
ループの先頭へ制御を移動
continue 文の実行により、ルー
プ本体の最後へ処理が移る。
つまり、繰り返しを判定する式
の評価へ移動。continue 文の
後の処理はスキップされる。
/* continueの実行によりここに処理が移る */
}
このプログラムではアルファベット以外の文字数 count_char を数えていない。
5
様々な繰り返し処理
数列 {1, 2, 3, 4, ..., n} の和を求めるプログラム
手順:
1) n の入力 (n > 1)
2) for 文を用いて和を計算
int i, n, sum=0;
scanf(“%d”, &n);
for(i=1; i<=n; i++)
sum += i;
参考までに
printf(“総和は %d \n”, sum);
である。
同じ動作をするプログラムを while 文・do 文を使って書いてみる。
6
円周率の計算
であることを利用して円周率の近似値を求めるプログラム
積分区間 [0, 1] を細かく区切り、短冊の面積を合計することで積分を近似
int i;
double dx = 0.01, sum = 0;
区間幅を dx とする
for(i=0; i<100; i++)
sum += 1.0/(1+ (i*dx)*(i*dx))*dx;
積分は足し算にほか
ならない
printf(“%f\n”, 4*sum);
として変数変換。積分区間は
より
7
素数
1 と自分自身以外では割り切れない自然数を素数という。ただし 1 は素数ではない
2, 3, 5, 7, 11, 13, ...
自然数 a が素数かどうかを判定するアルゴリズム
a が、2 で割り切れない ( a%2 != 0 )
3 で割り切れない ( a%3 != 0 )
4 で割り切れない ( a%4 != 0 )
.....
a–1 で割り切れない ( a%(a–1) != 0 )
a は素数である
a–1 までためす必要はないのでこ
のアルゴリズムは効率悪い
具体例
11 は、2, 3, 4, 5, 6, 7, 8, 9, 10 のいずれでも割り切れないので、素数。
35 は、2, 3, 4 で割り切れないが、5 で割り切れるので素数ではない。
8
素数判定のプログラム
int a, i;
printf(“自然数を入力:”);
scanf(“%d”, &a);
i=2;
while( a%i != 0 ){
i++;
}
if( i==a )
printf(“%d は素数です\n”, a);
else
printf(“%d は素数ではない\n”, a);
a が i で割り切れなければ i を
インクリメント。
a%a は 0 なので、繰り返しは必ず終了。
繰り返し変数 i が a に達した時のみ a
は素数である。
このプログラムでは a を i = 2, 3, 4, ..., a–1, で割っているが、i の範囲は floor( sqrt(a) ) までで十分
である。floor(double x) は x を越えない整数値を返す関数。math.h で定義されている。
9
少し効率の良い素数判定
a = 24 の素数判定には、24 を i = 2, 3, 4, 5, ..., 23 で割る必要はない。
24 の平方根 4.899 (sqrt(a))を越えない整数値の範囲 i = 2, 3, 4 で十分。
途中 i = 2 で割り切れれば直ちにループを抜けて、無駄な割り算はしない。
int i, a = 17;
for(i=2; i*i <= a; i++){
if( a%i == 0)
break;
}
if( i*i > a)
printf("%d は素数\n", a);
i < √aの代わりに、i2 < a で判定
break 文でループを抜ける
途中で割り切れてループを抜けた
なら a は素数ではない
さらに、2以外の偶数で割る必要はない!。(なぜ?)
10
フラグ変数
状態を表す値をとる変数をフラグ変数という。フラグ flag = 旗。
素数判定において、自然数 a が素数であるかどうかを判定するアルゴリズムとして
次がある。
1) フラグ変数を int 0 に初期化。
2) 繰り返し処理により、a を i = 2, 3, 4, ..., floor(sqrt(a)) で割り、
割り切れればフラグ変数を int 1 にする。
3) 繰り返し処理が終了した時点で、フラグ変数が 0 であれば a は素数。
int warikireta = 0, i, a=41;
for(i=2; i*i <= a; i++){
if( a%i == 0){
warikireta = 1;
break;
}
} /* end of for */
if( warikireta == 0)
printf("%d は素数\n", a);
フラグ変数を 0 (False) として初期化
途中で割り切れたらフラグ変数を 1
(True) とする。フラグを立ててループ
を抜ける。
最後にフラグが立っていなければ a
は素数。
11
素因数分解
素因数分解とは、自然数を素数の積の形に分解すること
例:84 = 2*2*3*7
84 を 2 で割ると、42 余り 0 (割り切れる)
42 を 2 で割ると、21 余り 0 (割り切れる)
21 を 2 で割ると、割り切れない
21 を 3 で割ると、7 余り 0 (割り切れる)
7 を 3 で割ると、割り切れない
7 を 4 で割ると、割り切れない
7 を 5 で割ると、割り切れない
7 を 6 で割ると、割り切れない
7 を 7 で割ると、1 余り 0 (割り切れる)
12
素因数分解アルゴリズム
自然数 a に対して、
1) 2 で割り切れるかぎり、a を 2 で割った商を、2 で割ることを繰り返す
2) 3 で割り切れるかぎり、商を 3 で割ることを繰り返す
3) 4 で割り切れるかぎり、商を 4 で割ることを繰り返す
(4 で割り切れるなら 2 で割り切れているので実際は不要)
4) 5 で割り切れるかぎり、商を 5 で割ることを繰り返す
...
5) 割り算の結果が商 1 余り 0 となれば終了
手順 1) は次のように書ける
int a, i;
i=2;
while( a%i == 0){
a=a/i;
}
2 で割り切れるかぎり商を 2 で割り続ける
整数同士の除算(割り算)の結果は整数である!
13
最大公約数
2 つの自然数 a と b の最大公約数を求めたい
例)36 と 42 の公約数は次のようにして求められる。
36%2 == 0 && 42%2 == 0 なので 2 は公約数
36%3 == 0 && 42%3 == 0 なので 3 は公約数
36%4 == 0 && 42%4 != 0 なので 4 は公約数ではない
36%5 != 0 && 42%5 != 0 なので 5 は公約数ではない
36%6 == 0 && 42%6 == 0 なので 6 は公約数(これが最大)
36%7 != 0 && 42%7 == 0 なので 7 は公約数ではない
...
36%36 == 0 && 42%36 == 0 なので 36 は公約数ではない
36 までためす必要はない
(効率の悪いアルゴリズム)
14
最大公約数を求める方法(効率悪い)
int a, b, i, gcd=1;
scanf(“%d %d”, &a, &b);
/* a >= b であるとする */
for(i=2; i<=b; i++){
if( a%i==0 && b%i==0 )
gcd=i;
}
新しい公約数 i で gcd の値を更新
printf(“%d と %d の最大公約数は %d\n”, a, b, gcd);
少なくとも b 回の割り算が必要。より少ない計算量で最大公約数を求めるアルゴ
リズムが知られている。
15
ユークリッドの互除法
最大公約数を求める効率的な方法の一つ。Euclid : 古代ギリシャの数学者
2 つの自然数 a, b の大きい方を x, 小さい方を y とする。
1) x を y で割った余りを r とする。
2) r が 0 でないかぎり、以下 a), b), c) を繰り返す。
r = x % y;
a) y を x に代入。
while( r != 0 ){
b) r を y に代入。
x = y;
c) x を y で割った余りを r とする。
y = r;
3) y が a と b の最大公約数である。
r = x % y;
}
例)a = 42, b = 24 の時(x = 42, y = 24)
42 / 24 は、1 余り 18 ( r = 42%24 ), r の値は 0 ではない。
x=24, y=18 として、24 / 18 は、1 余り 6。r の値は 6(0 ではない)。
x=18, y=6 として、18 / 6 は、 3 余り 0。(r の値は 0 となって割り切れる)
6 が最大公約数である。
16
問題 1 素数判定
入力した正の整数値が素数であるかどうかを判定するプログラム。Ctrl-D が入
力されるまで判定を繰り返す。
% ./a.out
自然数を入力:35
35 は素数ではない。
自然数を入力:9
9 は素数ではない。
自然数を入力:17
17 は素数である。
自然数を入力:-9
入力エラーです。
自然数を入力:Ctrl-D
プログラムを終了します。
%
この色はプログラムによる出力
17
問題 2 素因数分解
自然数を入力し、素因数に分解するプログラムを作れ。
エラー処理も行うこと。
% ./a.out
自然数を入力:24
24 = 2*2*2*3
% ./a.out
自然数を入力:144
144 = 2*2*2*2*3*3
% ./a.out
自然数を入力:-9
入力エラー
%
この色はプログラムによる出力
18
問題 3 最大公約数
ユークリッドの互除法を用いて、入力した 2 つの自然数の最大公約数を求めるプロ
グラムを作れ。
% ./a.out
自然数を2つ入力:54 144
144 と 54 の最大公約数は 18 です。
%
この色はプログラムによる出力
19
問題 4 完全数
完全数とは、約数(自分自身は除く)の和が自身と等しい自然数である。
例)6 の約数は 1, 2, 3 であり、1 + 2 + 3 == 6 であるので、6 は完全数。
6, 28, 496, 8128 は完全数である。
可能な限りたくさんの完全数を探すプログラムを作れ。
% ./a.out
見つけた!6
見つけた!28
見つけた!496
見つけた!8128
...
%
ヒント:a が完全数かどうかを判定する部分を作成。
これを a に関するループで囲めば良い。
プログラム実行結果の表示
20
約数の和を求める
約数の和を求めるには、1から始めて、順に割っていき、割り切れた数の合計を
求めればよい。
int goukei = 0;
int i, n;
n=280;
// たとえば、280の約数の和を求める
for(i=1; i < n; i++){
if( n%i == 0)
goukei += i
}
printf(“%dの約数の和は%d \n", n,goukei);
21
問題 5 借金の返済
年率rでx円を借りる。返済は毎年y円返していくことにする。一年後から完済するまで、
毎年の返済額、残額、返済額の合計を表示するプログラムを作れ。
利息は複利で計算するものとする。
% ./a.out
借用金額を入力:1000000
利率を入力(%):3.0
毎年の返済額を入力:100000
借用金額 1000000円、毎年の返済額 100000, 利率 3.00%
1年目, 返済金 100000円, 残金 930000円, 返済額 100000円
2年目, 返済金 100000円, 残金 857900円, 返済額 200000円
............
12年目, 返済金 100000円, 残金 6558円, 返済額 1200000円
13年目, 返済金 6755円, 返済金の総額 1206755円
%
プログラム実行結果の表示
一年後の借金の総額は
x(1+r/100)
である、これからyを引
いた金額が残金である。
二年目以降も、残金に
(1+r/100)
を掛けた金額が借金の
総額で、これからyを引
いた金額が残額である。
借金の総額がy以下で
あれば、返済が完了す
る。y円を返済して終了
するl。
22
繰り返しの考え方
1)x,y,rを入力する
2)x=x*(1+r/100);1年度後の借金額
3)もしy>=xならx円を返済して終了
4)x=x−y;
返済後の借金の残額 この範囲を繰り返す
5)x=x*(1+r/100);1年度の借金額
6)もしy>=xならx円を返済して終了
7)x=x−y;
。。。。。。。
これを続ける
繰り返すのは、2)〜4)の間。しかしこれでは、繰り返しの終了判定が
3)で、繰り返しの途中になる。(break文を使えば、途中での終了も可能)
あ) whileでの繰り返しの終了判定は、繰り返しの最初におこなう。
い) do〜whileでは繰り返しの最後に行う。
あ)の場合は、3)から5)を繰り返す。
い)の場合は、4)から6)を繰り返す。
23
あ)の場合
い)の場合
x,y,rを入力する
x=x*(1+r/100);1年度後の借金額
while (y < x) {
x=x−y;
返済後の借金の残額
y円を返済して、返済後の借金額はx円
x=x*(1+r/100);1年度の借金額
}
if (x > 0)
x円を返済
x,y,rを入力する
x=x*(1+r/100);1年度後の借金額
if (y < x) {
do {
x=x−y;
返済後の借金の残額
y円を返済して、返済後の借金
額はx円
x=x*(1+r/100);1年度の借金額
} while (y < x);
}
if (x > 0)
24
ダウンロード

7週目