主要内容 #

1. 分解因数
2. 放苹果问题

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）=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;
}