pythonでリストの比較を行いたい

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする．15段の階段を昇る昇り方は何通りあるか．（京大理系07）
この問題をpythonを使って解きたいのですが、下記のプログラムでは同じパターンの出力がでてしまい、それの解決方法が分かりません。答えは277通りで最後のprint文で277通りと出力させたいです。
リストを保存して比較しようとしてもそれだけのリストを準備することができません。そもそもこのやり方での実現は不可能なのでしょうか。

コード

import random
counter = 0
for i in range(100):#この値を無限に増やす。
　 a = 0
    b = 0
    result = []
    while a < 15:
        r = random.randint(1,2)
        result.append(r)
        if r == 2 and b == r:
            break
        a += r
        if a == 16:
            break
        b = r
    if a == 15:
        counter += 1
        print(result)
print("通り数は" + str(counter) + "通りです。")```python

行動規範の内容に同意します

回答2件

すでに出てきたパターンをすべて保存しておけば、同じパターンの出現を避けることはできます。

python
1import random
2done = set()
3for i in range(100):#この値を無限に増やす。
4    a = 0
5    b = 0
6    result = []
7    while a < 15:
8        r = random.randint(1,2)
9        result.append(r)
10        if r == 2 and b == r:
11            break
12        a += r
13        if a == 16:
14            break
15        b = r
16    if a == 15:
17        result = tuple(result)
18        if result not in done:
19            done.add(result)
20            print(result)
21print("通り数は" + str(len(done)) + "通りです。")

ただ、乱数に頼る方法は、いつまでたっても正しい回答にたどり着けない可能性があるので、基本的には避けるべきです。(ほかに方法がない場合を除く)

一応、別解も示しておきます。

python
1import itertools
2
3def solve(m):
4  return 1 + sum(len(list(itertools.combinations_with_replacement(range(n), r))) for n, r in enumerate(range(m - 2, -1, -3), 2))
5
6print(solve(15))

投稿2022/04/23 21:46

actorbug

総合スコア2224

ベストアンサー

再帰関数を使う意味はありませんでした。改善したコードです。

Python
1def steps(mx):
2    tpl=((),)
3    while True:
4        tpl = tuple(tp+(i,) if sum(tp) < mx else tp
5                    for tp in tpl for i in (1,2) if not(tp and tp[-1]==2==i))
6        tpl = tuple(set(tpl))
7        if all(sum(tp) >= mx for tp in tpl):
8            return tuple(tp for tp in tpl if sum(tp) == mx)
9
10n = 15
11tpl = steps(n)
12print(f'{n}段の登り方は{len(tpl)}通り')
13# 15段の登り方は277通り

元のコードは以下です。
リストではなくタプルを使用し、再帰関数を使用したサンプルコードです。ご参考まで

Python
1def steps(mx, tpl=((),)):
2    tpl = tuple(tp+(i,) if sum(tp) < mx else tp
3                for tp in tpl for i in (1,2) if not(tp and tp[-1]==2==i))
4    tpl = tuple(set(tpl))
5    if all(sum(tp) >= mx for tp in tpl):
6        return tuple(tp for tp in tpl if sum(tp) == mx)
7    return steps(mx, tpl)
8
9n = 15
10tpl = steps(n)
11print(f'{n}段の登り方は{len(tpl)}通り')
12# 15段の登り方は277通り