# 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 2 months ago, Updated 2 months ago, 4 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 = [1]+[0]*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=[0]*(N+1)#x stairway up (0 xx NN)
ways[0] = ways[1] = 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 + [1])

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 4433
android x 1590
java x 1475
javascript x 1383
c x 903
c++ x 831
ruby-on-rails x 681
php x 678
python3 x 651
html x 631