整数划分问题

将一个正整数n表示成一系列正整数之和。

n = n1+n2+n3+...+ni(其中,n1>=n2>=...>=nk>=1,k>=1)

正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数称为正整数n的划分数,记作p(n)。

例如:正整数6有如下11种不同的划分,所以p(6) = 11。

6;

5+1;

4+2,4+1+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。

求正整数n的不同划分个数。

正整数n要怎么分呢。将n划分成最大加数n1<= m的划分个数记为f(n, m)

一、 递归的做法:

整数划分问题

最后一点:

n>m>1时,根据划分中是否包含最大值m,可以分为两种情况:

       1)划分中包含m的情况,即{m, {m+1,m+2...m+i}}, 其中{m+1,m+2,..m+i} 的和为n-m,因此这情况下为理解为n-m不大于m的划分,个数为q(n-m,m);
       2)划分中不包含m的情况,那么划分出来的正整数都比m小,最大的为m-1,即为n的(m-1)划分,那么,此时这种情况的个数为q(n,m-1);

     所以,综合上面两点 q(n, m) = q(n-m, m)+q(n,m-1);
原文链接:https://blog.csdn.net/weixin_35909255/article/details/54896972

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

上一篇:2021年N1叉车司机考试题库及N1叉车司机考试报名


下一篇:Codeforces Round #742 (Div. 2)--C