八街薫の日記
技術士(電気電子、情報工学、総合技術監理)を持つ計測制御系エンジニアです。継続研鑽の一環として資格取得等にチャレンジする様を描きます。
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
平成18年度「コンピュータ工学」Ⅰ-2-1
昨年度の変わり種の出題が気になっていたので、
解いてみた。

問題:
4個の数A,B,C,Dの和を求めるとき、演算の優先順序として、
次の5通りが考えられる。
  ((A+B)+C)+D
  (A+(B+C))+D
  (A+B)+(C+D)
  A+((B+C)+D)
  A+(B+(C+D))
m個の数の和の優先順序がn通りあるとき、f(m)=nと書く
ことにする。上の例の場合はf(4)=5である。
(1)5個の数をA,B,C,D,Eとするとき、上の4個の数の場合に
  ならって、5個の数の和の優先順序を全て示せ。
(2)一般に、
    m-1
  f(m)=Σ f(i)f(m-i),m≧2、
    i=1
  であることを説明せよ。ただし、f(1)=1である。
(3)この式を用いてf(6)の値を求めよ。

答案:
(1)以下の14通りである。
  A+(((B+C)+D)+E)
  A+((B+(C+D))+E)
  A+((B+C)+(D+E))
  A+(B+((C+D)+E))
  A+(B+(C+(D+E)))
  (A+B)+(C+(D+E))
  (A+B)+((C+D)+E)
  (A+(B+C))+(D+E)
  ((A+B)+C)+(D+E)
  (((A+B)+C)+D)+E
  ((A+(B+C))+D)+E
  ((A+B)+(C+D))+E
  (A+((B+C)+D))+E
  (A+(B+(C+D)))+E

(2)m(≧2)の数の和を求める優先順序を全て数え
 上げるに際して、最も優先順位が低い(最後に演算する)
 +の位置により、m-1通りに場合分けができる。

 場合1    1番目の+の優先順位が最も低い場合
  ・
  ・
 場合i    i番目の+の優先順位が最も低い場合
  ・
  ・
 場合m-1  m-1番目の+の優先順位が最も低い場合

 場合iについては、優先順位の最も低い+の左側にi個の
 数があり、右側にはm-i個の数がある。左側のi個の数の
 和の優先順序の決め方はf(i)通り、右側のm-i個の数の
 和の優先順序の決め方はf(m-i)通りあるので、場合iの
 優先順序の決め方はf(i)・f(m-i)通りある。

 したがって、場合1から場合m-1までの全ての優先順位の
 決め方を合計すると、下式を得る。

    m-1
  f(m)=Σ f(i)f(m-i),m≧2、
    i=1

(3)(2)で説明した式を用いると、f(1)=1であるから
  f(2)= f(1)・f(1)=1

     2
  f(3)=Σf(i)f(3-i)
    i=1

    = f(1)・f(2)+f(2)・f(1)
    = 1・1+1・1=2

  f(4)=5(題意より)

  f(5)=14((1)より)

     5
  f(6)=Σf(i)・f(6-i)
    i=1

    = f(1)・f(5)+f(2)・f(4)+f(3)・f(3)
               +f(4)・f(2)+f(5)・f(1)
    =1・14+1・5+2・2+5・1+14・1
    =42 //

ほとんど数学の問題である。f(m)の漸化式が与えられて
いなければ難しいかもしれないが、漸化式が与えられている
ので、比較的簡単である。

さて、この出題の意図は何なのだろう。19年度試験で
求められる「応用能力」のひとつとして、このような
アルゴリズム発見能力があるということか。

いずれにしても、この手の問題は事前に準備できるような
性格の問題ではない。自分には応用力はあると信じて、
知識問題対策に集中するのが得策だろう。
関連記事
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://yachimata.blog102.fc2.com/tb.php/5-7c733e74
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。