正整数分解算法

问题：将以正整数n表示成一系列正整数之和. n=n1+n2+n3+...+nk (n1>=n2>=n3>=nk>=1, k>=1)这就是正整数n的一个划分，正整数n不同的划分个数称为正整数n的划分数, 记作p(n)例如：6 有如下11种划分则p(6)=116;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;则求任意正整数的划分数p(n).

1. c改编的

class Int
{
private int n;
  private int[] a;
  public int cnt;
  public Int(int x)
  {
    n = x;
    cnt = 0;
    a = new int[100];
  }

  public void outPut(int m)
  {
    for(int i=0;i        System.out.print(a[i] + "+");
    cnt++;
    System.out.println();
  }

  public void fenjie(int n,int m)
  {
    int i;
    if(n==1)
        outPut(m);
    else
        for(i=n-1;i>=1;i--)
        if(m==0||i<=a[m-1])
        {
          a[m]=i;
          fenjie(n-i,m+1);
        }
  }

  public static void main(String[] args)
  {
    int x = 7;
    Int i = new Int(x);
    i.fenjie(x,0);
    System.out.println((x-1) + "的排列共有" + i.cnt + "种！");
  }
}

 

 

2.用递归解决，关键是上层函数的计算结果要保留到下层函数中。

CODE:

public class SplitInt
{
   static int cnt=1;
   //hs:上层函数已经分解完毕的数字串;m:上层函数分解完毕的数字;n:本层函数正在分解的数字
   //例如m=2,n=3,表示上层函数已经把5这个数字分解出2了，把5-2=3这个数字传给本层分解
   void split(String hs,int m,int n)
   {
       for(int i=m;i<=n/2;i++)
       {
           split("+"+i+hs,i,n-i);
           System.out.println((cnt++)+":"+(n-i)+"+"+i+hs);
       }
   };
   public static void main(String[] args)
   {
       int num=6;
       new SplitInt().split("",1,num);
   }
}

 

结果如下:
1:1+1+1+1+1+1
2:2+1+1+1+1
3:3+1+1+1
4:2+2+1+1
5:4+1+1
6:3+2+1
7:5+1
8:2+2+2
9:4+2
10:3+3
这个代码的特点是代码行少，简单。但是理解起来可能有点复杂。