[C++知识库]4117:简单的整数划分问题

4117:简单的整数划分问题
很难理解，绕来绕去绕不明白

#include <bits/stdc++.h>
using namespace std; 
//int takeapart(int n,int i){//分解n，从最大因数i开始分解 
//	if(n==0||i==1)return 1;
//	if(n==i)return takeapart(n,i-1)+1;
	if(n<i)return takeapart(n-i,n-i)+takeapart(n,i-1);
//	if(n<i)return takeapart(n,n);
//	if(n>i)return takeapart(n-i,i)+takeapart(n,i-1);
//}
int takeapart(int n,int i){//不能确定n和i哪个大，n-i是差，是下一次的n，差和减数 
	if(n==0)return 1;
	if(i==1)return 1;//用分解思想这种更好，分解1只用一种方式 
//或者if(i==0)return 0; 用减法思想这种更好，相当于这个数没有分解出更多方式 
	if(n>=i)return takeapart(n-i,i)+takeapart(n,i-1);//n可以连续减去i和不用i做减数 
	if(n<i) return takeapart(n,n);
///也可以是if(n<i) return takeapart(n,i-1);直到i减小到等于n 
}
//5 i=5,5+f(0) i=4,4+f(1) i=3,f(2) i=2 2+f(3) i=1 1+f(4)

//5(5,5), 4+1(5,4), 3+2(5,3), 3+1+1, 2+2+1(5,2), 2+1+1+1, (5,1)1+1+1+1+1
//不要被前面几个例子迷惑，从(5,2)开始其实下次对n-i进行分解，
//最大因子是i，不能超过i, 前面几个例子最大因数是n-i而不是i，是因为i+i大于n了
//也就是这次的n-i<x下次的i 
// 分解4，从1开始 分解3从2开始 分解 
//i是从大到小，如果n-i小于i，那么n-i和i都没经历过，如果n-i大于i，说明n-i分解过 
int main(){
	int n;
	while(cin>>n){
	cout<<takeapart(n,n)<<endl;	
	}
    return 0;
}

如下是之前分解因数的题，些许类似
1751:分解因数

#include <bits/stdc++.h>
int sum=0; 
using namespace std; 
void takeapart(int begin,int n){
	for(int i=begin;i<=n;i++){
		if(n%i==0&&n/i>=i){
			sum++;
			takeapart(i,n/i);
		}
		else //n/i<i{//说明n/i之前当过因子
		break; 
//		}
	}
}

int main(){
	int n;
	while(cin>>n){
		sum=1;
		takeapart(2,n);
	cout<<sum<<endl;	
	}
    return 0;
}

还有下面这段毫无厘头没有结果的 QWQ

#include <bits/stdc++.h>
int sum=0; 
using namespace std; 
void takeapart(int sub,int n){
	if(n==1||sub==1)sum++;
	for(int i=sub;i>=0;i--){//减数i从大到小 
//		if(n-i>=0&&n-i<=i){
			sum++;
//			takeapart(i,n-i);
//		}
//		else //n-i>i{//说明n-i之前当过因子
//		break; 
	if(n>i)takeapart(i,n-i);
	if(n<i)takeapart(n,n);
	if(n==i)sum++;
	}
}

int main(){
	int n;
	while(cin>>n){
		takeapart(n,n);
	cout<<sum<<endl;	
	}
    return 0;
}

//	for(int i=begin;i<=n;i++){
//		if(n%i==0&&n/i>i)takeapart(i,n/i);
//		if(n/i<i)
//		//18 1*18	 
//	}

希望学完动态规划之后能够清晰起来，I’ll come back!