题目：糖果分配方案
题目描述
现在有n颗糖均匀地分配给n个人，每个人的糖的数量可以为0。请找出所有可能的分配方案。
输入
一个正整数n，表示糖果的数量和待分配的人的数量。
输出
输出各种可能的分配方案，每行为一种方案，每个数字之间用空格分隔。
例子
输入：
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
解决思路
我们可以使用递归的方法来生成所有可能的糖果分配方案。对于每个人，我们遍历他们可能分到的糖果数量（从0到剩余糖果数量），然后递归地调用函数来处理剩下的人和剩余的糖果数量。
代码实现
#include <iostream> #include <vector> using namespace std; // 递归生成所有糖果分配方案 void generateDistributions(int candies, int people, vector<int>& distribution) { // 如果只剩下一个人，则将剩余的糖果数量加入分配方案中，输出当前方案，并弹出向量中的元素 if (people == 1) { distribution.push_back(candies); // 输出当前的分配方案 for (int i = 0; i < distribution.size(); i++) { cout << distribution[i]; if (i != distribution.size() - 1) cout << " "; } cout << endl; distribution.pop_back(); return; } // 第一个人获得的糖果数量从0到candies递增 for (int i = 0; i <= candies; i++) { distribution.push_back(i); // 递归调用函数来分配剩余的糖果数量给其他人 generateDistributions(candies - i, people - 1, distribution); distribution.pop_back(); } } int main() { int n; cin >> n; vector<int> distribution; // 调用函数生成糖果分配方案 generateDistributions(n, n, distribution); return 0; }
解释和讨论
在这个问题中，我们使用了递归的方法来生成所有可能的糖果分配方案。通过遍历每个人可能分到的糖果数量，并递归地处理剩下的人和剩余的糖果数量，我们可以找到所有的方案。
在代码中，我们定义了一个generateDistributions函数来执行递归。我们使用一个向量（distribution）来存储当前的分配方案。
对于每个递归步骤，我们首先判断是否只剩下一个人。如果是，则将剩余的糖果数量加入distribution中，输出当前的分配方案，并弹出向量中的元素。如果不是，则遍历第一个人可能分到的糖果数量，并递归地调用函数来处理其他人和剩余的糖果数量。
在主函数中，我们读取输入的糖果数量和人数，并调用generateDistributions函数来生成糖果分配方案。
最后我们封装成了一个函数
#include <iostream> #include <vector> #include <functional> using namespace std; // 递归生成所有糖果分配方案 vector<vector<int>> generateDistributions(int candies, int people) { vector<vector<int>> result; vector<int> distribution; // 嵌套函数用于递归生成糖果分配方案 function<void(int, int)> generate = [&](int candies, int people) { // 如果只剩下一个人，则将剩余的糖果数量加入分配方案中，输出当前方案，并弹出向量中的元素 if (people == 1) { distribution.push_back(candies); result.push_back(distribution); distribution.pop_back(); return; } // 第一个人获得的糖果数量从0到candies递增 for (int i = 0; i <= candies; i++) { distribution.push_back(i); // 递归调用函数来分配剩余的糖果数量给其他人 generate(candies - i, people - 1); distribution.pop_back(); } }; // 调用嵌套函数生成糖果分配方案 generate(candies, people); return result; } int main() { int n; cin >> n; vector<vector<int>> distributions = generateDistributions(n, n); // 输出糖果分配方案 for (int i = 0; i < distributions.size(); i++) { for (int j = 0; j < distributions[i].size(); j++) { cout << distributions[i][j]; if (j != distributions[i].size() - 1) cout << " "; } cout << endl; } return 0; }
