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

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一下。。。

仰望天上的光

#include<stdio.h>
#include<stdlib.h>
#define N 1000
//存放划分出来的整数
//vec[0]为要划分的整数
int vec[N];

void work();
void getPartition(int n, int pos);
void print(int pos);
int main(){
        while(scanf("%d",vec)!=EOF) work();
}

void work(){
        getPartition(vec[0],1);
}
void getPartition(int n,int pos){
        if(n>0){
                int i;
                for(i=min(n,vec[pos-1]);i>0;--i){
                        vec[pos]=i;
                        getPartition(n-i,pos+1);
                }
        }
        else print(pos);
}

void print (int pos){
        int i;
        printf("%d=%d",vec[0],vec[1]);
        for(i=2;i<pos;++i) printf("+%d",vec[i]);
        printf("\n");
}

仰望天上的光

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

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:}