1910 - 整数划分
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。
正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
Input
第一行，输入需要划分的整数n。
Output
输出整数划分的个数。
Examples
Input
6
Output
11
Hint
建立递归关系，编程递归算法。
Solution C
#include<stdio.h> int main() { int q(int ,int ); int n,r; scanf("%d",&n); r=q(n,n); printf("%d\n",r); //system("pause"); return 0; } int q(int n,int m) { if(n<1||m<1) return 0; if(n==1||m==1) return 1; if(n<m) return q(n,n); if(n==m) return 1+q(n,m-1); return q(n,m-1)+q(n-m,m); }
Solution C++
#include<iostream> using namespace std; class BS{ int n,m; public: void q(int n,int m) { this->n=n; this->m=m; } int p(int n,int m) { if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n<m) return p(n,n); if(n==m) return p(n,m-1)+1; else return p(n,m-1)+p(n-m,m); }}; int main() { BS a; int N,M; cin>>N; M=N; a.q(N,M); a.p(N,M); cout<<a.p(N,M)<<"\n"; }
Hint
建立递归关系，编程递归算法。