PTA 整数的划分问题 算法

对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。例如，对于正整数n=6，它可以分划为：

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，一共有11种，其中5+1和1+5被认为是同样的。

输入格式:

输入有多组数据，每行为一个正整数n(n < 50)。

输出格式:

对于每组输入，输出有多少种整数划分的方法。

输入样例:

在这里给出一组输入。例如：

1
6

输出样例：

1
11

详细的算法思路请看这篇文章，讲得非常详细：【算法】整数划分问题

以下给出我的代码：

#include<iostream>
#include <sstream> 
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;
    else
        return split(n,m-1)+split(n-m,m);
}

int main()
{
    
    int n;
    while(cin>>n)
    {
        cout<<split(n,n)<<endl;
        
    }
    //cout << line << endl << line.length();
}

其中有一个很值得讲的点：题目要求输入不定多行数据，并且没有结束标志，此时可利用cin对象的返回值作为循环的判断条件

while(cin>>n)
{
	//code here
}

最后

以上就是直率牛排为你收集整理的PTA 整数的划分问题 算法的全部内容，希望文章能够帮你解决PTA 整数的划分问题 算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。