Saw the Stick (Alice In Wonderland) - 三角数

どんな問題？

Saw the Stick
http://www.checkio.org/mission/stick-sawing/

指定の長さの棒を、切った棒の長さが、連続した三角数の数列になるように切断せよ。
このとき切った棒の数ができるだけ多くなるようにすること。

引数は、棒の長さ。1000未満の整数。
戻り値は、三角数の数列を小さい順に並べてリストで返す。答えが無いときは、 [ ] を返す。

例題：

checkio(64) == [15, 21, 28]
checkio(371) == [36, 45, 55, 66, 78, 91]
checkio(225) == [105, 120]
checkio(882) == []

三角数 (Triangular numbers)

そもそも三角数ってなんじゃいな？またもWikipedia先生に聞いてみる。

n番目の三角数を T_n とすると、

三角数 - Wikipedia（日本語版）

1000未満の三角数はこれだけ。

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990

どうやって解く？

まず、n番目の三角数を求める関数を書く。

def t(n):
    return n * (n + 1) // 2

あとは、いろんなパターンの数列を作成して、条件に一致するものを探すだけ。

まとめ

def t(n):
    """ Returns triangular numbers
    """
    return n * (n + 1) // 2

MAX_START = MAX_COUNT = 100

def checkio(number):
    for start in range(1, MAX_START):  # 数列の開始インデックス
        for count in range(1, MAX_COUNT):  # 数列の長さ
            series = [t(n) for n in range(start, start + count)]
            total = sum(series)
            if total == number:
                return series
            elif total > number:
                break
    return []

http://www.checkio.org/mission/stick-sawing/publications/natsuki/python-3/first/

公開したものの、見直してみると、やっぱり MAX_START、MAX_COUNTを100に決め打ちしているのが、いまいちだなぁ。今回は 0＜number＜1000という条件があるとはいえ、あまりスマートな方法ではない。number=1 のときに100回もループをするのは無駄だ。

では、startの上限はどうやって求めればいいかな。少なくともstartがnumberを超えることはないのだから、

for start in range(1, number + 1):
    ～

としておくか。ついでに、startとcountのループを、startとendのループにして、書き直してみた。

まとめ2

def t(n):
    """ Returns triangular numbers
    """
    return n * (n + 1) // 2

def checkio(number):
    for start in range(1, number + 1):
        for end in range(start, number + 1):
            series = [t(n) for n in range(start, end + 1)]
            total = sum(series)
            if total == number:
                return series
            elif total > number:
                break
    return []

うーん、なんかこれもしっくりこない。

他の人の答え

http://www.checkio.org/mission/stick-sawing/publications/bryukh/python-3/dumbstraight/
T_nのリストを作成するときは、n*(n+1)//2 で計算するより、 T_n-1+n で連続して求める方が速いし、indexの上限値も同時にわかる。また、ループ内で数列を計算するより、あからじめTnのリストを作っておいて、必要な部分をスライスで取り出しているのも効率的。

別の人の答えでは、startの上限を int(number ** 0.5) としている人もいた。T_n-1+T_n=n² から求めているのかな。

summer_tree_home

Check iOでPython3をマスターするぜっ