问题描述
两种糖果分别有9个和16个,要全部分给7个小朋友,每个小朋友得到的糖果总数最少为 2个,最多为 5个,问有多少种不同的分法。糖果必须全部分完。
只要有其中一个小朋友在两种方案中分到的糖果不完全相同,这两种方案就算作不同的方案。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数,填写多余的内容将无法得分。
解题思路
把每个人看成一个格子,类比走迷宫用dfs一格子一格子走下去就好
AC代码
public class Main {
public static void main(String[] args) {
dfs(1, 9, 16);
System.out.println(sum);
}
static int sum = 0;
static void dfs(int x, int a, int b) {
if (x == 8) {
if (a == 0 && b == 0) {
//如果七个人恰好分完则计数加一
sum++;
}
return;
}
for (int i = 0; i <= a; i++) {
for (int j = 0; j <= b; j++) {
if (i + j >= 2 && i + j <= 5) {
//只有满足2-5的条件才可以
dfs(x + 1, a - i, b - j);
}
}
}
}
}
相关知识
“DFS” 是深度优先搜索(Depth-First Search)的缩写,它是一种图遍历算法。该算法从图的某一顶点开始,沿着图的边不断向下探索,直到不能再继续为止,然后回溯到上一个节点,继续探索其他分支。DFS 通常用于解决图和树的遍历问题,以及与搜索连通性有关的问题。
在深度优先搜索中,有两种常见的实现方式:递归和使用栈。下面简要描述一下 DFS 的递归实现:
递归实现DFS的基本思路:
-
选择起始节点: 选择图的一个顶点作为起始节点。
-
访问节点: 标记当前节点为已访问,可以输出节点的值。
-
递归探索: 对当前节点的未访问邻居中选择一个,重复步骤 2。
-
回溯: 当当前节点的所有邻居都被访问过,回溯到上一个节点,重复步骤 3。
-
结束条件: 当所有节点都被访问过时,算法结束。
(by 归忆)
版权声明:本文为博主作者:归忆_AC原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq1677852098/article/details/134339911