『每日一题 2012-02-13』整数划分问题

问题描述：

对于正整数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,编写算法打印所有划分。

算法实现：

可以求出具体划分方式

#include <stdio.h>
#define MAX 100
int d[MAX]; /* 用来存放分解结果 */

void decompose(int m, int n, int k); /* 将m分解为不大于n的组成数，k>=0是项号 */

int main()
{
    int n;
    printf("input n:");
    scanf("%d", &n);
	decompose(n, n, 0);
    return 0;
}

void decompose(int m, int n,int k)
{
    int i;
	
    if (m == 0) 
	{ /* 当m为0时，得到一个划分，将分解结果输出 */
        printf("%d", d[0]);
        for (i=1; i<k; i++)
            printf("+%d", d[i]);
        for (i=1; i< k; i++) /* for + if 处理输出格式 */
            if (d[i] != 1)
                break;
		if (i == k) 
			printf("\n");
		else
			printf(", ");
		return;
    }
    for (i=(m<n?m:n); i>0; i--) 
	{ /* 一次分解的几种可能分法 */
        if (i < n)
            d[k] = i;
        else
            d[k] = n;
        decompose(m-d[k], d[k], k+1); /* 递归调用使分解继续下去，直到得到一个划分 */
    }
}

#include <stdio.h>

int split(int n,int m);

int main()
{
	int n;
	printf("Please input an integer:\n");
	scanf("%d",&n);
	int sum=split(n,n);
	printf("%d\n",sum);
	return 0;
}
int split(int n,int m)
{
	if (1==n || 1==m)
	{
		return 1;
	}
	if (n==m)
	{
		return 1+split(n,m-1);
	}
	if (m>n)
	{
		split(n,n);
	}
	else
	{
		return split(n,m-1)+split(n-m,m);
	}
}

http://baike.baidu.com/view/4491942.htm

http://www.programfan.com/acm/show.asp?qid=57