минимальное количество шагов на 1 или 2, но делится на заданное число

Question

Я работаю над программой на Python, в которой я хочу найти минимальное количество шагов, необходимых для достижения верхнего этажа, чтобы число шагов делилось на заданное число, скажем m

Вотмоя программа взята из здесь :

# A program to count the number of ways to reach n'th stair 

# Recurssive program to find n'th fibonacci number 
def fib(n): 
    if n <= 1: 
        return n 
    return fib(n-1) + fib(n-2) 

# returns no. of ways to reach s'th stair 
def countWays(s): 
    return fib(s + 1) 

# Driver program 

s = 10
print("Number of ways = ", countWays(s) )

Здесь я получаю общее количество способов, но я хочу отфильтровать их по тем, которые делятся на данное число, скажем m, каксделать это?

Example:
1) s = 10 and m = 2, output should be 6, as the steps are {2,2,2,2,1,1}

2) s = 3 and m = 5 output should be -1 as the possible steps are {1,1,1}, {2,1}, {1,2}  
--> here none of them (means 3 steps, 2 steps, 2 steps) are divible by 5.

Answer 1

s = 10
m = 2
if s % m == 0:
    print(s)

outputs: 10

Использование% является операцией по модулю. Это обеспечивает «остаток» после деления. Поэтому, если у вашего товара нет остатка, он делится на выбранное число.

# A program to count the number of ways to reach n'th stair 

# Recursive function used by countWays 
def countWaysUtil(n,m): 
    res = [0 for x in range(n)] # Creates list res witth all elements 0 
    res[0],res[1] = 1,1

    for i in range(2,n): 
        j = 1
        while j<=m and j<=i: 
            res[i] = res[i] + res[i-j] 
            j = j + 1 
    return res[n-1] 

# Returns number of ways to reach s'th stair 
def countWays(s,m): 
    return countWaysUtil(s+1, m) 

# Driver Program 
s,m = 4,2
print "Number of ways =",countWays(s,m) 

# Contributed by Harshit Agrawal 

Answer 2

Вы можете использовать это:

# A program to count the number of ways to reach n'th stair 

# Recurssive program to find n'th fibonacci number 
def fib(n): 
    if n <= 1: 
        return n 
    return fib(n-1) + fib(n-2) 

# returns no. of ways to reach s'th stair 
def countWays(s, m): 
    # Add in a division by m, which you pass to the function
    # Cast it as an int to return a whole # and not decimal
    return int(fib(s + 1) / m)

# Driver program 

s = 10
# Set this to whatever
m = 3
print("Number of ways = ", countWays(s, m) )