Python3で実装問題解決力を鍛える！アルゴリズムとデータ構造【第４章】設計技法(2)：再帰と分割統治法

「問題解決力を鍛える！アルゴリズムとデータ構造」の章末問題をPython3で実装していくシリーズ。

大枠まとめ記事は、ここに。 blacktanktop.hatenablog.com

前回の記事は、【第３章】設計技法(1)：全探索 blacktanktop.hatenablog.com

今回は【第４章】設計技法(2)：再帰と分割統治法について扱う

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

内容
【第４章】設計技法(2)：再帰と分割統治法の概要
章末問題
まとめ
終わりに

内容

Python3でやっている。
簡単に自分の理解を整理する用。
そこまで厳密ではない可能性が高い。
記事を書いたら、書評の方に記事を載せていく。
コード等はGitHubにおいた。 github.com

【第４章】設計技法(2)：再帰と分割統治法の概要

ここの章で再帰の考え方。図4.1の概念図がわかりやすくて、最初の流れは、 f(x) = x + f(x-1)でf(0) = 0とすると、
f(5) → f(4)を呼び出し → f(3)を呼び出し → f(2)を呼び出し → f(1)を呼び出し → f(0)を呼び出す。
次の流れは値の返り方で、 f(x) = x + f(x-1)がf(0)から逆流していく感じ
f(0) = 0なので、f(5)は
0 → 1 + 0 → 2 + 1 → 3 + 3 → 4 + 6 → 5 + 10 となり、15が返り値となる。

再帰関数のポイント
ベースケース（再帰の呼び出しを行わないでreturnするケースのこと）の処理が重要。

テンプレート的にはこんなイメージ

# 再帰関数のテンプレート
def recursive(引数):
        if 条件文:
            return 値
    return recursive(次の引数)

注意点は、再起呼び出しを行った時の引数はベースケースになるように（近づくように）設計しないと、無限ループになる。

章末問題

4.1 Tribonacci sequenceを再帰で計算する

入力は0以上の整数値を想定して、以下のコードのtribo_rec()が問題の意図している再帰関数を使った方法。
確認用のためにtribo_list()は配列とfor文を使った方法も書いておいた。 * テンプレート通りに、初期値の３つをベースケースとする。 * 再起呼び出しは、引数の手前の３つを使う(nに対して、n-1, n-2, n-3)

def main():
    def tribo_list(n):
        d = [0] * (n+1)
        # d[0]とd[1]とd[2]を規定。
        d[0] = 0
        d[1] = 0
        d[2] = 1
        # 3~nまでを見る必要がある
        for i in range(3, n+1):
            d[i] = d[i-1] + d[i-2] + d[i-3]
        return d
    def tribo_rec(n):
        if n == 0:
            return 0
        elif n == 1:
            return 0
        elif n == 2:
            return 1
        ans = tribo_rec(n-1) + tribo_rec(n-2) + tribo_rec(n-3)
        return ans
    print('0以上の整数を標準入力するとTribonacci sequenceを出力する')
    n = int(input())
    if n >= 0:
        print('Tribonacci list', tribo_list(n))
        # [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,
        #  274, 504, 927, 1705, 3136, 5768, 10609, 19513,
        #  35890, 66012, 121415, 223317, 410744, 755476]
        # 項数は0から始まる
        print('再帰によるTribonacci sequenceの第', n, '項の計算の値：', tribo_rec(n), sep='')
        # 755476
    else:
        print('0以上の整数を標準入力するとTribonacci sequenceを出力する')
    
if __name__ == '__main__':
    main()

4.2 再帰関数のメモ化

入力は0以上の整数値を想定して、 4.1を少し変形する。tribo_memo()が意図した再帰関数。

この部分がポイントで、

# メモ作成
memo = [-1] * (n+1)
…
# 再計算をしないように、メモにあるならメモ使う
if memo[n] != -1:
    return memo[n]
memo[n] = tribo_memo(n-1) + tribo_memo(n-2) + tribo_memo(n-3)
return memo[n]

メモ化できるようにリストを作る。
すでに計算した値があれば、メモを利用するようにする。(ここが再計算を減らすポイント)
- メモの全ての初期値は-1なので-1じゃなかったらその値を使う。
メモ化のリストに再起した値を入れる。

