【算法简析】整数划分问题
本帖最后由 这个显卡不太冷 于 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的。
文中部分思路借鉴网络。加入了个人的一些理解，方便大家能看懂。
scanf不安全！快用scanf_s（微软教你做人），gcc就算了-_-|| 本帖最后由 20011010wo 于 2016-8-17 19:29 编辑
还有z->0这个语法糖我喜欢，叫趋向于吧？还有一个-->快速趋向于 20011010wo 发表于 2016-8-17 19:28
还有z->0这个语法糖我喜欢，叫趋向于吧？还有一个-->快速趋向于
我写的是(z--)>0的意思 20011010wo 发表于 2016-8-17 19:27
scanf不安全！快用scanf_s（微软教你做人），gcc就算了-_-||
-_-|| 竞赛多数是GCC，用scanf_s过不了的 这个显卡不太冷 发表于 2017-1-25 15:54
我写的是(z--)>0的意思
直接写while(z--)就行。 nkc3g4 发表于 2017-1-25 17:32
-_-|| 竞赛多数是GCC，用scanf_s过不了的
所以算了 这用来解决什么问题
页:
[1]
2