平成20年 春期 ソフトウェア開発技術者 午前 問13

次の流れ図において、ステップS4でYesと判断したときまでの、ステップS1〜S4の実行回数をそれぞれn1〜n4とする。
n1〜n4の間に成立する式はどれか。

　ア 　n4=n1+n2+n3 　イ 　n4=n1+n2-n3
　ウ 　n4=n1-n2+n3 　エ 　-n4=n1+n2+n3

答え　ウ

【解説】
各比較処理(分岐処理)(S1、S3、S4)のYesとNoの場合のときの回数を調べる。

  • S1がNo、S4がYesのときは、
    S1が1回
    S2が0回
    S3が0回
    S4が1回
    なので、n4の計算式としては
    n4=n1+n2+n3(ア)
    n4=n1+n2-n3(イ)
    n4=n1-n2+n3(ウ)
    のいずれかである。(選択肢エはありえない。)
  • S1がNo、1回目のS4がNo、S3がYes、2回目のS4がYesのときは、
    S1が1回
    S2が0回
    S3が1回
    S4が2回
    なので、n4の計算式としては
    n4=n1+n2+n3(ア)
    n4=n1-n2+n3(ウ)
    のいずれかである。(選択肢イとエはありえない。)
  • S1がYes、S3がYes、S4がYesのときは、
    S1が1回
    S2が1回
    S3が1回
    S4が1回
    なので、n4の計算式としては
    n4=n1+n2-n3(イ)
    n4=n1-n2+n3(ウ)
    n4=n1+n2+n3(エ)
    のいずれかである。(選択肢アはありえない。)
これより、n4の計算式としては
　n4=n1-n2+n3
(ウ)であることがわかる。

【キーワード】
・計算量

【キーワードの解説】
  • 計算量
    コンピュータの処理時間を考えた場合、最も正確に測定する方法は実際にプログラムを作って実機で処理時間を計測する方法であるが、プログラムの設計段階で2つのアルゴリズムの計算時間を比較する場合には、プログラムを作って比べることは難しいため、各アルゴリズムの計算量を調べて、計算量で比較を行います。
    一般にコンピュータの処理で時間がかかるのは、比較演算であるので計算量を考えるときは、そのアルゴリズムの比較演算の回数を用います。
    計算量を表す記号はオーダ(程度)を意味するO ( )を使用します。

もっと、「計算量」について調べてみよう。

戻る 一覧へ 次へ