算法题目——整数划分(HRBUST-2004)

爱被打了一巴掌 2022-09-14 02:24 172阅读 0赞

题目链接：[HRBUST-2004][]

递归法:

1.当n=1时，此时只有1种解\{1\};

2.当m=1时，此时也只有1种解\{1,1,1, …

3.当n> m时，要分为最大数包含m和不包含m两种情况。

●包含m:此时就是\{mx1,2…\}. 其中x1+x2+3.+… =n-m, 就相当于求和为n-m,最大值为m的划分个数: f(n-m,m)  
●不包含m:此时最大数最大为m-1,相当于把n划分为最大数为m-1的划分个数: f(n,m-1)

因此:当n>m时划分个数为f (n-m,m) +f (n,m-1)

4.当n=m时，此时也要分为两种情况，包含m和不包含m。

●包含m,此时就只有一种情况，\{m\}  
●不包含m,此时最大值为m-1, f(n,m-1)

因此:当n=m时， 划分个数为1+f (n, m-1) ;

5.当n<m时,此时不可能包含m,最大值最大就是n,最大划分个数为f (n,n) 。也可以分为包含n和不包含n两种情况:

●包含n，此时就只有一种情况，\{n\};●不包含n，最大值是n-1, f(n,n-1)

因此可以写成1+(n,n-1).  
相关问题分析：[算法设计与分析——分治与递归——整数划分问题][Link 1]  
问题点：注意 **多组测试数据，输入到文件结束**

#include<iostream>
    #include<vector>
    using namespace std;
    int q(int n,int m)//整数n的划分，划分中最大数为m 
    {
        
    	if((n<0)||(m<0))
    		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));
    	if(1<m<n)
    		return q(n,m-1)+q(n-m,m);
    }
    int main()
    {
        
    	int n;
    	vector<int> vec;
    	while(scanf("%d",&n)!=EOF)
    	{
        
    		vec.push_back(q(n,n));
    	 } 
    	for(int i=0;i<vec.size();i++)
    	{
        
    		cout<<vec[i]<<endl;
    	}
    	
    
    	return 0;
     }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_7_color_FFFFFF_t_70_g_se_x_16]

[HRBUST-2004]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2004
[Link 1]: https://blog.csdn.net/qq_50675813/article/details/117480405
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d6a61168bb2c4fb8b0a7b77fdbf885d1.png