相同元素分配到相同空间问题（放鸡蛋问题）详解(Detailed explanation of the problem of assigning the same elements to the same space (egg laying problem))-其他

相同元素分配到相同空间问题（放鸡蛋问题）详解(Detailed explanation of the problem of assigning the same elements to the same space (egg laying problem))

## 对于问题1：将n个鸡蛋放到m个篮子里，允许有空篮子，有几种方法？方法数 = 所有篮子都不空 + 空1个篮子 + 空2个篮子 + … +空m -1个篮子即“F(m,n) = T(m,n) + T(m-1,n) + T(m-2,n) + … + T(1,n)“，根据上面对问题2的分析我们可知：T(m,n) = F(m,n-m)，则上式变为：“F(m,n) = F(m,n-m) + F(m-1,n)“这也就是我们后边要用到的**递归**原型。对于递归来说，我们要考虑好它的**终止条件**：* 当 m = 1即篮子数 = 1时，无论有多少的鸡蛋都只能放进这个篮子里，所以返回1；* 当 n = 0即鸡蛋数 = 0时，无论有多少篮子，也没有鸡蛋可以放，所以返回0；* 当 n < m 即鸡蛋数 <篮子数时，肯定会有n – m个空篮子，所以我们令m = n；

**但此时我们得到的递归式还并不是我们最终需要的**，在此我以F(2,2)作为例子：`F(2,2)`指将两个鸡蛋放入两个篮子中，且允许有空篮子。那我们仔细想一想其实就能想出来，只有两种分配方法：1,1和2，0。但此时若我们用上述得到的式子进行计算可得：`F(2,2) = F(2,0) + F(1,2) = 1`与真实答案不符，仔细观察该式，可知原因：**当 m = n时，直接利用变化来的式子未考虑一个篮子放一个鸡蛋的情况**，所以还要在上面得到的式子的基础上，对**终止条件**进行补充：* 当 n = m时，令`分配方法数 += 1`。

## 以数的划分为例题我用c++以上述思路来解决数的划分：题目描述将整数 n 分成 k 份，且每份不能为空，问有多少种不同的分法。当 n=7, k=3 时，下面三种分法被认为是相同的：1,1,5; 1,5,1; 5,1,1

“`7 3“`输出数据“`4“`四种分法为：1,1,5；1,2,4；1,3,3；2,2,3。

“`cpp/***Filename:heli*Author:wan*Date:2022.1.14*version:1.3*Description:heli*/#include <bits/stdc++.h>using namespace std;int number;//分配方法数int give_space(int m,int n){ //篮子是m,鸡蛋是n int sum = 0; if(m ==n){ sum += 1; // printf(“sum:%d\n”,sum); } if(n == 0){//蛋 = 0 return 0; } if(m == 1||m == 0){//篮子 = 0/1 return 1; } if(n < m){//鸡蛋数<篮子数时，篮子 = 鸡蛋 m = n; //此处判断很重要，否则计算时会少1 return give_space(m,n); } //printf(“%d %d\n”,m,n); sum += give_space(m,n-m); sum += give_space(m-1,n); return sum;}int main(){ int n,k; scanf(“%d %d”,&n,&k); if(n <= k){ number = 1; } else{ //k = m,篮子，n是鸡蛋 number += give_space(k,n – k); } printf(“%d”,number); return 0; }“`*ps:在终止条件中，当 n < m 即鸡蛋数 <篮子数时，我们令m = n后记得把这个m,n重新传进去，否则会少考虑将每个篮子里放一个鸡蛋的情况。*

————————

In high school, the arrangement and combination problem we came across was to put the same elements in different spaces, which was easy to find** So what if the same elements are allocated to the same space** I checked it on the Internet, but I didn’t explain it in detail, so I deduced it according to the existing data, and corrected the errors in some of the existing data here. Next, I will take the * * put eggs * * problem as an example. There are ` n ‘eggs and ` m’ baskets. Ask: * put n eggs in M baskets and * * allow * * to have empty baskets. How many methods* Put n eggs into m baskets, and * * is not allowed * * to have empty baskets. How many methods are there* PS: 1, 1, 5 when n = 7 and M = 3; 1，5，1； 5, 1 and 1 are considered to be the same division*

**But at this time, the recursive formula we get is not what we finally need * *. Here I take F (2,2) as an example: ` f (2,2) ‘refers to putting two eggs into two baskets and allowing empty baskets. If we think about it carefully, we can actually figure out that there are only two allocation methods: 1,1 and 2,0. But at this time, if we use the above formula to calculate, we can get that: ` f (2,2) = f (2,0) + F (1,2) = 1 ‘is inconsistent with the real answer. After careful observation of the formula, we can see the reason: * * when m = n, the formula directly using the change does not consider the situation of putting one egg in one basket * *, so we need to supplement the * * termination condition * * on the basis of the formula obtained above: * when n = m, Let ` number of allocation methods + = 1 ‘.

##Taking the division of numbers as an example, I use C + + to solve the division of numbers with the above ideas: the problem description divides the integer n into k parts, and each part cannot be empty. How many different divisions are there. When n = 7 and K = 3, the following three methods are considered to be the same: 1,1,5; 1,5,1; 5,1,1

Enter two numbers n, K in one line.

The output format is an integer per line, that is, different division numbers. input data

“`7 3 ` ` output data ` ` 4 ` ` four classification methods are: 1,1,5; 1,2,4； 1,3,3； 2,2,3。

Idea: Here I regard number as an egg and division as a basket.

“`cpp/***Filename:heli*Author:wan*Date:2022.1.14*version:1.3*Description:heli*/#include < bits/stdc++. h> using namespace std; int number;// Number of allocation methods int give_ Space (int m, int n) {/ / basket is m, egg is n, int sum = 0; if (M = = n) {sum + = 1; / / printf (“sum:% d \ n”, sum);} If (n = = 0) {/ / egg = 0 return 0;} If (M = = 1|m = = 0) {/ / basket = 0 / 1 return 1;} If (n & lt; m) {/ / number of eggs & lt; number of baskets, basket = egg, M = n; / / judgment here is very important, otherwise 1 return give_space (m, n) will be lost during calculation;}// printf(“%d %d\n”,m,n); sum += give_ space(m,n-m); sum += give_ space(m-1,n); return sum;} int main(){ int n,k; scanf(“%d %d”,&n,&k); if(n <= k){ number = 1; } Else {/ / k = m, basket, n is egg number + = give_space (k, N – K);} printf(“%d”,number); return 0; }“`* PS: in the termination condition, when n & lt; M is the number of eggs & lt; When counting the baskets, we should remember to re pass this m and N after making M = n, otherwise we will less consider putting one egg in each basket*

Finally: Based on personal understanding, there may be errors in this paper. If there are errors, please point out them and I will modify them as soon as possible. Hope to help you: D