时间戳

首页 > 解决方案 > 最小步数可被 1 或 2 整除，但可被给定数整除

python-3.x - 最小步数可被 1 或 2 整除，但可被给定数整除

问题描述

我正在开发一个 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.

标签： python-3.x

解决方案

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

推荐阅读