平成21年秋期試験午後問題 問8

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】

問8 データ構造及びアルゴリズム

次のアルゴリズムの説明及びプログラムを読んで,設問に答えよ。

 方程式の解の一つを求めるアルゴリズムである。任意に定めた解の予測値から始めて,計算を繰り返しながらその値を真の値に近づけていく。この方法は,ニュートン法と呼ばれる。

〔アルゴリズム1の説明〕
 3次方程式 a3x3+a2x2+a1x+a0=0 の解の一つを,次の手順で求める。
  • 解の予測値 x,係数 a3,a2,a1,a0 を読み込む
  • 3×a3をb2に,2×a2の値をb1に,1×a1の値をb0に,それぞれ求める。
  • 次の①~④の処理を一定の回数繰り返す。
    1. a3x3+a2x2+a1x+a0 の値を求め,これを f とする。
    2. b2x2+b1x+b0 の値を求め,これを d とする。
    3. x,f,dの値を印字する。
    4. x-ƒdの値(解の一つにより近い値となる)を求め,これを新たな x とする。
 プログラム1は,このアルゴリズム1を実装したものである。

〔アルゴリズム2の説明〕
 アルゴリズム1を一般化して,n次方程式 anxn+an-1xn-1+…+a1x+a0=0 の解の一つを,次の手順で求める。
 なお,方程式によっては解が求められない場合がある。
  • 次数n,解の予測値x,係数an,an-1,…,a1, a0 を読み込む。
  • n×an の値を bn-1に,(n-1)×an-1 の値を bn-2に,…,2×a2 の値をb1に,1×a1の値をb0に,それぞれ求める。
  • 次の①~④の処理を一定の回数繰り返す。
    1. anxn+an-1xn-1+…+a1x+a0 の値を求め,これを f とする。
    2. bn-1xn-1+bn-2xn-2+…+b1x+b0 の値を求め,これを d とする。
    3. x,f,dの値を印字する。
    4. x-ƒdの値(解の一つにより近い値となる)を求め,これを新たな x とする。
 プログラム2は,このアルゴリズム2を実装したものである。
pm08_2.png

設問

次の記述中の に入れる正しい答えを,解答群の中から選べ。
  • 解の予測値 x=2.5,係数 a3=1,a2=-3,a1=-1,a0=3 を与えて,3次方程式 x3-3x2-x+3=0 の解の一つを求める(解は3,1,-1)。プログラム1を有る処理系で実行した結果,図1に示す通り解の一つであるx=3が近似的に得られた。
    pm08_3.png
     この印字結果の行番号6,7のxの値(網掛けの部分)はいずれも3.000000である。行番号6,7を印字した時点で変数xに保持されていた実際の値をそれぞれ x6, x7 で表すと,a
     なお,この処理系では,実数型は2進数の浮動小数点形式であって,有効けた数は10進数で十数けた程度であることが分かっている。
  • プログラム2では,係数 ak (k:n,n-1,…,1,0)の値を配列 a の要素 a[k] に,bk (k:n-1,n-2,…,1,0)の値を配列 b の要素 b[k] に,それぞれ図2のように格納している。
    pm08_4.png
     プログラム2の行番号9~11は,アルゴリズム2の手順(2)の処理である。この部分のプログラムは,次のようになる。
    pm08_5.png
     また,行番号13~18は,アルゴリズム2の手順(3)の①と②の処理である。
    プログラム1では,例えばfの値a33+a22+a1x+a0を求める式を,

      f←((a3×x+a2)×x+a1)×x+a0

    と変形して,演算回数を減らす工夫をしている。この部分にも同様の工夫をすると,プログラムは次のようになる。
    pm08_6.png
  • 次数n=4,係数a4=1,a3=-8,a2=24,a1=-32,a0=16として,4次方程式 x4-8x3+24x2-32x+16=0 の解を求める(4個の解がすべて2)。解の予測値をx=2.00001として,ある処理系でプログラム2を実行したところ,図3に示すとおりの印字結果となった。
    pm08_7.png
     この印字結果の行番号2では,xの値(網掛けの部分)が解である2から遠ざかってしまっている。その原因を調べるため,f を求める式に実際の数値を当てはめて,
    pm08_8.png
    として,(A)の部分の中間結果を印字するプログラムを作り,同じ処理系で実行した。印字結果は-16.00000であり,正確な値-15.99999999999999999999と有効数字7けたで一致した。しかし,行番号1で印字された f の値は,正確な値である10-20(印字の表記では1.000000(-20))とは異なっている。
     これらのことから判断して,(A)の部分では演算の過程でeが徐々に累積し,(A)の計算結果に16.0を加算するときに,けた落ちが発生したと考えられる。
a に関する解答群
  • x6=x7である
  • x6≠x7である
  • x6=x7ともx6≠x7ともいえない
b に関する解答群
  • b[k-1] ← (k-1)×a[k]
  • b[k-1] ← k×a[k]
  • b[k] ← k×a[k+1]
  • b[k] ← (k+1)×a[k+1]
c,d に関する解答群
  • b[k-1]
  • b[k]
  • b[k+1]
  • b[n-1]
  • b[n-1]×x
  • b[n-1]×x+b[n-2]
e に関する解答群
  • けたあふれ
  • けた落ち
  • 指数下位けたあふれ
  • 丸め誤差
解答選択欄
  • a:
  • b:
  • c:
  • d:
  • e:
  • a=
  • b=
  • c=
  • d=
  • e=

解説

この設問の解説はまだありません。

Pagetop