浦项建设内部网站,wordpress下载按钮,阿里云共享云主机做网站,做外销网站将正整数n表示为一系列正整数之和#xff0c; nn1n2n3n4......nk #xff08;其中#xff0c;n1n2n3n4........nk0,k1#xff09;正整数n的这种表示成为正整数n的划分。正整数n的不同划分个数成为正整数n的划分数#xff0c;记作p#xff08;n…将正整数n表示为一系列正整数之和 nn1n2n3n4......nk 其中n1n2n3n4........nk0,k1正整数n的这种表示成为正整数n的划分。正整数n的不同划分个数成为正整数n的划分数记作pn。
例如正整数6有如下11种划分:
6;
51;
42,411;
33,321,3111;
222,2211,21111;
111111;
其实这种问题可以认为是把n划分为 加数小于或等于某个数的划分在这里把这个数成为m。例如对6的划分可以认作是将6划分为加数小于等于6的划分因为6的加数确实小于等于6为什么要引入这个m呢是因为我们发现从这个角度思考比较容易求解。我们将划分的种类数记为qn,m
在递归里要对形参进行判断
1当n1时 q(1,m)表示是对1的划分那么只有一种划分方式 1
2当m1时q(n,1)当m1时其实就是把让所有加数小于等于1那就是所有加数都是1咯不考虑负数当然也只有一种划分方式
3当nm时q(n,n)此时就是对n的划分出来的数没有限制默认限制就是不大于n此时划分的总类数要分两种情况才比较好解决 1.划分出来的数包含n或m因为nm:那只有一种方式 比如 6的划分 只有 6;一种方式2.划分出来的数不包含n或m因为nm:就可以认为是将6划分出来的数都小于6其实就是都小于或等于5,接下来 其实就是求出来q(n,n-1)或者是q(n,m-1),此时nm-1,放到递归方程里就是求解q(n,m) nm综合起来 q(n,n)1q(n,m-1)4当nm时当遇到这个问题时其实可以看做是对n的划分有了条件就是所有的划分出来的数小于m在上文中6有11种划分方式那是没有对6划分出来的数进行限制当要使划分出来的数都小于某个数时比如5时那就不是11种了。
51;
42,411;
33,321,3111;
222,2211,21111;
111111;
这个时候分两种情况包含m和不包含m
不包含m就是
42,411;
33,321,3111;
222,2211,21111;
111111;这些情况其实就是求6的划分出来的数小于等于4的情况,放到递归方程就是 q(n,m-1)
包含m就是
51;
这个时候确定这种划分数量的时候m不再是主角我们只要求出来n-m的划分情况就行了因为此时的m的划分情况取决于n-m。 比如包含m5的划分情况就是 6-51的情况比如包含4的划分情况就是求6-42,2的没有限制的划分情况。放到递归方程里面就是q(n-m,m)
5qn,mnm:nm时比如n6,m7 求得就是6得划分数小于等于7的情况其实就是求解小于等于6故此时情况就是求解q(n,n);
根据以上分析
q( n, n ) 1, 当 n 1;
q( n, n ) 1, 当m 1;
q( n, n ) q( n,n ) , 当n m;
q( n, n ) q( n, m-1) 1 , 当n m;
q( n, n ) q( n - m, m ) q( n , m -1) , 当n m0;
#includeiostream
using namespace std;
int q(int n,int m)
{if((n0)||(m0))return 0;if((n1)||(m1))return 1;if(nm)return q(n,n);if(nm)return (1q(n,m-1));if(1mn)return q(n,m-1)q(n-m,m);
}
int main()
{int n;cout输入需要来解决的整数划分问题的数字endl;cinn; coutn的整数划分的个数一共有q(n,n);return 0;}
