近期帮同学解了一道重邮的Python题目,稍微有点复杂(主要是数学部分),记录于此。

图就不配了,自行脑补(


题目

侯先生每天都会爬楼梯锻炼身体,他有时候一次跨一级,有时候一次跨两级。
有一天侯先生想弄明白一个很难的问题:从最下面的第1级开始到顶端的第n级一共有多少种走法呢?比如n是3时,有两种走法(直接从第1级上跨两步到第3级,或者从第1级跨一步到2级再跨一步到第3级)。
请你帮帮侯先生,给你n (1<n<40)的值,请计算并输出有多少种爬到顶端的方法。

输入n的值,n是1到40之间的整数。
输出一共有多少种从第1级台阶到第n级台阶的走法。
【样例输入】4
【样例输出】3

原题目的用语不规范,没有明确给定侯先生一步最多可以跨多少级。根据题目上下文和示例输入输出可以推测侯先生爬楼梯一步只能跨1或2级。上面的题目已经过修正。

思路1

将台阶看作一个个空位,使用2级尽量填充前面,然后由后至前逐步拆分为1级,拆分出来的1级们又可以组合为2级。遍历并统计所有可能性。

步骤:

  • 首先使用2级填充前面的空位,最后如果余下1个空位(奇数级)就填充1级,否则不填充。记录这种排序方法。
  • 将最后一个2级拆分为两个1级,这时后面就有了2或3个1级。在保证最左边有1个1级用于与2级间隔的情况下,若后面的1级们又可以组成2级,就尽力组成最多的2级,然后循环遍历。每次得到一种排序就比较记录是否已存在,已存在就continue,否则计数++并记录当前的排序方法。
  • 继续拆分,循环遍历……
  • ……

这种方法十分复杂,需要用到递归,使问题复杂化,基本不可行。于是抛弃了此思路。

思路2

同样将台阶看作一个个空位,若空位有x个,那么2级最多能有的数量为num_2_max = x // 2。那么2级的数量可以是[0, num_2_max],即0, 1, 2, ..., num_2_max。

遍历2级可能的数量。对于每个2级的可能性数量num_2的情况:

  • 由总共的台阶数求得对应的1级的数量num_1 = x - num_2 * 2
  • 现在有num_1个1级,num_2个2级,加起来刚好可以走完全部台阶。问题可以转化成对这几个1级和2级的排列问题,求得它们的排列的所有可能性就得到了当前num_2情况下的可能性。
  • 累加当前的可能性。

最后即可得到累加的可能性,为总的可能性。

排列数计算

排列数计算方法为:
image.png

应当注意:所有1级都视为相同的元素(内部顺序不同不会影响结果),因此1级之间不同的顺序不计入结果。2级同理。

由于各种元素内部的顺序不影响结果,我们需要对排列数量进行修正。修正后的排列数量将总的排列数量除以A元素(1级)内部的排列数量和B元素(2级)内部的排列数量来得到。
修正后的排列数为:
image.png

完整的排列组合知识点请看排列组合 - OI Wiki (oi-wiki.org)

代码

import math  

def permutation(x, y):
    """计算修正后的排列数"""
    total_elements = x + y  
    inner_permutation_A = math.factorial(x)  
    inner_permutation_B = math.factorial(y)  
    corrected_permutations = math.factorial(total_elements) / (inner_permutation_A * inner_permutation_B)  
    return int(corrected_permutations)  

n = int(input())  
num_2_max = (n - 1) // 2  
probably_counts = 0  
for num_2 in list(range(num_2_max + 1)):  
    num_1 = (n - 1) - num_2 * 2  
    probably_counts += permutation(num_1, num_2)  
print(probably_counts)