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.

I look forward to your kind regards.I appreciate your reply.

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 appreciate your reply.

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

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

Popular Questions

339 Understanding the Meaning of mpm prefork Settings

353 I have saved several codes written in python to a visual studio file.

340 Memory layouts learned in theory don't work out as expected when actually printed as addresses.

356 I want to create an array of sequences from "1" to a specified number.

© 2023 OneMinuteCode. All rights reserved.