算法每日一题（七）——____递归与分治

LNH_Sniper

问题：将一个整数n表示成一系列的正整数之和：
         n = n1+n2+n3+n4+......+nk( n1>=n2>=n3>=nk>=1,k>=1)
被称作正整数n的一个划分。一个正整数n可能存在着不同的划分，例如正整数6的全部的划分为：
6 = 6
6 = 5 + 1
6 = 4 + 2        6 = 4 + 1 + 1
6 = 3 + 3        6 = 3 + 2 + 1   6 = 3 + 1 + 1 + 1
6 = 2 + 2 + 2   6 = 2 +2 + 1 + 1     6 = 2 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 1 + 1

提示：本题应用到分治与递归的思想，这是一种占有重要地位的算法思想，无论是问题的抽象，还是对逻辑理解的深入。
同时与本题同类型的是2011年蓝点杯的选拔赛试题，大家可以好好研究下。

风扫地

占楼。。try一下。。。

仰望天上的光

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define N 1000
   
4. //存放划分出来的整数
   
5. //vec[0]为要划分的整数
   
6. int vec[N];
   
7. 
   
8. void work();
   
9. void getPartition(int n, int pos);
   
10. void print(int pos);
    
11. int main(){
    
12.         while(scanf("%d",vec)!=EOF) work();
    
13. }
    
14. 
    
15. void work(){
    
16.         getPartition(vec[0],1);
    
17. }
    
18. void getPartition(int n,int pos){
    
19.         if(n>0){
    
20.                 int i;
    
21.                 for(i=min(n,vec[pos-1]);i>0;--i){
    
22.                         vec[pos]=i;
    
23.                         getPartition(n-i,pos+1);
    
24.                 }
    
25.         }
    
26.         else print(pos);
    
27. }
    
28. 
    
29. void print (int pos){
    
30.         int i;
    
31.         printf("%d=%d",vec[0],vec[1]);
    
32.         for(i=2;i<pos;++i) printf("+%d",vec[i]);
    
33.         printf("\n");
    
34. }

复制代码

仰望天上的光

。。。效率低了，没记录重复出现的子问题的解。

LNH_Sniper

仰望天上的光 发表于 2011-7-10 16:13

                               
登录/注册后可看大图

error C2065: 'min' : undeclared identifier  错误提示，请检查下

LNH_Sniper

仰望天上的光

加上min的声明和实现
int main(int a, int b){return a<b?a:b;}即可。

8938

{:1_1:}