再帰関数

再帰関数

次のような問題を考えます。

[問題]

整数 k に対して、レベル k の AB文字列 を次のように定義します。

・レベル 0 の AB 文字列は "B" です。

・レベル k の AB 文字列は "A" + (レベル k - 1 の AB 文字列) + "B" + (レベル k - 1 の AB 文字列) + "A" です。

　例 : レベル 2 の ABC 文字列は "A" + "ABBBA" + "B" + "ABBBA" + "A" = "AABBBABABBBAA" となります。

レベル k の AB 文字列の x 文字目 までに "B" が何個あるかを求めてください。

[条件]

・レベル k は、1以上 50以下の整数

・x（何文字目） は、1以上 レベル kのAB文字列の長さ以下の整数

解法・ソースコード

まず レベル k のAB文字列の長さは ２の k 乗 以上になり k ≦ 50 という条件を考慮すると、単純に文字列を生成する方法では処理が終わりません。

そこで 再帰関数 を使った解法を考えてみます。

問題をよく読むと、レベル k の AB文字列は レベル k - 1 の AB文字列によって定義されていることがわかります。

つまり、AB文字列は １つ前のAB文字列 によって再帰的に定義されています。

レベル k の AB文字列の長さを len_s[k]、レベル k の AB文字列に含まれる文字列”B”の個数を cnt_b[k]とします。

このとき、レベル k の AB文字列を表す文字列の先頭から x文字目 に含まれる 文字列”B”の数 は次のように考えることができます。

  • x=1のとき
    0個
  • x=2 ～ len_s[k-1]+1のとき
    ひとつ前の文字列レベルの先頭から、x-1文字列の中に含まれる文字列”B”の個数
  • x=len_s[k-1]+2のとき
    ひとつ前の文字列レベルの文字列”B”の個数+1
  • x=len_s[k-1]+3 ～ 2 * len_s[k-1]+2のとき
    ひとつ前の文字列レベルの先頭から、x-len_s[k-1]-2文字の中に含まれる文字列”B”の個数 + cnt_b[k-1] + 1個
  • x=2*len_s[k-1]+3のとき
    cnt_b[k-1] * 2 + 1個

以上により、レベル k の AB文字列 を レベル k-1 の AB文字列 に関する問題へと帰着することができました。

また、レベル k の AB文字列の長さ(len_s) と 文字列”B”の個数(cnt_b) は以下のように定義できます。

  • レベル k の AB文字列の長さ
    len_s[k] = len_s[k-1] * 2 + 3 　　(len_s[0] = 1)
  • 文字列”B”の個数
    cnt_b[k] = cnt_b[k-1] * 2 + 1 　　(cnt_b[0] = 1)

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#---------- 入力例 1 ---------
k = 2   # 文字列レベル k 
x = 7   # 何文字目までの "B" をカウントするか
#---------- 入力例 2 ---------

# 再帰関数
def rec(k, x, len_s, cnt_b):
    if k == 0:      # 終了条件
        return 1
    # xに応じて処理分け
    if x == 1:
        return 0
    elif x <= len_s[k - 1] + 1:
        return rec(k - 1, x - 1, len_s, cnt_b)
    elif x == len_s[k - 1] + 2:
        return cnt_b[k - 1] + 1
    elif x <= len_s[k - 1] * 2 + 2:
        return rec(k - 1, x - len_s[k - 1] - 2, len_s, cnt_b) + cnt_b[k - 1] + 1
    else:
        return cnt_b[k - 1] * 2 + 1

len_s = [1] * (k + 1)   # レベルごとの文字列の長さ
cnt_b = [1] * (k + 1)   # レベルごとの文字列"B"の数
for i in range(1, k + 1):
    len_s[i] = len_s[i - 1] * 2 + 3   # ひとつ前のレベル文字列を２倍し３を足したものが文字列数
    cnt_b[i] = cnt_b[i - 1] * 2 + 1   # ひとつ前のレベル文字列を２倍し１を足したものが文字列"B"の数

# 再帰的に求める
print(rec(k, x, len_s, cnt_b))

[実行結果]

4

文字列レベル2の文字列は “AABBBABABBBAA” であり、この文字列の先頭から7文字の中に 文字列”B” が 4個 含まれます。