応用数学 (全55問中35問目)
No.35
長さn の文字列C1C2…Cnの中に，部分文字列は全部で幾つあるかを表す式はどれか。ここで，空文字列(長さ 0 の文字列)とC1C2…Cn自身も部分文字列とみなす。例えば，長さ3の文字列C1C2C3の中に，部分文字列はC1，C2，C3，C1C2，C2C3，C1C2C3及び空文字列の7個がある。
出典：平成21年春期 問4
- 2n－1
- n(n＋1)／2＋1
- n(n－1)＋1
- n!＋1
分類
テクノロジ系 » 基礎理論 » 応用数学
正解
イ
解説
長さが1の文字列は、部分文字列が2つ(自分自身と空文字)、
長さが2の文字列は、部分文字列が4つです。(仮に2文字をABとすると、空文字・"A","B","AB"の4種類)
選択肢であたえられている式に、この1と2を代入して正しい値となるかを、検算して答えを求めます。
※掲示板に論理的にこの問題を解く方法が寄せられたので追記いたします(スレッドNo.154)。
n文字の文字列からn文字の部分文字列のとり方は先頭の文字からの1通り、n-1文字の部分文字列のとり方は2通り、n-2文字の部分文字列のとり方は3通り……、2文字の部分文字列のとり方はn-1通り、1文字の部分文字列のとり方はn通りになります。
これらの合計は初項1、公差1、項数nの等差数列の和なのでn(n+1)/2です。
これに空文字列の1を加えて答えは「n(n+1)/2+1」となります。
長さが2の文字列は、部分文字列が4つです。(仮に2文字をABとすると、空文字・"A","B","AB"の4種類)
選択肢であたえられている式に、この1と2を代入して正しい値となるかを、検算して答えを求めます。
- n=1 ⇒ 1, n=2 ⇒ 3
- n=1 ⇒ 2, n=2 ⇒ 4
- n=1 ⇒ 1, n=2 ⇒ 3
- n=1 ⇒ 2, n=2 ⇒ 3
※掲示板に論理的にこの問題を解く方法が寄せられたので追記いたします(スレッドNo.154)。
n文字の文字列からn文字の部分文字列のとり方は先頭の文字からの1通り、n-1文字の部分文字列のとり方は2通り、n-2文字の部分文字列のとり方は3通り……、2文字の部分文字列のとり方はn-1通り、1文字の部分文字列のとり方はn通りになります。
これらの合計は初項1、公差1、項数nの等差数列の和なのでn(n+1)/2です。
これに空文字列の1を加えて答えは「n(n+1)/2+1」となります。