算法问题:整数划分问题

来源：百度知道 编辑：UC知道 时间：2024/05/03 02:04:09
问题如下:
输入整数N,例如n=5:
5;
4+1;
3+2;3+1+1;
2+2+1;2+1+1+1
1+1+1+1+1;
输出:7;

现在问题是要划分为正奇数和不同的正整数和,望高手指教

#include <iostream>
using namespace std;

int q(int n,int m) //n个正整数的小于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 q(n,n-1)+1;
return q(n,m-1)+q(n-m,m);
}

int q2(int n,int m) //正奇数划分
{
if(n<1 || m<1) return 0;
if(n==1 || m==1) return 1;
if(n<m) return q2(n,n);
if(n==m && n%2==1) return q2(n,n-1)+1;
if(n==m && n%2==0) return q2(n,n-1);
//if(n>m && n%2==1)
return q2(n,m-2)+q2(n-m,m);
//return q2(n,m-2)+q2(n-m,m);
}

int q3(int n,int m) //不同正整数划分
{
if(n==1 && m==1) return 1;
if(n<0 || m<=1) return 0;
if(n<m) return q3(n,n);
if(n==m) return q3(n,n-1)+1;
return q3(n,m-1)+q3(n-m,m-1);
}

int main()
{
int n,m;
cin >> n >> m;
cout << q(n,n) << endl;
cout <<