電算工学-I 後期中間試験 (by望月 '99 12月)

• 筆記用具以外に持ち込み可なものは， テキスト(ザ・Ｃ 第2版)のみです。 誰の作成であろうと， プリントやメモ書き等の持ち込みは禁止です。
• 授業中に実行させたプログラムや 私が過去に作ったプログラムを参考にしましたが， 同様な問題を出す場合は数値は変えましたので， 注意して下さい。
• 回答は，空きスペースの適当な場所に書いて下さい。
• 部分点もありますので，正解が思い浮かばない場合でも， 恥ずかしがらずに回答をトライしましょう。
• もしも回答を，裏面など別の場所に書いたならば， 赤ペンや太くて大きい文字などわかり易い文字で 「裏も回答あり」，「回答はあちらにあります −−→」 というふうに明記して下さい。 回答する場所が分からない場合，採点しない可能性があります。

問

(ボーナス問題) 2値符号を使って数値を表わす方法は， 何通りも存在する。
もっとも普通に使われるのは2進数であり， 例えば10ビット使うことが出来るのであれば， 0 〜 1023 (= 2 の 10乗 から 1を減じたもの) を表わすことが出来る。
日本古来の表わし方のひとつが，そろばんであり， 1個の5の玉と，4個の1の玉の位置で一桁を表わす。 これは，5ビットにより数字一つを表わすと考えられる。 10ビット使うことが出来るのであれば， 0 〜 99 を表わすことが出来る。

それでは，2進数と，そろばん方式について， お互いを比較してそれぞれの長所を述べよ。

・2進数を使うと，同じビット数で大きな数を表わせる。
・2進数を使うと，計算機内で簡単なハードウエアで計算可能。
・そろばんは，広い意味では10進数であり，人間に理解しやすい。
・そろばんは，人間が使うのと同じアルゴリズムで計算できる。






問2 次のプログラム(抜粋)のなかの�@, �Aおのおのの演算は違った答えとなるというが， その理由を述べよ。
(注意：模擬試験とは数値が変えてあります。)


int a; float b; a = 10/7; �@ b = 10./7.; �A


・�@は整数型演算をし，�Aは実数型演算をする。
・整数型演算では小数点以下を切り捨てるが，実数型演算では切り捨てしない。

問3 次のプログラム(抜粋)のなかの�@〜�Bにおいて， 指示された変数はいくらなのか述べなさい。
(注意：模擬試験とは数値も式も変えてあります。)


int a,b,c; a = 2; b = 3; c = a + b; �@ このとき c の値は? b = b + c; �A このとき b の値は? a= a + b - c; �B このとき a の値は?


・�@では，c は 5
・�Aでは，b は 8
・�Bでは，a は 5 (=2+8-5)






問4 次にあげる4つのプログラムは， 小さい数から順番に大きな数を表示するが， それぞれ幾つから幾つまで表示するか答えよ。
ヒント：ループの最初と，ループの最後に特に注意しよう。
(注意：模擬試験とは数値を変えてあります。)


int i; i=1; while(i<=4){ printf("%d\n",i); i=i+1; } 1,2,3,4	int i; i=1; do{ i=i+1; printf("%d\n",i); }while(i<=4); 2,3,4,5
int i; for(i=1; i<4; i=i+1){ printf("%d\n",i); } 1,2,3	int i; i=1; while(i>=0){ if(i==4) break; i=i+1; printf("%d\n",i); } 2,3,4

問5 次のプログラム(抜粋)は， �@の所では変数 a の値は 0 から 9 まで変化する。 if文により �Aにて出力するのは a がいくつの時なのか， 値をすべて記せ。
(注意：模擬試験とはif文の条件式を変えてあります。)


int a; for(a=0; a<10; a=a+1){ printf("%d\n",a); �@ if( (3<a) && (a<7) ){ printf(" condition = true\n"); �A } }

4,5,6





問6 次のプログラム(抜粋)は，次の動作をするように作られた：
配列 byou[i] には， クラスの 出席番号 i の人の1500メートル走の時間(秒)が入っている。 最も早かった人の出席番号と，その時間を求める。
しかし，�@の部分 ( 複数行が入る可能性あり ) が未完成である。 ここを埋めて，正しく動作するようにしなさい。
(注意：模擬試験とは目的とする動作が多少変わってます。)
(注意：また，max という変数を使わなくしています。)


int byou[100],n,i,isaikou; //この部分で，以下のように設定／入力 // n : 最大の出席番号 // byou[i] : 出席番号 i の人の点数 // byou[1] から byou[n] が有効な数字 printf("1 番目の人の点数は，%d です。\n",byou[1]); isaikou=1; for(i=2; i<=n; i=i+1){ printf("%d 番目の人は，%d 秒で走りました。\n",i ,byou[i]); �@ if( byou[i] > byou[isaikou] ){ printf("この人は最高記録ではありません\n"); }else{ printf("最高記録の候補です\n"); isaikou=i; }; } printf("最高記録は %d 番目の人による %d 秒です。\n",isaikou ,byou[isaikou]);


問7 次のプログラム(抜粋)は，次の動作をするように作られた：
配列 tensu[i] には，クラスの 出席番号 i の人のテスト結果が入っている。 点数の小さい順に並べ替えて表示する。
テスト時に特に指定しませんでしたが，次の事も考慮して下さい。
「並べ替えのアルゴリズムは幾つも存在するが，ここでは次のアルゴリズムに沿ってプログラムする。」
並べ替えのアルゴリズム(考え方)：
1. まず，tensu[1] 〜 tensu[n] の中には， クラスの最低点が存在するはずである。
2. 1番目の点数と，その他すべての点数を比較し， クラスの最低点を求め，tensu[1]に入れる。
3. すると，tensu[2] 〜 tensu[n] の中には， クラスの2番目に低い点数が存在するはずである。
4. 2番目の点数と，その他すべての点数を比較し， その中の最低点を求め，tensu[2]に入れる。
5. すると，tensu[3] 〜 tensu[n] の中には， クラスの3番目に低い点数が存在するはずである。
6. 同様に繰り返し，tensu[n-1] まで求める。
7. すると，tensu[n] には，自動的にクラスの最高点が入っているはずである。
8. 以上により動作完了
9. 後は印刷するだけである。
しかし，このプログラムは，一部おかしい点がある。 (ここでは敢えて'おかしい'ということがどういう点か述べない) 正しく動作するにはどの部分をどう変更したら良いか答えなさい。
ヒント：n を 4 くらいに置いて，どういう動作が行われるか検討してみよう。
(注意：模擬試験とは異常動作の原因を変えてあります。)


int tensu[100],t,n,i,j; for(i=0; i<100; i=i+1) tensu[i]=0; //この部分で，以下のように設定／入力 // n : 最大の出席番号 (1クラスは約80名とする) // tensu[i] : 出席番号 i の人の点数 // tensu[1] から tensu[n] が有効な数字 // tensu[0] は 0 // tensu[n+1] から tensu[99] は 0 for(j=1; j<(n-1); j=j+1){ for(i=(j+1); i<=n; i=i+1){ if( tensu[j]>=tensu[i] ) { t=tensu[i]; //以下3行でならべ変え tensu[i]=tensu[j]; tensu[j]=t; } } } for(j=1; j<=n; j=j+1){ printf("%d 番目に低い点数は，%d です。\n", j, tensu[j]); }


正しい動作のためには。上の青い行を，
for(j=1; j<n; j=j+1){
と変更すべきである。そうしないと，最後の2つの比較が行われない。

なお，上の緑の行を，
if( tensu[j]>tensu[i] ) {
と変化させると，無駄時間が減って，より優れたプログラムとなる。 等しい場合にはわざわざ並べ替える必要はないからである。 (わざわざ並べ替えても，動作の正しさは変わらないが)




数値計算の問題 (関数も使って)
問8 x という数値の平方根を求めるには， 普通には sqrt という関数を用い，
　　y = sqrt(x);
という風に用いる。

しかし，sqrt を使わなくても計算する方法がある。
ここでは，0 < x < 1 という x に対して， 有効桁数 5桁で，sqrt(x) とほぼ同じ値を返す関数を考えよう。
(教科書には p.83 にその方法が載っているが， ここでは別のスマートな方法を使おう。)

まずは，解の条件を明確にする。

1. この場合，y から x に対して，x=y*y という式が成り立つ。
2. x は 0.0 〜 1.0 であるため， y も 0.0 〜 1.0 の筈である。
3. また，y は一つだけである。
このように，逆関数があり，解の下限と上限が決まり， 一意に決まるという3つの性質を持つことから， 次に述べるアルゴリズム(考え方)によって， 必ず正しい解を求めることが出来る。

解法のアルゴリズム(考え方)：
1. まず 解の候補として 変数 a, b を定義する。
   変数 a, b それぞれの初期値は 0.0 と 1,0 とする。
2. (i)と(ii)の条件より，
   a*a < x < b*b
   という関係式が成り立つ。
   
3. 次の操作により。(II)の関係式を満たしながら，a と b の差が縮まるよう値を変えて行く。
   1. c=(a+b)/2. を計算する。
   2. 解は，a*a 〜 c*c の間か，または，c*c 〜 b*b の間の何れかに存在する。
      どちらに存在するか判定し，それに応じて a または b の値を書き換える。
   3. 以上の作業により， a と b の差は，半分になった。
   4. 望みの精度に達するまでこの作業を繰り返す。
4. a または b の値を解として表示する。
以上を C 言語に焼き直した正しく動作するプログラムを次に示す。

しかし，このプログラムは冗長度が高いため， 処理時間を考えるとベストな解とは言えない， もっと処理時間を短くするには，必要十分な動作をするよう書き換える必要がある。
そのためには何処をどう変更したら良いか答えなさい。


#include double f(double y) { return(y * y); } main() { double a,b,c,x; // ここで，x に 0 から 1 までの値を設定する。 a=0.0; b=1.0; while( (b-a) > 0.00001 ){ c=(a+b)/2.0; if( (f(a) <= x) && (x < f(c)) ){ b=c; }else if( (f(c) <= x) && (x <= f(b)) ){ a=c; }else{ printf("この関数はこのアルゴリズムでは扱えません。\n"); exit(); //プログラム終了 } } printf("%d の平方根は，%d です。\n", x, a); }


プログラムの中の青い部分は大いなる冗長性を含んでおり，次のように書き直せます。

if( x < f(c)) ){
	b=c;
}else{
	a=c;
}

だって，
・c=(a+b)/2. としたら，
・解は，a*a 〜 c*c の間にあるか， または，c*c 〜 b*b の間にあるかどちらかですから， 最初の if で計算したら，else if で改めて計算する必要はないで。
また，解はもともと a*a 〜 b*b にあるのですから， 毎回 a や b を条件式に入れる必要もありません。

なお，while を for ループに焼き直す人がいましたが， 本題からいってむしろ while のほうがすんなりいきます。

else の最後のコメントは本来ありえないはずですが， 場合によっては，while ループに入る前に x の値をチェックし， 範囲をそれているようでしたらこのコメントを出力するという手もあります。 (この部分は学生の回答により気がつきました)

注意：このアルゴリズムは「2分法」と呼ばれています。 先に述べた条件さえ満たしていれば，確実に解を求めることが出来ます。
例えば，ある計算機が，ライブラリの関係で， 指数関数は計算できても log を計算できなかったとします。 こんな時でも，同じアルゴリズムで log を求めることが出来ます。 その場合は，関数 f(x) を書き換えれば OK です。 但し，x の変域に気をつけるのをお忘れなく。