萝卜头IT论坛

了解更多
搜索
查看: 772|回复: 6
收起左侧

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

[复制链接]
发表于 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);

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

  2.    int split(int n, int m)
  3.    {
  4.       if(n < 1 || m < 1) return 0;
  5.       if(n == 1 || m == 1) return 1;
  6.       if(n < m) return split(n, n);
  7.       if(n == m) return (split(n, m - 1) + 1);
  8.       if(n > m) return (split(n, m - 1) + split((n - m), m));
  9.   }

  10. int main()
  11. {
  12.      printf("12的划分数: %d", split(12, 12));
  13.     return 0;
  14. }
复制代码


---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
回到最开始的问题,就变得很简单了。就像变式
设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.


  1. #include <stdio.h>
  2.    
  3. int f(int m , int n)
  4. {
  5.     if(m == 1 || n== 1 || m == 0) return 1;
  6.     if(m < n)    return f(m, m);
  7.     return f(m - n, n) + f(m, n - 1);
  8. }

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


评分

1

查看全部评分

回复

使用道具 举报

发表于 2016-8-17 19:27:12 来自手机 | 显示全部楼层
scanf不安全!快用scanf_s(微软教你做人),gcc就算了-_-||
回复

使用道具 举报

发表于 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的意思
回复

使用道具 举报

发表于 2017-1-25 17:32:13 | 显示全部楼层
20011010wo 发表于 2016-8-17 19:27
scanf不安全!快用scanf_s(微软教你做人),gcc就算了-_-||

-_-|| 竞赛多数是GCC,用scanf_s过不了的
回复

使用道具 举报

发表于 2017-1-25 17:35:04 | 显示全部楼层

直接写while(z--)就行。
回复

使用道具 举报

发表于 2017-1-25 21:57:22 | 显示全部楼层
nkc3g4 发表于 2017-1-25 17:32
-_-|| 竞赛多数是GCC,用scanf_s过不了的

所以算了
回复

使用道具 举报

联系站长|手机版|萝卜头IT论坛 ( 苏ICP备15050961号-1 )

GMT+8, 2018-4-27 02:58 , Processed in 0.090429 second(s), 40 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表