def main():
    def tribo_list(n):
        d = [0] * (n+1)
        # d[0]とd[1]とd[2]を規定。
        d[0] = 0
        d[1] = 0
        d[2] = 1
        # 3~nまでを見る必要がある
        for i in range(3, n+1):
            d[i] = d[i-1] + d[i-2] + d[i-3]
        return d
    def tribo_memo(n):
        memo = [-1] * (n+1)
        if n == 0:
            return 0
        elif n == 1:
            return 0
        elif n == 2:
            return 1
        if memo[n] != -1:
            return memo[n]
        memo[n] = tribo_memo(n-1) + tribo_memo(n-2) + tribo_memo(n-3)
        return memo[n] 
    print('0以上の整数を標準入力するとTribonacci sequenceを出力する')
    n = int(input())
    if n >= 0:
        print('Tribonacci sequence', tribo_list(n))
        # [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,
        #  274, 504, 927, 1705, 3136, 5768, 10609, 19513,
        #  35890, 66012, 121415, 223317, 410744, 755476]
        # 項数は0から始まる
        print('メモ化しながら再帰によるTribonacci sequenceの第', n, '項の計算の値：', tribo_memo(n), sep='')
        # 755476
    else:
        print('0以上の整数を標準入力するとTribonacci sequence出力する')
if __name__ == '__main__':
    main()

4.3 Fibonacci sequenceの一般項

フィボナッチ数列は三項間漸化式なので，特性方程式を用いて一般項を求めることができる。
ビネの公式っていうらしい。
漸化式を等比数列に帰着させて解けばいい。

漸化式： $a_n=a_{n−1}+a_{n−2}$ を $a1=a2=1$ の元で解く。

特性方程式は漸化式より、 $x^2=x+1$ である。

$x^2=x+1$ の解を $α=\frac{1+\sqrt{5}}{2}, β=\frac{1-\sqrt{5}}{2}$ とおく。

$α+β=1, αβ=−1$ であるので、

$a_n=(α+β)a_{n−1}+(αβ)a_{n−2}$

上記の式を変形すると、 $a_n - αa_{n-1} = β(a_{n−1} -αa_{n−2})$ となる。

よって、 $a_n - αa_{n -1}$ は公比 β の等比数列である。

以下の式から $a_{n-1}$ を消して、 $a_{n}$ について解く。

$a_n - αa_{n -1}$ = $β^{n−2}(a_2−αa_1)=β^{n−1}$

$a_n - βa_{n -1}$ = $α^{n−2}(a_2−βa_1)=α^{n−1}$

$a_n=\frac{α^n−β^n}{α−β}=$ ${\displaystyle\frac{1}{\sqrt{5}}\{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n\}}$

pythonにはSymPyというsolverモジュールがあるので、今回これを使って、漸化式の一般項を求めてみた。
(動かす場合はSymPyをインストールする必要あり)
さらに、その一般項を用いて、検算をしてFibonacci sequenceを求めた。

python solution_4_3.py とEnterした後、少し時間がかかる。

import sympy as sym
def main():
    # 一般項f(n)
    fn = sym.simplify("f(n)")
    # 左辺が0になるように漸化式を書く
    y = sym.simplify("f(n)-f(n-1)-f(n-2)")
    # 初期条件
    init = sym.simplify({"f(0)": 0, "f(1)": 1})
    # 初期条件iniの漸化式sをfについて解く
    fib_n = sym.rsolve(y, fn, init)
    print('Fibonacci sequenceの一般項の式は')
    print(fib_n)
    print('------------------------------')
    # -sqrt(5)*(1/2 - sqrt(5)/2)**n/5 + sqrt(5)*(1/2 + sqrt(5)/2)**n/5

    def fib_g(n):
        x = sym.symbols('x', nonnegative=True, integer=True)
        fib = -sym.sqrt(5)*(1/2 - sym.sqrt(5)/2)**n/5 + sym.sqrt(5)*(1/2 + sym.sqrt(5)/2)**n/5
        # fibの式のxにnを代入
        formula = fib.subs(x, n)
        ans = int(sym.simplify(formula))
        print(formula, '=', ans)
        return ans
    print('0以上の整数を標準入力するとFibonacci sequenceの一般項の式と検算結果を出力する')
    n = int(input())
    print('検算結果')  
    print('第', n ,'項までの', 'Fibonacci sequence', [fib_g(n) for n in range(0, n)], sep='')

