主要内容
- 分解因数
- 放苹果问题
1. 分解因数
问题描述
给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意到a = a也是一种分解。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768)。
输出
n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。
样例输入
2
2
20
样例输出
1
4
算法分析
令i = 2~an,通过an%i ==0来判断i是不是an的因数，如果是，则由an/i作为参数进一步带入函数来判断直至an/i == i，(此时i为最后一个因数)。
首先需知道f(m,n)的含义——求n中从m开始到n/m所有分解种数的和。而为什么每次只要满足上面的条件就算加一种情况呢？这不妨举个例子当n = 100时，2、50算一种情况，而50可以继续分为2、25，这就有了2、2、25，再继续分，且每次分都能成为其一种分解情况所以a++。
参考程序
#include < iostream >
using namespace std;
int s = 0; //s用来记录分解的种类的数
void f(int x, int y) //x为因数，y为被分解数
{
for (int i = x; i * i >= y; ++i) {//依次试每一次分解
if (y % i == 0) {
++s;//种数加一
f(i, y / i);//返回下一次函数调用
}
}
}
int main()
{
int t;
cin >> t; //输入样例的总数
while (t--) {
int a = 0;
cin >> a;
s = 1;//a=a也算一种分解
f(2, a);
cout << s << endl;
}
return 0;
}
2. 放苹果问题
问题描述
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？5，1，1和1，5，1 是同一种分法。
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
1
7 3
样例输出
8
算法分析
该题目主要运用了递推的思维方式，解决的关键在于找出递推关系和递推出口。
m个苹果放在n个盘子中，设递推函数为apple(m,n)：
情况1：
m=0，没有一个苹果，则apple(0,n)=1；
情况2：
n=1，只有一个盘子，则apple(m,1)=1
情况3：
n>m，与m个苹果放在m个盘子中情况一样，则apple(m,n)=m
情况4：
n<=m，按是否有空盘子，又可以分为两种情况：
不是所有盘子都有苹果（至少有一个盘子没有苹果），则apple(m,n-1)
所有盘子都有苹果（至少每个盘子都有一个苹果），m个苹果中有n个放在n个盘子里，剩下m-n个苹果，这种情况和m-n个苹果放在n个盘子中是一样的，即apple（m-n,n）
则有以下递推关系：apple（m,n）=apple（m−n,n）+apple（m,n−1）
综上所述：可以将情况1和情况2视为一种临界条件，即为n=1时，所有苹果都在一个盘子中；m=0时，没有苹果可放！这种临界条件通常可以视为递归出口。
参考程序
#include < iostream >
using namespace std;
int apple(int m,int n) {
//情况1和情况2
if(m<=1||n==1) return 1;
//情况3
if(n>m)
return apple(m,m);
else
return(apple(m-n,n)+apple(m,n-1)); //情况4
}
int main() {
//设置两个数组分别存苹果数和盘子数
int n,a[20],b[20],i;
cin>>n;
for(i=0;i < n;i++)
cin>>a[i]>>b[i];
for(i=0;i < n;i++) {
cout << apple(a[i],b[i]) << endl;
}
return 0;
}