这个显卡不太冷 发表于 2016-8-17 13:12:52

【算法简析】整数划分问题

本帖最后由 这个显卡不太冷 于 2016-8-17 18:52 编辑

写这个是因为今天看到一道题 ,发现了新的做法~
以下是原题目:http://noi.openjudge.cn/ch0205/666/
总时间限制: 1000ms 内存限制: 65536kB描述把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)
5,1,1和1,5,1 是同一种分法。
输入第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。输出对输入的每组数据M和N,用一行输出相应的K。
样例输入17 3
样例输出8



乍一看这题,觉得应该就是属于DFS无脑搜的类型,从每个盘子都放一个开始枚举,判断重复的方案,最后输出。虽然这道题可行,因为数据10*20不算大,1S内可以过,但是如果真的数据大了,爆搜肯定没法过。
于是,我想到了类似的问题,整数划分问题。
-----------------------------------------------------------------简陋的分割线--------------------------------------------------------------------------
那么先来了解一下什么是整数划分问题。
整数划分问题是将一个正整数m拆成一组数连加并等于m的形式,且这组数中的最大加数不大于n。
    如6的整数划分为
   
    6
    5 + 1
    4 + 2,
    4 + 1 + 1
    3 + 3, 3 + 2 + 1,
    3 + 1 + 1 + 1
    2 + 2 + 2,
    2 + 2 + 1 + 1,
    2 + 1 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1 + 1
    一共11种
是不是觉得和放苹果问题有点像??
此类问题的正确解法是递归求解。(有点像DP)

首先设一个方法fun(m,n)表示整数m的在最大加数n的情况下的划分方案数。
1.有例子得出边界条件
   当m或者n都等于1的时候(被划分数为1或者只用1来划分),只有一种方案数。
   if(m==1||n==1) return 1;

2.有例子得出递归关系

(1)m=n
   这种关系一般是一开始就出现的关系。
   观察例子可得到方案数为“用本身划分(即只有一种)”的方案数和“不用本身划分的方案数(继续递归)”之和。
   if(m==n) return 1+fun(m,n-1);

(2)m>n
   紧接着出现的就是这种关系。
   同样是方案数为“用最大加数划分”和“不用最大加数划分”之和。
   if(m>n) return fun(m-n,n)+fun(m,n-1);
   这里说明一下,用最大加数分解的话那么其中一个数就定了,就成了被划分数减去最大加数后的划分方案。

(3)m<n
   如果(2)中设m=6,n=4,则可能会出现这种情况。
   这种情况十分简单。因为被划分数字不能超过m。那么等价于n=m;
   if(m<n) return fun(m,m);

至此,所有情况已经讨论完成,可以写代码了。
#include <stdio.h>

   int split(int n, int m)
   {
      if(n < 1 || m < 1) return 0;
      if(n == 1 || m == 1) return 1;
      if(n < m) return split(n, n);
      if(n == m) return (split(n, m - 1) + 1);
      if(n > m) return (split(n, m - 1) + split((n - m), m));
}

int main()
{
   printf("12的划分数: %d", split(12, 12));
    return 0;
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
回到最开始的问题,就变得很简单了。就像变式
设f(m,n)表示m个苹果放在n个盘子里的方案。
1.边界条件只有一个盘子或者只有一个苹果或者没有苹果(因为允许空)
if(m==1||n==1||m==0) return 1;

2.m>n
苹果数大于盘子数,则为空一个盘子和不空盘子的方案数之和(类比为用最大加数划分和不用最大加数划分之和)
if(m>n) return f(m,n-1)+f(m-n,n);
同样说明一下。因为m>n所以如果不空盘子的话,每个盘子里面放一个不会影响方案数。所以m=m-n;可以类比整数划分~~

3.m<n
反正有n-m个盘子是空的。
if(m<n) return f(m,m);

4.m=n
这种情况可以每个盘子放一个(一种方案),和f(m,n-1)的方案数之和。
通过观察,固定的一种方案必定是边界条件所以可以整合进1和2.


#include <stdio.h>
   
int f(int m , int n)
{
    if(m == 1 || n== 1 || m == 0) return 1;
    if(m < n)    return f(m, m);
    return f(m - n, n) + f(m, n - 1);
}

int main()
{
    int n , m , z;
    scanf("%d", &z);
    while(z-- > 0)
    {
      scanf("%d%d", &m ,&n);
      printf("%d\n",f(m, n));
    }
    return    0;
}代码提交上去是AC的。
文中部分思路借鉴网络。加入了个人的一些理解,方便大家能看懂。


20011010wo 发表于 2016-8-17 19:27:12

scanf不安全!快用scanf_s(微软教你做人),gcc就算了-_-||

20011010wo 发表于 2016-8-17 19:28:09

本帖最后由 20011010wo 于 2016-8-17 19:29 编辑

还有z->0这个语法糖我喜欢,叫趋向于吧?还有一个-->快速趋向于

这个显卡不太冷 发表于 2017-1-25 15:54:00

20011010wo 发表于 2016-8-17 19:28
还有z->0这个语法糖我喜欢,叫趋向于吧?还有一个-->快速趋向于

我写的是(z--)>0的意思

nkc3g4 发表于 2017-1-25 17:32:13

20011010wo 发表于 2016-8-17 19:27
scanf不安全!快用scanf_s(微软教你做人),gcc就算了-_-||
-_-|| 竞赛多数是GCC,用scanf_s过不了的

nkc3g4 发表于 2017-1-25 17:35:04

这个显卡不太冷 发表于 2017-1-25 15:54
我写的是(z--)>0的意思
直接写while(z--)就行。

20011010wo 发表于 2017-1-25 21:57:22

nkc3g4 发表于 2017-1-25 17:32
-_-|| 竞赛多数是GCC,用scanf_s过不了的

所以算了

iwork 发表于 2019-4-28 11:02:56

这用来解决什么问题
页: [1] 2
查看完整版本: 【算法简析】整数划分问题