B16  アルゴリズム



努力目標

  理解する




技術士試験の問題からは必要最小限の引用にとどめる。(問題)が記されている部分はその引用である。

問題および解答は日本技術士会のホームページより必要に応じて入手してください。

  技術士第一次試験の問題       技術士第一次試験の正答(答え)  



問題番号が赤字のものは、ボーナス問題

H28年 1−2−3   H26年 1−2−2   H24年 T−2−5

H16年 T−2−5




プログラムを組んだことのある人には簡単な問題ですが、そうでない人には難しい問題かもしれません。試験時間中にデータを追いかけるにも、時間がとられてしまいそうです。自信がなければパスもありですね。

なお、この問題後略のポイントは、やはり極端なケースを想定して数字を回してみる、ということでしょうか。簡単なプログラムをExcelの裏で作り走らせてみると理解が進むのですが、時間との相談ですね。



H28年 T−2−3

H28年度問題

正答: @ 

(解答)


(ウ)がDに示された2Nであったならどのようなことが起こるか?

問題文の通りに計算を進めると、

まず I=−1、N=11>0 なので計算は下へ

カウンターが I=−1+1 で I=0 に

 11÷2=5 余り 1

A{0}=1、N=5 となるべき。ところが
N=11のままですから、2N=22、 従って、
A{0}=1、N=22 となってしまう。

このN=22が「Nと0を比較」で(ア)に進み、

 22÷2=11 余り 0

Nは22のままですから、N=24に、

そしてループは周り続け、N−48、N=96・・・・
この計算はいずれ、オーバーフローで停止する運命にあります。




H26年 1−2−2

H26年度問題 

正答: A 

(解答)


「あまりRが0になるまで、繰り返す」と書かれているのだから、
当然、(ア)はR=0、そうすると(イ)はR≠0.

「AとB」の公約数を求める、と言っているのだから、当然(ウ)は求める公約数Rとなる。



実際に数値Aおよび数値Bに整数を与え、このループをたどってみると、この計算アルゴリズムの動きがわかる。

あるいは、実際にプログラムを組んでみると、最初はおそらく、思った答えが出てこないので、アルゴリズムの良い勉強になる。


Basic では
AをBで割った時の余りは   A MOD B
AをBで割った時の商は    A ¥ B

である。



H24年 T−2−5

H24年度問題 

正答: A 

(解答)

左のアルゴリズムでわかるように、最初に最小値(min)には1000が、最大値(max)には0が与えられています。初期値として最小値に多いな値、最大値に小さな値を入れておくのは最大値、最小値を求める場合の常とう手段です。

さて、問題で与えられたアルゴリズムはうまく働くでしょうか? 極端な場合を想定してシミュレーションしてみれば、結果がわかります。

いま、最大値と最小値を知りたいデータセットは1000個の実数より構成されています。1000個の整数ではありません。

が999、aが998.9、aが999.8と規則的に999から0.1ずつ小さくなっていくデータセットを考えます。1000個目のデータは999−0.1×999=899.1となります。このデータセットをaからa1000まで順番にコンピュータに通すと、最小値は毎回更新されていきますが、最大値判定のループには入れませんので、計算終了時には最大値は初期値である0のままとなります。最小値は繁栄するが、最大値については保証のないプログラム(アルゴリズム)ということになります。

これを改良しようとすれば、右のようなアルゴリズムに書き直す必要があります。すべてのaiについて、最大値も最小値も判定するループが付いています。





H16年 T−2−5

H16年度問題

正答: C 

(解答)



最初に負の数、たとえば X=−1 が来たときには、a>0 の判定で N となり、出力ルーチンへと作業が移ります。ここで X=−1 の出力となります。従って、Cは誤りであることが分かります。

参考までに、この流れを左の図にしてみましたので、C以外のデータの動きも確認してください。




                問題一覧表へ戻る