圣诞节到了，圣诞老人给 N 个小朋友准备了 M 个同样的礼物。每个小朋友有一个袜子（袜子不编号，无区别，认为袜子都相同），
圣诞老人将 M 个礼物装到 N 个袜子中的放法有多少种？
注意：
1）若M=7 N=3，那么5,1,1的放法和1,5,1的放法算是同一种装法。
2）允许袜子为空。
3）M和N无大小关系，M可以比N大，M也可以比N小。
Input
输入数据包含两个整数 M,N。1<=M,N<=50。
M在前，N在后，中间空格。
Output
输出共有几种不同的放法。
Sample Input
7 3
Sample Output
8
### 圣诞礼物问题解析
#### 问题背景与定义
圣诞节是西方的传统节日之一，在这一天，传说中的圣诞老人会给孩子们送去礼物。本问题探讨的是一个经典的组合数学问题：假设圣诞老人给N个小朋友准备了M个同样的礼物，每个小朋友都有一个相同的袜子，现在需要计算圣诞老人将M个礼物放入N个袜子中不同方法的数量。
#### 问题描述
- **输入**：输入数据包含两个整数M和N，表示礼物的数量和小朋友的数量。其中1 <= M, N <= 50。
- **输出**：输出所有可能的不同放法数量。
- **示例**：
- 输入：7 3
- 输出：8
#### 解题思路
本问题可以通过递归的方式来解决，主要涉及到的是组合数学中的“分治”思想。具体的递归公式如下：
\[f(m, n) = \begin{cases}
0 & m < 0 \\
1 & m = 0 \\
f(m, n-1) + f(m-n, n) & \text{其他情况}
\end{cases}
\]
- **边界条件**：
- 当`m < 0`时，表示袜子中礼物的数量为负数，这是不可能的情况，所以返回0。
- 当`m == 0`时，表示当前袜子中不再有礼物需要分配，因此无论袜子数量如何，只有一种情况，即所有袜子已经正确地分配了礼物，此时返回1。
- **递归过程**：
- `f(m, n-1)`表示将当前袜子不考虑，计算剩余袜子和礼物的分配方法数量。
- `f(m-n, n)`表示将当前袜子放入`n`个礼物，然后计算剩余袜子和礼物的分配方法数量。
#### 代码实现分析
下面给出的C语言程序实现了上述递归算法来解决该问题。
```c
#include<stdio.h>
// 定义递归函数 distribution 来计算不同放法的数量
int distribution(int m, int n){
if (m < 0) return 0; // 如果礼物数量小于0，则返回0
if (m >= 1) {
if (n == 0) return 0; // 如果没有袜子，则返回0
if (n == 1) return 1; // 如果只有一个袜子，则只有一种放法
}
if (n >= 1) {
if (m == 0) return 1; // 如果礼物数量为0，则只有一种放法
}
// 递归调用
return distribution(m, n-1) + distribution(m-n, n);
}
// 主函数
int main(){
int m, n;
scanf("%d %d", &m, &n); // 输入礼物数量和袜子数量
printf("%d", distribution(m, n)); // 输出结果
return 0;
}
```
#### 结论
通过以上分析和代码实现，我们解决了圣诞礼物问题，并且能够正确地计算出不同的放法数量。这个问题不仅考验了编程能力，还涉及到了组合数学中的递归思维，对于理解和掌握递归算法具有很好的实践意义。此外，本问题还可以进一步优化，例如通过动态规划减少重复计算来提高效率等。
