整数划分问题

coding

学习博客:https://www.cnblogs.com/jinhong123/p/7909689.html  

说明一下问题,什么是整数划分?

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=5时我们可以获得以下这几种划分(注意,例子中m>=5)

5 = 5

= 4 + 1

= 3 + 2

= 3 + 1 + 1

= 2 + 2 + 1

= 2 + 1 + 1 + 1

= 1 + 1 + 1 + 1 + 1

一、 动态规划解法

根据n和m的关系,考虑以下几种情况: 

1、当n=1时,显然f(n,m) =1(m>0) 只有本身

2、当m=1等于1时,不管n等于多少,都只有n个1组成的集合

3、当n=m时,考虑是否取m值,分为两种情况:

  取m值,那么就只有一个n

  不取m值,那么转化为f(n,m-1)    

  所以f(n,m)=1+f(n,m-1)

4、当n<m时,完全可以看作n=m的情况

5、当n>m时,考虑是否取m

  取m值,即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m,可能再次出现m,因此是(n-m)的m划分,因此这种划分个数为f(n-m, m); 

  不取m值, 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1);

  所以n>m的情况,f(n,m)=f(n-m,m)+f(n,m-1)

综上所述:可以按情况进行递归:

其中1 2属于递归终止条件

3 4属于特殊情况

5属于通用情况

下面看代码:

#include<iostream>

usingnamespace std;

int dfs(int n,int m)

{

cout<<n<<""<<m<<endl;

// cout<<n<<" "<<m<<endl;

if(n==1||m==1) return1;

elseif(n==m) return1+dfs(n,m-1);

elseif(n>m) return dfs(n-m,m)+dfs(n,m-1);

elseif(n<m) return dfs(n,n);//相当于n,n的情况

}

int main()

{

int n,m;

while(cin>>n>>m)

{

cout<<dfs(n,m)<<endl;

}

return0;

}

下面看几个变种:

(一)要求1,2,3,4..,m中每个数只允许使用一次的时?

只需要考虑当n>m时,考虑是否取m

  取m值,即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m,可能再次出现m,因此是(n-m)的m划分,因此这种划分个数为f(n-m, m-1); 因为m不能再取了 

  不取m值, 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1);

  所以n>m的情况,f(n,m)=f(n-m,m)+f(n,m-1)

  但是终止条件 当n=1时 m>=1 肯定是1   但是当n=1  m<1或者  n>1 m=1时显然是0  因为你已经凑不出来了n值

(二)要求只能取1,2,3,4,..,m中的奇数?(默认m为奇数,如果不是则m=m-1)

  这个呢,我们首先需要调整边界状态:当m=1时,f(n,m)=1;当n=1而m>1时,f(n,m)=0

  其次,我们需要调整状态转换公式:

  f(n-m,m)+f(n,m-1); (n>m) 应该更改为:f(n-m,m)+f(n,m-2); (n>m)

  当n=m时,考虑是否取m值,分为两种情况:

  取m值,那么就只有一个n

  不取m值,那么转化为f(n,m-2)    

  所以f(n,m)=1+f(n,m-2)

以上是 整数划分问题 的全部内容, 来源链接: utcz.com/z/509317.html

回到顶部