自然数的拆分.txt

解决排列组合问题的通用算法,自然数得拆分,求最大公约数的算法

/*
自然数拆分

	自然数(这里说的自然数不包括0，可能和现在的标准有冲突，下同)拆分是一个经典问题，
	意思是将一个自然数拆分为多个自然数之和。其基本算法是递归。例如5的拆分，可以化
	成1+(4的拆分)，2+(3的拆分)。为了保证不重复，我们要求拆分后的序列是不减的，及后
	项不小于前项。
*/
#include <stdio.h>
#include <string.h>

long res[1024],Total;

void fen(long n, long m)//n是需要拆分的数，m是拆分的进度。
{
  long rest;
  for(long i=1;i<=n;i++)//从1开始尝试拆分。
  {
    if(i>=res[m-1])//拆分的数大于或等于前一个，保证不重复。(第一个是0，虚拟的，不计入结果)
    {
      res[m]=i;//将这个数计入结果中。
      rest=n-i;//剩下的数是n-i。
      //如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。
      if(rest==0&&m>1)
      {
        Total++;
        printf("%ld\t",Total);
        for(long j=1;j<=m;j++)
        {
          printf("%ld ",res[j]);
        }
        printf("\n");
      }
      else
      {
        fen(rest,m+1);//否则将剩下的数进行进度为m+1拆分。
      }
      res[m]=0;//取消本次结果，进行下一次拆分。
    }
  }
}

int main()
{
  long n;
  printf("Input n:");
  scanf("%ld",&n);
  memset(res,0,sizeof(res));
  Total=0;
  fen(n,1);
  return 0;
}