经典算法:整数划分问题

蓝飞 蓝飞 | 时间:2012-12-12, Wed | 18,264 views
编程算法 

整数划分问题(算法分析与设计 P12):将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分:

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

由于将思路写作注释更方便理解,就不再在前面赘述了,给出代码及思路如下:

#include<stdio.h>

int list[255];

// num: 要分割的原始数字, n: 当前要分割的数字, k: 已经分割出的数量, sum: 已分割出的数字之和
void split(int num, int n = 0, int k = 0, int sum = 0){
	// 如果当前要分割的数字未传入,则当前分割的数字即为要分割的原始数字,减少传入参数数量
	if(n == 0){
		n =  num;
	}
	// 如果已分割的数字之和等于要分割的原始数字,即分割完毕
	if(sum + n == num){
		// 将最后一个数字存入数组
		list[k] = n;
		// 判断已分割的数字是否后面小于前面,防止重复
		bool flag = true;
		// 暂时未想到更好办法去除重复项,每次都要遍历数组,性能较低
		for(int i = 1; i <= k; ++i){
			if(list[i] > list[i - 1]){
				flag = false;
			}
		}
		// 如果数组合法,则输出
		if(flag){
			printf("%d", list[0]);
			for(int i = 1; i <= k; ++i){
				printf("+%d", list[i]);
			}
			printf("\n");
		}
	}
	// 从大到小进行分割
	for(int i = 1; i < n; ++i){
		// 分割出的数字存入数组
		list[k] = n - i;
		// 分割剩下的数字继续分割
		split(num, i, k + 1, sum + n - i);
	}
}

int main(){
	int n;
	while(~scanf("%d", &n)){
		split(n);
	}
	return 0;
}

感谢@夜尽--天明,偶得优化代码及思路如下:

#include<stdio.h>

int list[255];

void split(int n, int m = 0){
	int i;
	// 如果分割完毕
	if(n == 0){
		// 遍历输出数组
		for(i = 0; i < m; ++i){
			printf("%d ", list[i]);
		}
		printf("\n");
		return;
	}
	// 由大到小进行分割
	for(i = n; i > 0; --i){
		// 如果未分割或当期分割的数字不大于上一个分割的数字
		if(m == 0 || i <= list[m - 1]){
			// 将分割的数字存入数组
			list[m] = i;
			// 分割剩下的数字
			split(n - i, m + 1);
		}
	}
}

int main(){
	int n;
	while(~scanf("%d", &n)){
		split(n);
	}
	return 0;
}

于2013年5月2日22点温习算法,重写代码如下:

#include<stdio.h>

int list[100];
int last;

int min(int a, int b){
	return a > b ? b : a;
}

void split(int n, int max, int k = 0){
	if(n == 0){
		if(last != list[0]){
			if(last > 0){
				printf("\n");
			}
			last = list[0];
		}else{
			printf(" ");
		}
		for(int i = 0; i < k; ++i){
			printf("%d", list[i]);
			if(i < k - 1){
				printf("+");
			}
		}
		return;
	}
	for(int i = max; i > 0; --i){
		list[k] = i;
		split(n - i, min(n - i, min(i, max)), k + 1);
	}
}

int main(){
	int n;
	while(~scanf("%d", &n)){
		split(n, n);
	}
	return 0;
}
如需转载请注明出处:蓝飞技术部落格

6 条评论 »

  1. 你自己做的 好漂亮!

  2. 做的很不错,文章各方面写的也很好,原创永远经典~~
    能加个友情链接吗?你看看我的www.itcxy.com

    1. 谢谢~
      不过因为最近友链越来越多,所以不得不做个限制,PR3以上的才做,真是不好意思了。。

      1. 不知道博主是否愿意加个好友,有问题想请教~虽然我工作了 但时间有限,有些东西没时间研究,想问问关于sina SAE的事情

        1. 没问题呀,把你的联系方式私信给我咯?不过最近要期末考试了,还有六级考试,所以可能比较少在线哦。