【蓝桥杯】【算法】整数的分划问题

系统管理员 2022-10-25 04:41 132阅读 0赞

整数的分划问题。  
如，对于正整数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+1

【注意】对于一个正整数n的分划，就是把n表示成正整数之和的表达式。主要，分划与顺序无关，例如6=5+1和6=1+5被认为是同一种分划。

现在的问题是，对于给定的正整数n,编写算法打印所有划分。  
用户从键盘输入 n

1.  打印所有划分（n 范围1~10）
2.  只打印种类（n 范围1~999）

### 1. 打印所有划分 ###

#include <iostream>
    using namespace std; 
    int arr[11];
    long long sum_num=0;
    
    int min(int a, int b)
    { 
    	return a>b ? b : a;
    }
    
    // 
    void f(int n, int fn, int step)
    { 
    	if(n==0) 
    	{ 
    		for(int i=0; i<step; i++)
    		{ 
    			cout << arr[i] << " ";
    		} 
    		cout << endl;
    		sum_num++;
    		return ;
    	}
    	for(int i=min(n,fn); i>0; i--)
    	{ 
    		arr[step] = i;
    		f(n-i, i, step+1);
    	}
    }
    
    int main()
    { 
    	int n;
    	cout << "请输入数字："; 
    	cin >> n;
    	//1. 寻找所有情况，并打印 
    	cout << endl << "所有情况如下：" << endl;
    	f(n, n, 0);
    	cout << endl << "共有" << sum_num << "种" << endl; 	 
    	return 0;
    }

### 2. 只打印种类 ###

#include <iostream>
    using namespace std; 
    long long book[1000][1000] = { 0};
    
    int min(int a, int b)
    { 
    	return a>b ? b : a;
    }
    
    //
    long long f2(int n, int fn, int step)
    { 
    	int minnfn = min(n,fn);
    	
    	if(book[n][fn]!=0) return book[n][fn];
    	
    	if(n==0) 
    	{ 
    		return 1;
    	}
    	
    	long long sum=0;
    	for(int i=minnfn; i>0; i--)
    	{ 
    		sum += f2(n-i, i, step+1);
    	}
    	
    	book[n][fn] = sum;
    	return sum;
    } 
    
    int main()
    { 
    	int n;
    	cout << "请输入数字："; 
    	cin >> n;
    	
    	//2. 只寻找种类数
    	cout << f2(n, n, 0) << endl;
    	 
    	return 0;
    }