# How many ways are there to go up the n-step stairs when you decide to go up a prime number of steps, such as going up two steps, going up three steps, going up five steps?

Asked 5 months ago, Updated 5 months ago, 21 views

Nice to meet you, I'm a Python beginner.

How many ways to go up the n-step stairs when you decide to go up one, two, three, five, etc.? where n is a natural number less than or equal to 50.

Rule: Use only built-in functions.Use list/tuple/set/dictionary.

Expectation: I thought I could use the Fibonacci sequence.For example, the way 11 steps are raised is the sum of the total number of steps 11-1, (11-2), (11-3), (11-5), (11-7), (11-9) and (11-11).

Actual: Function definition is prohibited and cannot be used
If you think about it logically, you can solve it.

I can't even write a flowchart because I don't know what to put into programming.

python algorithm mathematics

2022-09-30 11:18

Expectation: I thought I could use the Fibonacci sequence.For example, the way 11 steps are raised is the sum of the total number of steps 11-1, (11-2), (11-3), (11-5), (11-7), (11-9) and (11-11).

Actually: Function definition is prohibited, so I can't use it

Put the Fibonacci sequence aside and try to solve it with Dynamic Programming (DP).

``````## prime numbers
max_step, primes=50, [1,2]
for i in range (primes[-1]+1,max_step+1):
for jin 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 prime if <=n]
dp = +*n
for i in range (1, n + 1):
For pin steps:
if(i-p>=0):
dp[i]+=dp[i-p]

sum_steps=dp[n]
print(sum_steps)

#
652
``````

I will not explain the above code.If you are interested in DP, please check it out.

2022-09-30 11:18

As you notice, you can calculate how to climb a certain number of steps from how to climb a smaller number of steps.
Therefore, for the natural number x up to n, you can make a table of the number of stairs up in the x step in order from the smallest to the smallest.

Since the calculation requires a prime number, proceed with a list of prime numbers up to x at the same time.
Start with an empty list of prime numbers and add them if x is a prime number.

``````N=int(input("How many steps are there?"))

Ways=*(N+1)#x stairway up (0 xx NN)
ways = ways = 1
primes = [ ]#i List of prime numbers or less

for i in range(2,N+1):
if not any(i%p==0 for pin primes):
primes.append(i)#i was a prime number
ways[i] = sum (ways[i-p]) for pin primes + )

The print(f"{N} column goes up in {ways[N]} ways.")
``````

2022-09-30 11:18

## If you have any answers or tips

Popular Tags
python x 4628
android x 1593
java x 1493
javascript x 1425
c x 924
c++ x 877
ruby-on-rails x 696
php x 692
python3 x 683
html x 656