D. 例题3.2.2 整数划分问题

题目描述

将正整数n表示成一系列正整数之和：n=n_1+n_2+...+n_kn=n1​+n2​+...+nk​，其中8\geq n_1\geq n_2\geq ...\geq n_k\geq 18≥n1​≥n2​≥...≥nk​≥1，k\geq1k≥1。正整数n的这种表示称为正整数n的划分。

例如正整数6有如下11种不同的划分：

6；5+1；4+2，  4+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。

Copy

输入格式

一个正整数 n

保证 n\leq 8n≤8

输出格式

一个正整数 m，表示n可以被分成m种

input

6

Copy

output

11

Copy

数据规模与约定

时间限制：1s

空间限制：256MB

这道题其实就是根据这个n然后把已知的所有条件都求出来就即可。

整数划分问题将正整数n表示成一系列正整数之和，n=n1+n2+……+nk n1>=n2>=………>=nk>=1;k>=1正整数n的划分数，记为p(n)。例如正整数6有如下11种不同的划分，所以p(6)=11在最大加数n1不大于m的划分个数记作q(n,m)。 q(n,m)=1, 当n=1，m=1;q(n,m)=q(n,n) 当n<m; q(n,m)=1+q(n,n-1) 当n==m;q(n,m)=q(n,m-1)+q(n-m,m) 当n>m

#include<bits/stdc++.h>
using namespace std;
int fun(int n, int m)
{
    if(n==1||m==1)return 1;
    else if(n<m)return fun(n,n);
    else if(n==m)return (1+fun(n,m-1));
    else return(fun(n,m-1)+fun(n-m,m));
}
int main()
{
//    freopen("decompose.in","r",stdin);
//    freopen("decompose.out","w",stdout);
    int n;
    cin>>n; 
    cout<<fun(n,n);
    return 0;
}