python分配方案数
2023全国青少年信息素养大赛Python编程挑战赛复赛真题解析
博主推荐
- 所有考级比赛学习相关资料合集【推荐收藏】
1、Python比赛
-
信息素养大赛Python编程挑战赛
-
蓝桥杯python选拔赛真题详解
-
蓝桥杯python省赛真题详解
-
蓝桥杯python国赛真题详解
2、Python考级
-
python等级一级真题解析【电子学会】
-
python等级二级真题解析【电子学会】
-
python等级三级真题解析【电子学会】
-
python等级四级真题解析【电子学会】
一、题目要求
（注：input（）输入函数的括号中不允许添加任何信息）
1、编程实现
有n个人，他们需要分配m元钱(m>= n)，每个人至少分到1元钱，且每个人分到的钱数必须是整数。请问有多少种分配方案?
2、输入输出
输入描述：输入一行两个正款数n，m，用空格间隔。
输出描述：输出分配方案数。
输入样例：
5 10输出样例：
126二、算法分析
- 目标：输入n和m，要得到分配方案数，这是一个较为典型的排列组合问题
- 策略：可以使用数学的排列组合公式进行计算，这题也可以使用动态规划算法来解决
- 首先分析可以得到每个人至少要有一元，也就是剩下的m-n元要分配给n个人，每个人可以拿也可以不拿，拿多少是1到m-n的任意值
- dp定义：dp[[i][j]表示将j元钱分配给前i个人的方案数
- 初始化：当i等于1时，也就是1个人，所有的钱都是他的，也就是dp[1][j] = 1
- 状态转移方程：对于 i > 1，dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]，利用优化后的状态转移避免内层循环
- 便利顺序，由于后面的人和钱会用到前面人和钱的分配方案数，所以从前往后便利
- 最后输出即可
本文作者：小兔子编程 作者首页：小兔子编程-CSDN博客
三、程序编写
n, m = map(int, input().split())
if m < n:print(0)
dp = [[0] * (m + 1) for _ in range(n + 1)]for j in range(1, m + 1):dp[1][j] = 1for i in range(2, n + 1):for j in range(i, m + 1):dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]print(dp[n][m])四、程序说明
- 利用input输入函数从键盘获取输入数据
- 利用int函数将n转换成整数类型
- 利用map讲转换后输入的值映射到相应的变量
- 接着利用列表生成式快速给列表进行初始化0
- 然后给dp数组进行初始化
- 接着实现动态转移方程，方案数的调整
- 最后通过print函数输出即可
五、运行结果
5 10126六、考点分析
难度级别：中等，这题相对而言有一点小难度，难在排列组合和算法使用，具体主要考查如下：
- 学会分析题目，找到解题思路
- 学会动态规划算法知识的应用
- input函数：Python 中 input() 函数接受一个标准输入数据，返回为 string 类型。
- int函数：强制将传入对象转换成整数类型
- map函数：将指定的对象按照指定的函数进行迭代，在这里是将时分秒字符串类型数据按int整数类型数字返回输出（相当于多个变量强制类型转化）
- 学会列表的相关操作：列表声明、取数、遍历等等
- 学会for循环的使用：for循环可以遍历任何有序的项及列表元素等等。
- range函数：rang（a,b），循环的时候是不包括b的，所以我们这个案例中要转变一下，要想包含b，就应该写成range(a,b+1)
- print函数：用于打印输出，最常见的一个函数。
- 充分掌握for循环、列表和动态规划算法的使用
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！
