组合取球-2022年全国青少年信息素养大赛Python国赛第6题

全国青少年信息素养大赛（原全国青少年电子信息智能创新大赛）是“世界机器人大会青少年机器人设计与信息素养大赛”赛事之一，由中国电子学会主办，包含很多赛项，大赛自2013年举办，已连续成功举办八届，已正式入围“2022-2025学年面向中小学生的全国性竞赛活动名单”。 大赛旨在激发广大青少年的科学兴趣和想象力，培养钻研探究、创新创造的科学精神和实践能力，促进青少年科技创新活动的广泛开展，发现和培养一批具有科研潜质和创新精神的青少年科技创新后备人才。 大赛主要竞赛类别包括电子科技、智能机器人、软件编程三类，全国青少年Python编程挑战赛就属于其中的软件编程类。

一.赛事说明

2021-2022年（第8届）Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛，复赛是地方选拔赛，总决赛是全国各地选拔的精英汇聚在一起进行PK。2021-2022年全国青少年Python编程挑战全国总决赛于2022年8月27日正式举行。一共是10道编程题，每道题100分，满分1000分，考试时间是120分钟。 10道编程题分别如下：

• 分苹果
• 韩信点兵
• 借书问题
• 四位数密码
• 邮票面值
• 取球
• 统计连续字符
• n的n次方
• 海盗搜身
• 父与子

超平老师将分10讲对每道题进行详细的解读和剖析，今天要解读的是第6题，组合取球。

二.题目描述

题目背景： 一个箱子里面存放着50个球，其中10个红色，10个黄色，30个蓝色。 现在从箱子里面任意取n个球，计算并输出不同颜色的球的数量组合一共有多少种可能性。 输入描述： 一个数字n 输出描述： 一个数字，可能的组合总数 样例输入： 2 样例输出： 6 注意： input()内不添加任何参数 只有完全正确才可提交，若无法点击提交说明答题存在错误，可及时进行检查并修改

三.思路分析

粗略一看，这是一个组合问题，但是这不是一个在m个小球中选n个小球的简单组合，而是从3种不同颜色的小球堆中选出n个小球的复杂组合。

针对此类组合问题，通常有两种解决思路，一是使用枚举算法，二是使用组合的方法。组合方法难度相对要大一些，枚举则是更简单的实现方式，这里重点介绍枚举算法的思路。 我们假定红色球选x个，黄色球选y个，蓝色球选z个，根据题目的描述，x、y、z满足如下条件：

x + y + z = n
0 ≤ x ≤ 10  
0 ≤ y ≤ 10   
0 ≤ z ≤ 30

x + y + z = n 就是数学中的三元一次方程式，它有多组解，比如，当n = 2时，可以有如下不同组合：

x = 2 y = 0 z = 0
x = 0 y = 2 z = 0
x = 0 y = 0 z = 2
x = 1 y = 1 z = 0
x = 1 y = 0 z = 1
x = 0 y = 1 z = 1

可以将他们以元组的形式保存到列表中，如下：

[ (2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)]

针对3个变量，我们使用枚举算法，也就是3层循环就可以实现。 接下来，我们进入具体的编程实现环节。

四.编程实现

根据上面的思路分析，我们编写代码如下：

# 获取数字n
n = int(input())
# 枚举算法
result = []
for x in range(10):
  for y in range(10):
    for z in range(30):
      if x + y + z == n and (x,y,z) not in result:
        result.append((x,y,z))
# 输出组合总数
print(len(result))

简单说明两点： 1). 为了避免重复组合，第9行代码做了去重处理； 2). 每一种组合，可以使用元组(x, y , z)来表示，也可以使用列表[x, y, z]来表示； 运行程序，如果输入数字2，可以得到如下组合：

[(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0)]

如果输入数字3，可以得到如下组合：

[(0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2), 
  (1,1,1),(1,2,0),(2,0,1),(2,1,0),(3,0,0)]

五.总结与思考

本题难度中等，考查的知识点主要包括：

• 输入输出函数；
• 循环嵌套语句；
• 列表操作；
• 枚举算法；

善于思考的同学可能已经发现了，题目描述中有一条信息可能会产生干扰作用，这就是“箱子里面存放着50个球”。有些同学在分析思考的时候，会纠结如何在50个小球中取n个小球的问题上。 实际上，50个小球分成了3堆，分别是10个红色球、10个黄色球和30个蓝色球，然后分别从三堆小球中取球，如此一来，就自然而然想到枚举算法了。 如果你熟练掌握了列表推导式的用法，上面的代码，还可以进一步进化，如下：

n = int(input())
result = [(x,y,z) for x in range(10) for y in range(10) for z in range(30)  if x + y + z == n]
print(len(result))

除此之外，还可以itertools库中的product函数来解决，你知道是怎么实现的，赶紧动手试一下吧。