整数划分 (头歌算法分析设计)

整数划分 (头歌算法分析设计)"/>

整数划分 (头歌算法分析设计)

大家好今天带来一道头歌上的题目 . 

问题描述

将正整数n表示成一系列正整数之和。 n = n1 + n2 + …… + nk，其中n1≥n2≥……≥nk≥1，k≥1 正整数这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记为p(n)。 例如正整数6有如下11种不同的划分,所以p(6)=11.

6;

5 + 1;

4 + 2, 4 + 1 + 1;

3 + 3, 3 + 2 + 1, 3 + 1 + 1;

2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1;

输入形式

正整数n

输出形式

n的划分数。

样例输入

6

样例输出

11

#include<iostream>
using namespace std;
int split(int n,int m)
{if(n==1||m==1)return 1;else if (n<m)return split(n,n);else if(n==m)return split(n,n-1)+1;elsereturn split(n,m-1)+split(n-m,m);
}int main()
{int n;cin>>n;cout<<split(n,n);
}

这期就到这里下期见!