長さnの文字列ｃ1ｃ2･･･ｃnの中に、部分文字列は全部で幾つあるかを表す式はどれか。ここで、空文字列 (長さ0の文字列) とｃ1ｃ2･･･ｃn自身も部分文字列とみなす。例えば、長さ3の文字列ｃ1ｃ2ｃ3の中に、部分文字列はｃ1、 ｃ2、 ｃ3、 ｃ1ｃ2、 ｃ2ｃ3、 ｃ1ｃ2ｃ3及び空文字列の7個がある。
ア 2n−1
イ n(n＋1) ／2＋1
ウ n(n−1) ＋1
エ n! ＋1
イ
n = 1の時: 空文字と、ｃ1 の2個
n = 2の時: 空文字と、ｃ1、 ｃ2、 ｃ1ｃ2の 4個
n = 3の時: 問題より7個
になる選択肢を選べばよい。
ア 21−1 ＝ 1
22−1 ＝ 3
23−1 ＝ 7
イ 1(1＋1) ／2＋1 ＝ 2
2(2＋1) ／2＋1 ＝ 4
3(3＋1) ／2＋1 ＝ 7
ウ 1(1−1) ＋1 ＝ 1
2(2−1) ＋1 ＝ 3
3(3−1) ＋1 ＝ 7
エ 1! ＋1 ＝ 2
2! ＋1 ＝ 3
3! ＋1 ＝ 7
【別解】
n文字の文字列の時、
長さ0の文字、すなわち空文字の個数は1個。
長さ1の文字はn個。
長さ2の文字はn−1個。
長さ3の文字はn−2個。
・・・
長さn−1の文字は2個。
長さnの文字は1個。
したがって、部分文字列は
1＋n＋ (n−1) ＋ (n−2) ＋ ・・・ + 2 ＋ 1
＝ 1＋n(n＋1) ／2
＝ n(n＋1) ／2 ＋1 となる。
| 問３ | 目次 | 問５ |