poj 放苹果(C语言 递归）

原题链接
Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input1
7 3
Sample Output
8
用递归思想，缩小范围，把这个问题分解成多个子问题：
子问题一：
当苹果数目小于盘子数目时（即N>=M),无论怎么放都会有盘子是空的，最多使用N个盘子（即每个盘子放一个苹果），缩小范围，把问题转化成把M个苹果放到M个盘子中；
子问题二：
当苹果数目大于盘子数目时（即N<=M),此时又存在两种情况：有盘子是空的和没有空盘子；
So:
**子问题二的子问题一：**把有盘子是空的缩小范围至有一个盘子是空，这就转化成了把M个苹果放到N-1个盘子中；
**子问题二的子问题二：**没有空盘子，也就是每个盘子至少有一个苹果，这也就转化成了把M-N个苹果放到N个盘子里。
代码实现：

#include<stdio.h>
int f(int m,int n){if(m==0||n==1) return 1;if(n>m) return f(m,m);else return f(m-n,n)+f(m,n-1);} 
int main(void)
{int m,n;int t;scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);printf("%d",f(m,n));if(t!=0) printf("\n");} return 0;
}```

poj 放苹果(C语言 递归）

原题链接
Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input1
7 3
Sample Output
8
用递归思想，缩小范围，把这个问题分解成多个子问题：
子问题一：
当苹果数目小于盘子数目时（即N>=M),无论怎么放都会有盘子是空的，最多使用N个盘子（即每个盘子放一个苹果），缩小范围，把问题转化成把M个苹果放到M个盘子中；
子问题二：
当苹果数目大于盘子数目时（即N<=M),此时又存在两种情况：有盘子是空的和没有空盘子；
So:
**子问题二的子问题一：**把有盘子是空的缩小范围至有一个盘子是空，这就转化成了把M个苹果放到N-1个盘子中；
**子问题二的子问题二：**没有空盘子，也就是每个盘子至少有一个苹果，这也就转化成了把M-N个苹果放到N个盘子里。
代码实现：

#include<stdio.h>
int f(int m,int n){if(m==0||n==1) return 1;if(n>m) return f(m,m);else return f(m-n,n)+f(m,n-1);} 
int main(void)
{int m,n;int t;scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);printf("%d",f(m,n));if(t!=0) printf("\n");} return 0;
}```