こんな採用クイズがあったのでpython初心者なりにやってみました。
import functools
def main():
fibo =getFibonacci()
fibo.reverse()
count = 0
for i in range(len(fibo) - 1):
list = [fibo[i]]
count = getMillion(fibo, list, fibo[i], i, count)
print('Number of fibonacci combination is ', count)
def getMillion(fibo, list, now, i, count):
new = now + fibo[i]
list += [fibo[i]]
if new < 1000000:
return getMillion(fibo, list, new, i, count)
else:
if new == 1000000:
print(list, ' = ', functools.reduce(lambda x, y: x + y, list))
count += 1
i += 1
list = list[:-1]
if i < len(fibo):
return getMillion(fibo, list, now, i, count)
else:
return count
def getFibonacci():
return list(filter(lambda x: 2 <= x <= 1000000, functools.reduce(lambda x,y: x+[x[-1]+x[-2],], range(30), [0,1])));
if __name__ == '__main__':
main()
ザ・再帰。
フィボナッチ数の取得処理は検索して持ってきました。
書いている途中から嫌な予感がしていましたが、実行するとこうなりました。
[832040, 121393, 46368, 144, 55] = 1000000
[832040, 121393, 46368, 144, 34, 21] = 1000000
[832040, 121393, 46368, 144, 34, 13, 8] = 1000000
[832040, 121393, 46368, 144, 34, 13, 5, 3] = 1000000
[514229, 317811, 121393, 46368, 144, 55] = 1000000
[514229, 317811, 121393, 46368, 144, 34, 21] = 1000000
[514229, 317811, 121393, 46368, 144, 34, 13, 8] = 1000000
[514229, 317811, 121393, 46368, 144, 34, 13, 5, 3] = 1000000
[317811, 317811, 317811, 46368, 144, 55] = 1000000
[317811, 317811, 317811, 46368, 144, 34, 21] = 1000000
[317811, 317811, 317811, 46368, 144, 34, 13, 8] = 1000000
[317811, 317811, 317811, 46368, 144, 34, 13, 5, 3] = 1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 55] = 1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 34, 21] = 1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 34, 13, 8] = 1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 34, 13, 5, 3] = 1000000
(中略)
Traceback (most recent call last):
File "/Users/Tono/Library/Application Support/IntelliJIdea13/python/helpers/pydev/pydevd.py", line 1004, in trace_dispatch
return additionalInfo.CreateDbFrame((self, filename, additionalInfo, t, frame)).trace_dispatch(frame, event, arg)
RuntimeError: maximum recursion depth exceeded
ですよねー。
というわけでロジック変更。
数が小さくなればなるほど同じ数の組み合わせが増えるため、再帰が限界を超えてしまいます。
ロジックを組み直し、フィボナッチ×数の辞書で値を保持するようにしました。
import functools
def main():
fibo =getFibonacci()
fibo.reverse()
count = 0
for i in range(len(fibo) - 1):
map = {fibo[i]:1}
count = getMillion(fibo, map, fibo[i], i, count)
print('Number of fibonacci combination is ', count)
def getMillion(fibo, map, now, i, count):
new = now
while new < 1000000:
new += fibo[i]
map[fibo[i]] = map[fibo[i]] + 1 if fibo[i] in map else 1
if new == 1000000:
list = sorted(map.items(), key=lambda x: x[0]);
list.reverse()
print(list, ' = ', functools.reduce(lambda x, y: x + (y[0] * y[1]), list, 0))
count += 1
if map[fibo[i]] == 1:
map.pop(fibo[i])
else:
map[fibo[i]] = map[fibo[i]] - 1
new -= fibo[i]
i += 1
if i < len(fibo):
return getMillion(fibo, map, new, i, count)
else:
return count
def getFibonacci():
return list(filter(lambda x: 2 <= x <= 1000000, functools.reduce(lambda x,y: x+[x[-1]+x[-2],], range(30), [0,1])));
if __name__ == '__main__':
main()
[(832040, 1), (121393, 1), (46368, 1), (144, 1), (55, 1)] = 1000000 [(832040, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(832040, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(832040, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (55, 1)] = 1000000 [(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(317811, 3), (46368, 1), (144, 1), (55, 1)] = 1000000 [(317811, 3), (46368, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(317811, 3), (46368, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(317811, 3), (46368, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(196418, 5), (17711, 1), (144, 1), (55, 1)] = 1000000 [(196418, 5), (17711, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(196418, 5), (17711, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(196418, 5), (17711, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(121393, 8), (28657, 1), (144, 1), (55, 1)] = 1000000 [(121393, 8), (28657, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(121393, 8), (28657, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(121393, 8), (28657, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(75025, 13), (17711, 1), (6765, 1), (144, 1), (55, 1)] = 1000000 [(75025, 13), (17711, 1), (6765, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(75025, 13), (17711, 1), (6765, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(75025, 13), (17711, 1), (6765, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (55, 1)] = 1000000 [(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (55, 1)] = 1000000 [(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (34, 1), (21, 1)] = 1000000 [(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(17711, 56), (6765, 1), (987, 1), (377, 1), (55, 1)] = 1000000 [(17711, 56), (6765, 1), (987, 1), (377, 1), (34, 1), (21, 1)] = 1000000 [(17711, 56), (6765, 1), (987, 1), (377, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(17711, 56), (6765, 1), (987, 1), (377, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(10946, 91), (2584, 1), (987, 1), (233, 1), (89, 1), (21, 1)] = 1000000 [(10946, 91), (2584, 1), (987, 1), (233, 1), (89, 1), (13, 1), (8, 1)] = 1000000 [(10946, 91), (2584, 1), (987, 1), (233, 1), (89, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(6765, 147), (4181, 1), (987, 1), (377, 1)] = 1000000 [(6765, 147), (4181, 1), (987, 1), (233, 1), (144, 1)] = 1000000 [(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (55, 1)] = 1000000 [(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (34, 1), (21, 1)] = 1000000 [(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (34, 1), (13, 1), (8, 1)] = 1000000 [(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (34, 1), (13, 1), (5, 1), (3, 1)] = 1000000 [(4181, 239), (610, 1), (89, 1), (34, 1), (8, 1)] = 1000000 [(4181, 239), (610, 1), (89, 1), (34, 1), (5, 1), (3, 1)] = 1000000 [(2584, 386), (1597, 1), (610, 1), (233, 1), (89, 1), (34, 1), (13, 1)] = 1000000 [(2584, 386), (1597, 1), (610, 1), (233, 1), (89, 1), (34, 1), (8, 1), (5, 1)] = 1000000 [(2584, 386), (1597, 1), (610, 1), (233, 1), (89, 1), (34, 1), (8, 1), (3, 1), (2, 1)] = 1000000 [(1597, 626), (233, 1), (34, 1), (8, 1), (3, 1)] = 1000000 [(610, 1639), (144, 1), (55, 1), (8, 1), (3, 1)] = 1000000 [(377, 2652), (144, 1), (34, 1), (13, 1), (5, 1)] = 1000000 [(377, 2652), (144, 1), (34, 1), (13, 1), (3, 1), (2, 1)] = 1000000 [(55, 18181), (34, 1), (8, 1), (3, 1)] = 1000000 [(34, 29411), (21, 1), (5, 1)] = 1000000 [(34, 29411), (21, 1), (3, 1), (2, 1)] = 1000000 [(8, 125000)] = 1000000 [(8, 124999), (5, 1), (3, 1)] = 1000000 [(5, 200000)] = 1000000 [(5, 199999), (3, 1), (2, 1)] = 1000000 Number of fibonacci combination is 61
わーいできたー、と思ったら全然違うことに気づいた。
これ1000000になる組み合わせが見つかったときに一番小さい数だけ分解してるけど、
他の数も分解してかないといけないんだ。
最後の
[(5, 200000)] = 1000000
を
[(5, 199999), (3, 1), (2, 1)] = 1000000
にするのなんか、
[(5, 199998), (3, 2), (2, 2)] = 1000000
[(5, 199997), (3, 3), (2, 3)] = 1000000
とえんえん分割していけるじゃない。
こりゃロジック考え直しだー、といったところで眠いので切り上げ。
続きやるかどうかはやる気次第。
コメント