

はじめまして、Python初心者です。

1段、2段上がる、3段上がる、5段上がる…というように一段または素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか？
ただし、nは50以下の自然数。

ルール：組み込み関数のみ使用。list/tuple/set/dictionaryを使用。

期待：フィボナッチ数列使えばいけると思った。例えば、11段の上がり方は、（11－1）段、（11－2）、（11－3）、（11－5）、（11－7）、（11－9）、（11－11）段までの上り方の総数の和。

実際：関数定義が禁止だから使えない  
論理的に考えれば解けるらしいので

プログラミングに落とし込むところが分からないのでフローチャートすら書けない状態。

よろしくお願いいたします。回答していただけるだけで有難いです。


CC BY-SA 4.0
2021-10-01T04:45:42.630
82787
2021-10-06T00:36:09.180
2021-10-06T00:36:09.180
2238
48340
question
python アルゴリズム 数学
2段上がる、3段上がる、5段上がる…というように素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか？


>
> 期待：フィボナッチ数列使えばいけると思った。例えば、11段の上がり方は、（11－1）段、（11－2）、（11－3）、（11－5）、（11－7）、（11－9）、（11－11）段までの上り方の総数の和。
>
> 実際：関数定義が禁止だから使えない

一旦、フィボナッチ数列は脇に置いて、DP(Dynamic Programming: 動的計画法)で解いてみます。

[code]

    ## prime numbers
    max_step, primes = 50, [1, 2]
    for i in range(primes[-1]+1, max_step+1):
      for j in primes[1:][:]:
        if i%j == 0: break
        if i < 2*j: primes.append(i); break
    
    #print(primes)
    
    ## sum all steps with DP
    n = 11
    steps = [i for i in primes if i <= n]
    dp = [1] + [0]*n
    for i in range(1, n+1):
      for p in steps:
        if (i-p >= 0):
          dp[i] += dp[i-p]
    
    sum_steps = dp[n]
    print(sum_steps)
    
    #
    652
    
[/code]

> 回答していただけるだけで有難いです。

上記のコードに関して解説はしません。DP に関して興味が湧いてきたのであれば調べてみて下さい。


CC BY-SA 4.0
2021-10-01T09:08:07.773
82795
2021-10-01T09:08:07.773
47127
82787
answer


お気づきのように、ある段数の上り方はそれより少ない段数の上り方から計算できます。  
ですので、 _n_ までの自然数 _x_ について小さい方から順番に、 _x_ 段の階段の上り方の数の表を作っていけばいいでしょう。

計算には素数が必要になりますから、同時に _x_ までの素数のリストを作りながら進めます。  
素数のリストは最初は空で始めて、もし _x_ が素数なら追加していきます。

[code]

    N = int(input("何段の階段ですか: "))
    
    ways = [0] * (N+1)              # x段の階段の上り方 (0≦x≦N)
    ways[0] = ways[1] = 1
    primes = []                     # i以下の素数のリスト
    
    for i in range(2, N+1):
        if not any(i % p == 0 for p in primes):
            primes.append(i)        # iは素数だった
        ways[i] = sum(ways[i-p] for p in primes + [1])
    
    print(f"{N} 段の上り方は {ways[N]} 通りです。")
    
[/code]


CC BY-SA 4.0
2021-10-01T11:08:21.463
82800
2021-10-01T11:08:21.463
9464
82787
answer