最新消息:网站改版咯

整数的划分问题解法

算法 Yovae 2205浏览

整数的分划问题:
整数的划分算法解析
如,对于正整数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=n1+n2+……+nk   (ni≥1,i=1,2,……,k,k≥1)

1   ≤n1≤n2≤……≤nk   ≤   n

现在的问题是,对于给定的正整数n,编写算法打印所有划分。

用户从键盘输入 n (范围1~10

程序输出该整数的所有划分。写了半天终于写出来,发现对于递归方面我还得多练习一下。

 

 

/*
 *coding:Yovae(叶有为)         2011-5-9
 *website:http://yovae.com
 *
 *算法原理:
 *
 *sep(i,n)   1=<i<=n
 *1.当sep(i,n) n-i=0的时候直接输出n
 *2.当sep(i,n) n-i=1的时候输出i+1
 *3.当sep(i,n) n-i>1的时候可以划分为 i+sep(n-i-j,n-i) 1=<j<=n-i
*/

#include <stdio.h>

void sep(int i,int n)
{
    int count,j;
    n>=i?count=n-i:count=i-n;

	if(count>1)
	{
		for(j=count;j>=1;j--)
		{
			if(i>=j)        //避免重复 比如6=3+2和6=2+3
			{
				printf("%d+",i);
     		    if(i==1)    //i=1的时候 说明不能再往下递归 输出count个1
				{
				sep(1,count);
	        	return;
				}
		        else       //继续递归
				{
				sep(j,count);
				}
			}
		}
	}
	else if(count==1)
	{
		if(i==1&&count==1)
		printf("%d+%d",i,count);
		else printf("%d+%d,",i,count);
	}
	else if(count==0)
	{
		printf("%d,",i);
		
	}
}

int main()
{
	int n,i;
	scanf("%d",&n);
    for(i=n;i>=1;i--)
	{
		if(i==n)//仅仅为了格式
		{
			printf("%d\n",i);
		}
		else if(i==n-1)
		{
			printf("%d+1\n",i);
		}
		else
		{
		    sep(i,n);
		    printf("\n");
		}
	}
    return 0;
}

另一种解法:

#include <stdio.h>
#include <conio.h>
#define len 100


int d[len],n,total,k;
void sep(int p)
{
    int i,j;
    if(total==n)
	{
        for(j=0;j<k;j++)
		{
            printf("%d",d[j]);
            if(j<k-1)
                putchar('+');
            else
			{
                if(n-d[0]==k-1)
                    putchar('\n');
                else
                    printf(", ");
            }
        }
	}
    else
	{
        for(i=p;i>=1;i--)
		{
            if(i+total<=n)
			{
                d[k++]=i;
                total+=i;
                sep(i);
            }
		}
	}
    total-=d[k-1];
    k--;
}

int main(void)
{
 
	scanf("%d",&n)==1;
    total=k=0;
    sep(n);
    return 0;
}

转载请注明:Yovae Studio » 整数的划分问题解法