フィボナッチとはじめてのPython

部屋を整理していたら学生時代の基礎的なプログラミング授業のレポートが出てきました。おもしろかったのと採点した方に受けたのを思い出したので書き直して記事にしてみます。

元はCの授業でしたが、よい機会なので書いたことのないPythonでやってみます。なのでこの記事では算数の話をしながら、遊びで「はじめてのPython」をします。

レポートは複数の問題から適当に選んで解答するスタイルでしたが、ここでは次の問題を扱います。

自然数nを2以上の数の和で表示する方法を全て記述せよ。和の順序が異なれば別の和とする。表示の数はいくつになるか？
Hint: n=6のとき2+2+2, 2+4, 3+3, 4+2, 6の5通り。最初の数が2か2より大きいかで分ける。最初の数が2の場合、その2を引くとn=4の表し方となる。最初の数が2より大きい場合はその数から1を引くとn=5の表し方となる。結果として表し方の総数はフィボナッチ数F(n-1)となる。

自然数nを奇数の和で表示する方法を全て記述せよ。いくつになるか？

Hintが書いてあると誘導されますね。改めて問題を見ると、プログラミングに慣れてたらHint無視してやってしまいそうですが、そのあたりも考えていきます。

それはそうとHintがわりとむずかしいです。n=6の表し方のうち2+2+2, 2+4から最初の2を引くと、2+2, 4となりこれはn=4の表し方である。3+3, 4+2, 6の最初の数から1を引くと、2+3, 3+2, 5となり、n=5の表し方である、と言ってます。

このHintから、一般的にnの表し方のうち最初の数が2のものとn-2の表し方は1対1に対応していることに気づくのが大事です。

1対1の証明はこのように考えます。n-2の表し方の前に「2+」を加えるとnの表し方で最初の数が2のものを作ることができて、かつすべて異なります。逆にnの表し方で最初の数が2のものから「2+」を引くと、n-2の表し方が作れて、すべて異なります。よって1対1に対応することがわかるのです。

最初の数が2より大きい場合も同様に考えて、nの表し方のうち最初の数が2より大きいものとn-1の表し方が1対1で対応していることが説明できます。

nを2以上の数の和で表す表示の数をtwoのTでT(n)とします。この中で最初の数が2の場合の数をT2(n)とすると、さきほどの議論から、T2(n) = T(n-2)とわかります。同様に最初の数が2より大きい場合の数をT3(n)とすると、T3(n) = T(n-1)です。よってT(n) = T2(n) + T3(n) = T(n-2) + T(n-1)とわかり、フィボナッチ数列の漸化式が出てきました。

フィボナッチ数列はF(0) = 0、F(1) = 1という初期条件ですが、nを2以上の数の和で表す表示の数はT(1) = 0、T(2) = 1という初期条件になるので、T(n) = F(n-1)であることがわかります。つまり2、3、4、5、6、7を2以上の数の和で表す表示の数はそれぞれ、1、1、2、3、5、8通りになるはずです。

ではプログラムを書いてみます。

とりあえずPythonをちょっと勉強しました。ゼロから作るDeep Learningがあったので、1章のPython入門に目を通しました。

学んだこととしては、[1,2,3]みたいにデータをまとめるリストの使い方。if、for、関数定義のdef、classなどの行末に:をつけること。Pythonではインデントに意味があること、などです。あとは困ったらネット検索で。

Hintの通りプログラムを書くと、このようになりました。code#1

def func(num):
    if num < 2:
        return []
    if num == 2:
        return [[2]]
    list1 = func(num-1)
    for i in list1:
        i[-1] += 1
    list2 = func(num-2)
    for i in list2:
        i += [2]
    return list1 + list2

while True:
    print("input:", end="")
    num = int(input())
    result = func(num)
    print(result)
    print(len(result))

func(num)という関数は、numを2以上の数の和で表示する方法を、リストのリストとして返します。最後にlen関数を使って何通りあるかも出力します。6、7を入力してみた結果がこちらです。結果が正しく出ていますね。

input:6
[[6], [2, 4], [3, 3], [4, 2], [2, 2, 2]]
5
input:7
[[7], [2, 5], [3, 4], [4, 3], [2, 2, 3], [5, 2], [2, 3, 2], [3, 2, 2]]
8

ところでHintがなくても、普通に2以上の数を引いていくだけのプログラムを書けますよね。どのように書けばよいでしょうか？