if __name__ == '__main__':
    main()

4.4 Fibonacci Sequenceの計算量

コードはない。一般項から考えると、
${\displaystyle\frac{1}{\sqrt{5}}\{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n\}}$ は線形和であり、第２項は $n→∞$ とすると0へ収束するので、
$O((\frac{1+\sqrt{5}}{2})^n)$

4.5 753数

適当な正の整数の入力をを想定する。

再帰関数のテンプレートで考える。
ベースラインは入力値を数値化した時の値よりも大きくなったら0を返す。
入力されたものが753数ならcnt=1とする。
再起呼び出しは入力された値に'7', '5', '3'をそれぞれ右側からくっつけたものとして、cntをインクリメントする。
初期値は''(空文字)にしたいけど、intにできなくて止まるので'0'とする。
- Pythonではint('0123')とすると整数の123となる

def main():
    n = int(input())
    m = len(str(n))
    def dfs(A):
        # nよりも大きくなったら0を返す
        if int(A) > n:
            return 0
        # 入力されたものが753数ならcnt=1としていく
        cnt = 1 if all(A.count(c) > 0 for c in '753') else 0
        # 実際に用件を満たすような文字列の出力
        if cnt == 1:
            print(A[1:])
        for i in '753':
            cnt += dfs(A + i)
        return cnt
    print('入力値', n, 'の753数は', dfs('0'))
if __name__ == '__main__':
    main()

4.6 部分和問題をメモ化をつかった再帰関数にする

例題と同じく、こんな入力を想定して、

4 14
3 2 6 5

コメントアウトしたけど、ただの再帰関数を用いたものを用意した。（f_rec()）これを、メモ化していく。ポイントはベースケースのところで

メモリストにある場合はそれを返す。
f_rec()ではそのまま返していた値も、メモリストへ代入する。

def main():
    def f_memo(i, w, A):
        if i == 0:
            if w == 0:
                return True
            else:
                return False
        # すでにメモに計算結果がが合ったらそのメモの値を返す        
        if memo[i][w] != -1:
            # print('メモ利用', 'i=', i, 'w=', w, 'A[i]=', A[i])
            return memo[i][w]
        if f_memo(i-1, w, A):
            memo[i][w] = True
            print('i =', i, 'w =', w, 'A[', i-1, ']=', A[i-1], 'を選ばない')
            return memo[i][w]
        if f_memo(i-1, w-A[i-1], A):
            memo[i][w] = True
            print('i =', i, 'w =', w, 'A[', i-1, ']=', A[i-1], 'を選ぶ')
            return memo[i][w]
        memo[i][w] = False
        return memo[i][w]

    n, w = map(int, input().split())
    a = [int(x) for x in input().split()]
    # 1つのリストの要素数がw, それがn個ある多重リスト
    memo = [[-1]*(w+1) for _ in range(n+1)]
    if f_memo(n, w, a):
        # print(memo)
        print('Yes')
    else:
        # print(memo)
        print('No')
    # # 元のただの再帰関数
    # def f_rec(i, w, A):
    #     if i == 0:
    #         if w == 0:
    #             return True
    #         else:
    #             return False
    #     if f(i-1, w, A):
    #         return True
    #     if f(i-1, w-A[i-1], A):
    #         return True
    #     return False
    # n, w = map(int, input().split())
    # a = [int(x) for x in input().split()]
    # if f(n, w, a):
    #     print('Yes')
    # else:
    #     print('No')

if __name__ == '__main__':
    main()

まとめ

再帰はベースケースの処理が重要。
テンプレートを上手く使う。
メモ化しないと計算量が増えるので基本メモ化する。

終わりに

再帰とは関係ないけど、久しぶりに三項間漸化式における特性方程式を用いて一般項を求めた。
再帰は結構値が返ってこないまま次の処理に回して、後から答えが返ってくるので、イメージがしづらいが今回のケースを通じて理解が深まった。