2023年蓝桥杯省赛—

2023年蓝桥杯省赛——分糖果

题目链接：12.分糖果 - 蓝桥云课 (lanqiao.cn)

思路

DFS解法

实现思路

代码实现

Java

C++

总结

题目链接：12.分糖果 - 蓝桥云课 (lanqiao.cn)

思路

第一眼是茫然的，第二眼是想枚举的，第三眼是发现要DFS 的，第四眼是不知道怎么开始的，第五眼是崩溃的，第六眼是慢慢摸出来了的，第七眼是报错了的，第八眼是跑不出来的，第九眼是拿下的。

DFS解法

实现思路

这段代码的核心思想是使用深度优先搜索（DFS）来解决问题。这是一个典型的深度优先搜索问题，就是求解给一群小朋友分糖果的方式数量。

一共有7个小朋友，每个小朋友都需要至少2颗糖果，并且不能超过5颗。此外，给出的糖果有两味，一种是 9 颗T9（代码里写的t9）味的，另一种是16颗T16 （代码里写的t16）味的。

首先，我们定义了一个全局变量sum来记录满足条件的分糖果方案数，这样就不用思考那复杂的sum在递归中如何返回了。

进入主函数后，首先调用DFS函数开始搜索，其中的参数分别是当前的小朋友（从1开始）、然后是剩余的T9味糖果颗数以及T16味糖果的颗数。

DFS函数搜索所有满足条件的糖果分配方案。如果所有的小朋友都分到了糖果，且没有剩余的糖果，那么意味着找到了一种满足条件的分配方案，sum变量加1。

注意：这里判断条件的x为什么是x==8呢，因为一共是7个小朋友，从1开始到7刚好是7次，在第七次递归完成之后进入第八次递归这时候x==8，这时候才完成了七次递归，才给七个小朋友分完了糖果，所以应该在这里才判断并结束递归。

接着，通过两个for循环枚举给当前这个小朋友分配T9味和T16味糖果的所有可能，从0到他们的剩余数量（注意，这里for循环一定要是剩余的数量，不然一直写死是9和16那么是会出现负数的），并且颗数之和的范围在2到5之间。然后对于每一种可能，递归的进行接下来的分配。

通过这种方式，枚举所有可能的分配方案，并且计算出了满足条件的方案的数量。最后输出这个数量，就是问题的答案。

真的是很简单的一道DFS题目了，这题比那些二叉树的题还要简单。

代码实现

Java

package src;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static int sum = 0;public static void main(String[] args) {DFS(1, 9, 16);System.out.println(sum);}public static void DFS(int x, int t9, int t16) {// 如果遍历到最后一个人糖果分完了，那么sum++// 思路中提到了为什么x==8if (x == 8) {// 刚好分完 sum++if (t9 == 0 && t16 == 0) {sum++;}// 结束这次递归return;}// 进行遍历递归// 模拟第一种糖果for (int i = 0; i <= t9; i++) {// 模拟第二种糖果for (int j = 0; j <= t16; j++) {// 一个小朋友糖果数量是 2-5个if (i + j >= 2 && i + j <= 5) {// 给这个小朋友分完了，下一位DFS(x + 1, t9 - i, t16 - j);}}}}
}

C++

#include <iostream>
using namespace std;int sum = 0;void DFS(int x, int t9, int t16){if(x == 8){if(t9 == 0 && t16 == 0){sum++;}return;}for(int i = 0; i <= t9; i++){for(int j = 0; j <= t16; j++){// 判断2-5if(i + j >= 2 && i + j <= 5){DFS(x + 1, t9 - i, t16 - j);}}}
}int main(){// 请在此输入您的代码DFS(1,9,16);cout << sum;return 0;
}