递归放苹果问题和整数划分问题

布满荆棘的人生 2022-06-13 06:30 156阅读 0赞

放苹果问题

对于m个苹果，n个盘子f(m,n):

如果m<n，那么就跟m个盘子，m个苹果是一样的f(m,m)。

如果m>n，那么有两种情况:一种有空盘子的情况，一种没有空盘子的情况，两种情况不重叠且加一起一定为情况总数。

第一种情况：m个苹果放在n-1个盘子里，因为至少有1个空盘子，即f(m，n-1)

第二种情况：每个盘子都至少有一个苹果，m-n个苹果再放到n个盘子里，即f(m-n,n)。

由上面两种情况得到递归式f(m,n)=f(m,n-1)+f(m-n,n)。

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    int t , m, n;
    
    int f(int m, int n)
    {
    	if (m == 0 || n == 1) return 1; //没有苹果或者只有一个盘子则只有一种分法
    	if (n > m) return f(m, m);
    	return (f(m, n - 1) + f(m - n, n));
    }
    int main()
    {
    	cin >> t;
    	while (t--)
    	{
    		cin >> m >> n;
    		cout << f(m, n) << endl;
    	}
        return 0;
    }
    整数划分问题

整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：
           n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,...,mi}为n的一个划分。
           如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
           例如当n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
           注意4=1+3 和 4=3+1被认为是同一个划分。
           该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m)的方法;
    1.递归法：
           根据n和m的关系，考虑以下几种情况：
            （1）当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};
            (2) 当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};
            (3) 当n=m时，根据划分中是否包含n，可以分为两种情况：
                  (a). 划分中包含n的情况，只有一个即{n}；
                  (b). 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。
                  因此 f(n,n) =1 + f(n,n-1);
            (4) 当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);
            (5) 但n>m时，根据划分中是否包含最大值m，可以分为两种情况：
                   (a). 划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，因此这种情况下
                     为f(n-m,m)
                   (b). 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);
                  因此 f(n, m) = f(n-m, m)+f(n,m-1);
          综上所述：
                                 f(n, m)=   1;                (n=1 or m=1)
                                 f(n, n);                        (n<m)
                                 1+ f(n, m-1);                (n=m)
                                 f(n-m,m)+f(n,m-1);      (n>m)
     代码如下： #include<iostream>  
    #include<string>  
    #include<string.h>  
    #include<cstdio>  
    #include<algorithm>  
    using namespace std;  
      
    int fun(int n, int m)  
    {  
        if(n == 1 || m == 1) return 1;  
        else if(n < m) return fun(n, n);  
        else if(n == m) return (1 + fun(n, m - 1));  
        else return (fun(n, m - 1) + fun(n - m, m));  
    }  
      
    int main()  
    {  
        //freopen("Input.txt", "r", stdin);  
        int N;  
        scanf("%d", &N);  
        while(N--)  
        {  
            int n;  
            scanf("%d", &n);  
            printf("%d\n", fun(n, n));  
        }  
        return 0;  
    }