0

はじめまして、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)段までの上り方の総数の和。

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

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

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

3
  • 4
    同じ分からないでも「論理的に考える部分が分からない」「プログラムに落とし込むところが分からない」「Python の文法が分からない」など複数のケースが考えられますが、どの部分で困っているかをもう少し具体的に説明した方が回答も付きやすいと思います。
    – cubick
    2021年10月1日 6:22
  • 関数定義を禁止されたならば、フィボナッチ数列を配列に確保した上で指定されたnまでの和を求めれば良いと思われます
    – hiropon
    2021年10月1日 8:28
  • 3
    「組み込み関数のみ使用」は標準・外部ライブラリを使ってはいけないというだけで、関数定義自体を禁止しているのではないのではないと思いますが….
    – eduidl
    2021年10月1日 8:34

2 件の回答 2

1

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

実際:関数定義が禁止だから使えない

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

## 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

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

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

1

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

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

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]} 通りです。")

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。