おーみんだよ。

おーみんだよ。

プログラミング、Unityなどのアウトプットを主に行っています。

応用情報技術者試験 H21年春期 午前 問4 解説

  f:id:bookreadkun:20190131103437p:plain

 

おはようございます。おーみん(@Ooooooomin_365)です。

 

 

所用で応用情報技術者試験を受けることになりました。

 

正直やる気は出ないのですが、受けると決めたからにはしっかり勉強して、ブログ等にアウトプットしていこうと思います。

 

今回勉強したのは基礎理論~確率分野です。

 

その中で気になった問題があったのでここで解説しようと思います。

 

 

応用情報技術者試験 H21年春期 午前 問4

【問題】

長さnの文字列c1c2...cnの中に、部分文字列は全部で幾つあるかを表す式はどれか。ここで、空文字列(長さOの文字列)とc1c2...cn自身も部分文字列とみなす。例えば、長さ3の文字列c1c2c3の中に、部分文字列はc1,c2,c3,c1c2,c2c3,c1c2c3及び空文字列の7個がある。

 

【選択肢】

ア:2^n-1

イ:n(n+1)/2+1

ウ:n(n-1)+1

エ:n!+1

 

解き方は僕が思いつく限りでは2パターン。

 

【解説】解き方その1

nに実際に整数を代入していきましょう。

 

n=1のとき、文字列はc1。

この場合の部分文字列はc1と空文字列の計2つとなります。

 

n=2のとき、文字列はc1c2。

この場合の部分文字列はc1,c2,c1c2と空文字列の計4つとなります。

 

ここで選択肢「イ」以外にn=2を代入しても4にならないことから正解は「イ」であることが分かります。

 

【解説】解き方その2

c1c2...cnの文字列から部分文字列を取り出すとき、部分文字列を一つ取り出すときはc1,c2...cnのn通り。

 

二つ取り出すときはn-1通り。三つ取り出すときはn-2通り。

 

・・・

 

n-1つ取り出すときは2通り。nつ取り出すときは1通りとなります。

 

よって部分文字列の取り出し方は1+2+...+n、そして空文字列の1通りを足したのが答えになります。

 

前者は等差数列の和なのでn(n+1)/2、そして空文字列の1通りを足してn(n+1)/2+1という答え(イ)になります。

 

・・・

 

・・・

 

ちなみに僕は回答欄のn(n+1)/2+1の「+1」部分を前項の分母にかかっている(つまりn(n+1)/3だと解釈)と勘違いして回答欄から弾いていたのはナイショのお話・・・( ;∀;)

 

まあこんなミスするのは単に注意不足なだけで僕が悪いんですが、表記の仕方は何とかならんもんですかねぇ~(笑)

 

・・・

 

よし!続きも頑張ろう!