n个学生，求有多少种成绩排名可能 python

一道面试题，参考了两位大佬的文章： https://www.zhihu.com/question/30200444/answer/47183882 https://blog.csdn.net/_FengXingwei/article/details/96619381?utm_source=app

题目要求

有n个学生，对他们的成绩进行排名，允许并列并且视为同一情况，共有多少种排名情况？

思路

已知有i个排名，j个学生，已经排好顺序，新进入1个学生，势必只能插入这个排序，有i+1个位置，可能与某人相等或刚好插入顺序

动态规划

假设dp[i][j] 表示排名可能，其中 i种名次，一共 j名学生，j ≥ i ＞ 1 因此有如下关系：

dp[i][i] = i! #说明大家成绩各不相同 dp[1][j] = 1 #成绩完全相同 dp[i][j] = i*dp[i][j-j] + i*dp[i-1][j-1] #dp[i][j-j]表示新添加的学生与其中一个学生成绩相同，i个排名位置 #dp[i-1][j-1]表示新添加的学生成绩与任何一个都不同，新插入的位置有i个可能

代码

import sys def fact(num):#阶乘 rs = 1 for i in range(1,num+1): rs *= i return rs def grade_sort(n): ''' :param n:学生数量 :return rs : 排名情况 ''' rs = 0; num = n; dp = [[0]*(n+1) for _ in range(n+1)] #初始化 for i in range(1,num+1): #i个名次 for j in range(i,num+1):#j个学生，至少i个学生 if i == j: tmp = fact(i) elif i == 1: tmp = 1; else: tmp = dp[i][j-1]*i + dp[i-1][j-1]*i; dp[i][j] = tmp #sum #只把有n个学生的排名情况统计一下 print(dp) for i in range(1,num+1): rs += dp[i][num] return rs if __name__ == "__main__": n = int(sys.stdin.readline().strip()) rs = grade_sort(n) print(rs)

递归

思路相同，上代码

import sys def fact(num):#阶乘 rs = 1 for i in range(1,num+1): rs *= i return rs def grade_sort_2(i,n): ''' :param i:名次数目 :param n:学生数量 :return rs : 排名情况 ''' if i==n: return fact(n); elif i == 1: return 1; else: rs = i*grade_sort_2(i,n-1) + i*grade_sort_2(i-1,n-1) return rs if __name__ == "__main__": n = int(sys.stdin.readline().strip()) rs = 0 for i in range(1,n+1): #名次数目 rs += grade_sort_2(i,n) print(rs)

PS

上边的博主提到另一个问题： 前提忽略司机和乘务员。有n个人坐车，每辆车可以坐1~n个人，要求所有人都能上车，且所有车都必须上人，车足够，问有多少种乘车方法？

思路

与成绩排名相类似，车的可能性1~n辆，假设i辆车，j名乘客，j≥i 没有找到原题，假设车辆方案与顺序无关 i==j，只有1种情况，一车一人 i == 1时，只有一种情况，整车走人 otherwise，f(i,j) = i*f(i,j-1) + f(i-1,j-1)，乘坐一辆已经有人的车，或者自己再来一辆新车（没乘以i是假设车辆方案与顺序无关）

欢迎讨论