このように書いてみました。2以上の数をnumが0になるまで引いていくというアプローチです。funcの最初の引数num_leftは数字を引いた残り、2番目のxs_tempはここまで引いてきた2以上の数のリスト、num_leftが0になったらnumを2以上の数の和で表せたことになるので、result_tempに追加していきます。code#2

def func(num_left, xs_temp, result_temp):
    if num_left == 0 and xs_temp:
        result_temp += [xs_temp]
    else:
        x = 2
        while x <= num_left:
            xs = xs_temp + [x]
            func(num_left - x, xs, result_temp)
            x += 1

while True:
    print("input:", end="")
    num = int(input())
    result = []
    func(num, [], result)
    print(result)
    print(len(result))

6、7を入力してみた結果です。正しい結果が出ていますね。

input:6
[[2, 2, 2], [2, 4], [3, 3], [4, 2], [6]]
5
input:7
[[2, 2, 3], [2, 3, 2], [2, 5], [3, 2, 2], [3, 4], [4, 3], [5, 2], [7]]
8

ところで次の図を見てください。Hintにしたがってn=2の場合から順に2以上の数の和で表示する方法を生成するとこのような絵が描けますね。赤線は最初の数に1を加える。緑線は最初に「2+」を加えることを表しています。赤は1進む、緑は2進むという風に解釈できないでしょうか？

つまりこの図から、6を2以上の数の和で表す表し方は、6-2=4の長さを、1進むか2進むか選びながらの進み方と対応していることがわかります。よってnを1と2の和で表す表し方の数をI(n)とすると、T(n) = F(n-1) = I(n-2)ということがわかりました。

2以上の数の和で表すことと、1と2の和で表すことは、もっとシンプルにつながっていそうです。。。

よく考えたら、2以上の数は2+1+1+...と表せる数なのです。

というわけで、遠回りですが一旦n-2を1と2の和で表し、それを元に2以上の数の和を作るコードも練習で書いてみましょう。code#3

def func(num_left, xs_temp, result_temp):
    if num_left == 0 and xs_temp:
        result_temp += [xs_temp]
    else:
        for i in [1,2]:
            if num_left >= i:
                xs = xs_temp + [i]
                func(num_left - i, xs, result_temp)

while True:
    print("input:", end="")
    num = int(input())
    result = []
    func(num-2, [], result)
    result2 = []
    for xs in result:
        xs2 = [2]
        for i in xs:
            if i == 1:
                xs2[-1] += 1
            else:
                xs2 += [2]
        result2 += [xs2]
    print(result)
    print(result2)
    print(len(result))

6、7を入力してみた結果です。できていますね。

input:6
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
[[6], [4, 2], [3, 3], [2, 4], [2, 2, 2]]
5
input:7
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [2, 2, 1]]
[[7], [5, 2], [4, 3], [3, 4], [3, 2, 2], [2, 5], [2, 3, 2], [2, 2, 3]]
8

ていうか改めてcode#2を見ると2以上の数を作るときに、2からはじめて1ずつ足して作ってたんですよね。

さて、2問目の自然数nを奇数の和で表示する方法ですが、Hint使わずにnumが0になるまで奇数を引いていくというアプローチで書いてみましょう。code#4

def func(num_left, xs_temp, result_temp):
    if num_left == 0 and xs_temp:
        result_temp += [xs_temp]
    else:
        x = 1
        while x <= num_left:
            xs = xs_temp + [x]
            func(num_left - x, xs, result_temp)
            x += 2

while True:
    print("input:", end="")
    num = int(input())
    result = []
    func(num, [], result)
    print(result)
    print(len(result))

これはcode#2の1と2を逆にしただけではないですか？

そうです。奇数というのは1+2+2+...と表せる数なのです。

4、5、6を入力してみた結果です。ちゃんとできていますね。

input:4
[[1, 1, 1, 1], [1, 3], [3, 1]]
3
input:5
[[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [3, 1, 1], [5]]
5
input:6
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 3], [1, 1, 3, 1], [1, 3, 1, 1], [1, 5], [3, 1, 1, 1], [3, 3], [5, 1]]
8

ここまでの議論によりnを奇数の和で表す方法は、n-1を1と2の和で表す表し方と対応することがわかりました。よってnを奇数の和で表す表示の数をodd numberのOでO(n)とすると、nを2以上の数の和で表す方法の数、フィボナッチ数、nを1と2の和で表す方法の数、nを奇数の和で表す方法の数の関係はT(n) = F(n-1) = I(n-2) = O(n-1)となるのです。

続・フィボナッチとはじめてのPythonへつづく。