応用数学 (全39問中19問目)

No.19

長さn の文字列C1C2…Cnの中に,部分文字列は全部で幾つあるかを表す式はどれか。ここで,空文字列(長さ 0 の文字列)とC1C2…Cn自身も部分文字列とみなす。例えば,長さ3の文字列C1C2C3の中に,部分文字列はC1,C2,C3,C1C2,C2C3,C1C2C3及び空文字列の7個がある。

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

解説

論理的に計算式で求める方法はわからないのですが、私の解いた方法はこうです。

長さが1の文字列は、部分文字列が 2つ(自分自身と空文字)、
長さが2の文字列は、部分文字列が 4つです。(仮に2文字をABとすると、空文字・"A","B","AB"の4種類)

選択肢であたえられている計算式に、この1と2を代入して正しい値となるかを、検算して答えを求めます。
  • n=1 ⇒ 1, n=2 ⇒ 3
  • n=2 ⇒ 1, 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」となります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop