思考:N级楼梯,每次只能跨1或2级,走完这楼梯共有多少种走法?

上一章《python递归与迭代:N级楼梯,每次只能跨1或2级,共有几种走法?》,我使用了数学递推法来解题,并通过python使用递归算法、迭代算法来计算解题。今天,我将跟大家一起探讨和使用数学中的排列组合方法一起解题。

排列组合知识点复习:

1、在数学中,从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号A(n,m)表示

2、从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示

3、组合数公式:

解题思路:

1、先抽取一个N=3的情况,穷举所有走法进行观察。用队列list把每次跨过的阶梯数记录下来,跨1级记录为数值1,跨2级记录为数值2。

N=3级楼梯走法:

1、如每次走1级,则 list=[1,1,1]

2、如第1次走2级,第2次走1级,则 list=[2,1]

3、如第1次走1级,第2次走2级,则 list=[2,1]

上述过程中有3个不同 list,所以3级楼梯走法共有 3 种

2、从上述步骤1中,可以看出,有多少个list,就有多少种走法,记为F(N)

3、再抽取一个N=5的情况,穷举所有走法进行观察,记录数值2的元素个数x 和 list长度(即list中元素的数量)关系,确定x的取值范围。

N=5级楼梯走法:

1、list=[1,1,1,1,1], 数值2的元素个数x=0,list长度=N=5

2、list=[2,1,1,1], 数值2的元素个数x=1,list长度=N-x=5-1=4

3、list=[1,2,1,1], 数值2的元素个数x=1,list长度=N-x=5-1=4

4、list=[1,1,2,1], 数值2的元素个数x=1,list长度=N-x=5-1=4

5、list=[1,1,1,2], 数值2的元素个数x=1,list长度=N-x=5-1=4

6、list=[2,2,1], 数值2的元素个数x=2,list长度=N-x=5-2=3

7、list=[2,1,2], 数值2的元素个数x=2,list长度=N-x=5-2=3

8、list=[1,2,2], 数值2的元素个数x=2,list长度=N-x=5-2=3

上述过程中,x取值范围为:0<=x<=k=int(N/2)=int(5/2)=2,即0<=x<=2,list长度=N-x

4、通过观察上述步骤3发现:

(1)、N级楼梯,元素数值全为1的list长度为N,每多1个数值为2的元素,list长度就减1.如果list中有x个数值为2的元素,则list长度为N-x。

(2)、当数值2的元素个数为x个时,那么 list 数量相当于从N-x个数值全为1的元素中抽取x个元素将其元素值变为2的方法有几种。list长度=N-x 的队列 list 共有 C(N-x,x) 个。

(3)、当list中的数值为1的元素个数=0或1时,x存在最大值k(k=N/2,然后k向下取整),记为 k=int(N/2),0<=x<=k。

5、把上述过程中,累加x从0到k赋值计算出来的list数量,就是F(N)。

如上述中,N=5级楼梯走法:

x取值范围为:0<=x<=k=int(N/2)=int(5/2)=2,即0<=x<=2,list长度=N-x

(1) 当 x=0时,即list长度=5的 list 数量为:C(N-x,x)=C(5-0,0)=C(5,0)=1

(2) 当 x=1时,即list长度=4的 list 数量为:C(N-x,x)=C(5-1,1)=C(4,1)=4

(3) 当 x=2时,即list长度=3的 list 数量为:C(N-x,x)=C(5-2,2)=C(3,2)=3

所以,F(N)=F(5)=C(5,0) C(4,1) C(3,2)=1 4 3=8

综上,通过研究跨2步的次数为x(0<=x<=k)的组合数,其中k=int(N/2),就可以得出走法F(N)的值,即:

F(N)=C(N-x,x=0) C(N-x,x=1) ... C(N-x,x=k)

=C(N,0) C(N-1,1) ... C(N-k,k)

=

结果验证:

当N=1时,0<=x<=int(N/2)=0, F(N=1)=C(N=1,0)=C(1,0)=1

当N=2时,0<=x<=int(N/2)=1, F(N=2)=C(N-x,x=0) C(N-x,x=1)=C(2,0) C(1,1)=1 1=2

当N=3时,0<=x<=int(N/2)=1, F(N=3)=C(N-x,x=0) C(N-x,x=1)=C(3,0) C(2,1)=1 2=3

当N=4时,0<=x<=int(N/2)=2, F(N=4)=C(N-x,x=0) C(N-x,x=1) C(N-x,x=2)=C(4,0) C(3,1) C(2,2)=1 3 1=5

当N=5时,0<=x<=int(N/2)=2, F(N=5)=C(N-x,x=0) C(N-x,x=1) C(N-x,x=2)=C(5,0) C(4,1) C(3,2)=1 4 3=8

当N=6时,0<=x<=int(N/2)=3, F(N=6)=C(N-x,x=0) C(N-x,x=1) C(N-x,x=2) C(N-x,x=3)=C(6,0) C(5,1) C(4,2) C(3,3)=1 5 6 1=13

当N=7时,0<=x<=int(N/2)=3, F(N=7)=C(N-x,x=0) C(N-x,x=1) C(N-x,x=2) C(N-x,x=3)=C(7,0) C(6,1) C(5,2) C(4,3)=1 6 10 4=21

......

python脚本实现如下:

import math import time print('n级楼梯,每次跨1级或2级,有多少种走法') ''' 组合计算: 从n个元素中抽取m个元素,记为C(n,m) ''' def fun_zuhe_jisuan(n, m): result_n = 0 try: if n <= 0 or m < 0 or m > n: result_n = 0 elif m == 0: result_n = 1 else: fenzi = math.factorial(n) # n的阶乘 fenmu = math.factorial(m)*math.factorial(n-m) result_n = fenzi/fenmu except Exception as err: print('组合: 计算从n个数中抽取m个数出来的方法,异常如下: ' str(err)) finally: return result_n ''' 计算N级楼梯走法 ''' def fun_get_fn(n): fn = 0 # n级楼梯走法 try: if n == 1: fn = 1 else: k = int(n/2) # 数值为2元素个数最大值 for i in range(k 1): # 遍历数值为2元素个数数量 fn = fun_zuhe_jisuan(n-i, i) # fn =2级楼梯段为i的组合数 except Exception as err: print('组合方法计算异常:' str(err)) finally: return fn print('3、组合方法') for i in range(1, 30): start_time = time.time() # 开始运行时间 fn = fun_get_fn(i) end_time = time.time() # 运行结束时间 run_time = float(end_time-start_time)*1000 # 计算运行时间,即计算过程耗时(毫秒) print(f'{i}级楼梯,每次跨1级或2级,有{fn}种走法,组合方法耗时:{run_time} 毫秒')

python运行结果:

数学题讲解排列组合:数学排列组合N级楼梯(1)

python数学组合方法计算结果

以上,便是通过数学中排列组合方式进行解题的思路、步骤、和计算结果。

,