- トップページ
- 応用情報技術者
- 平成21年度春季問題一覧
- 平成21年度春季問題4-解答・解説-分析
平成21年度春季問題
問題4
長さn の文字列C1C2…Cnの中に、部分文字列は全部で幾つあるかを表す式はどれか。ここで、空文字列(長さ0の文字列)とC1C2…Cn自身も部分文字列とみなす。例えば、長さ3の文字列C1C2C3の中に、部分文字列はC1、C2、C3、C1C2、C2C3、C1C2C3及び空文字列の7個がある。
| ア | 2n-1 |
| イ | n(n+1)/2+1 |
| ウ | n(n-1)+1 |
| エ | n!+1 |
長さn の文字列C1C2…Cnの中に、部分文字列は全部で幾つあるかを表す式はどれか。ここで、空文字列(長さ0の文字列)とC1C2…Cn自身も部分文字列とみなす。例えば、長さ3の文字列C1C2C3の中に、部分文字列はC1、C2、C3、C1C2、C2C3、C1C2C3及び空文字列の7個がある。
| ア | 2n-1 |
| イ | n(n+1)/2+1 |
| ウ | n(n-1)+1 |
| エ | n!+1 |
解答：イ
＜解説＞
【考え方1】
- n=1,n=2,n=3の場合の部分文字列の個数を考える。
- ア～エの選択肢にn=1,n=2,n=3を代入して演算結果が1と一致するのは(イ)n(n+1)/2+1である。
【考え方2】
- 長さ6の文字列c1c2c3c4c5c6をすべて数え上げると次のようになる。
※部分文字列なので、文字列中の文字を任意に取り出したり、順序を入れ替えたりする可能性はない。
長さ6の部分文字列 ： c1c2c3c4c5c6 ⇒1個 長さ5の部分文字列 ： c1c2c3c4c5，c2c3c4c5c6 ⇒2個 長さ4の部分文字列 ： c1c2c3c4，c2c3c4c5，c3c4c5c6 ⇒3個 長さ3の部分文字列 ： c1c2c3，c2c3c4，c3c4c5，c4c5c6 ⇒4個 長さ2の部分文字列 ： c1c2，c2c3，c3c4，c4c5，c5c6 ⇒5個 長さ1の部分文字列 ： c1，c2，c3，c4，c5，c6 ⇒6個 - 1より、長さnの文字列の長さ1～nの各部分文字列の個数は次のようになる。
長さnの部分文字列 ・・・ 1個 長さn－1の部分文字列 ・・・ 2個 長さn－2の部分文字列 ・・・ 3個 ： 長さ3の部分文字列 ・・・ n－2個 長さ2の部分文字列 ・・・ n－1個 長さ1 の部分文字列 ・・・ n個 - 2よりその総数は、1+2+3+・・・(n－2)+(n－1)+nとなる。
- 等差数列の法則よりn(n+1)/2となる。
- 空文字列(長さ0の文字列)も部分文字列とするので、(イ)n(n+1)/2+1となる。
分類
お問い合わせ
