算法每日一题（七）——____递归与分治
问题：将一个整数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年蓝点杯的选拔赛试题，大家可以好好研究下。
本帖最后由 风扫地 于 2011-7-10 13:56 编辑
占楼。。try一下。。。 #include<stdio.h>
#include<stdlib.h>
#define N 1000
//存放划分出来的整数
//vec为要划分的整数
int vec;
void work();
void getPartition(int n, int pos);
void print(int pos);
int main(){
while(scanf("%d",vec)!=EOF) work();
}
void work(){
getPartition(vec,1);
}
void getPartition(int n,int pos){
if(n>0){
int i;
for(i=min(n,vec);i>0;--i){
vec=i;
getPartition(n-i,pos+1);
}
}
else print(pos);
}
void print (int pos){
int i;
printf("%d=%d",vec,vec);
for(i=2;i<pos;++i) printf("+%d",vec);
printf("\n");
} 。。。效率低了，没记录重复出现的子问题的解。 仰望天上的光 发表于 2011-7-10 16:13 static/image/common/back.gif
error C2065: 'min' : undeclared identifier错误提示，请检查下
加上min的声明和实现
int main(int a, int b){return a<b?a:b;}即可。 {:1_1:}
页:
[1]