整数分划(整数划分)

什么是整数分划(整数划分)


给定一个正整数 n , 一个由 r 个正整数组成的数组 λ = ( x1 , x2, . . . . , xr) 如果满足
x1 + x2 + ··· + xr = n 且 x1 ≥ x2 ≥ ··· ≥ xr ≥ 1,
就称数组 λ 是 n 的一个分划。n 的所有不同的分划的个数记作 p(n)。
比如说 4 的分划 p(4) = 4 :
4 = 4 ;
4 = 3 + 1 ;
4 = 2 + 2 ;
4 = 2 + 1 + 1 ;
4 = 1 + 1 + 1 + 1 ;
我们可以像字典给单词排顺序一样给 n 的所有分划排一个顺序:对于 n 的两个不同的分划 λ = ( x1 , x2, . . . . , xr)
和 μ = ( y1 , y2, . . . . , ys),如果 λ 的 “首字母” x1 比 μ 的 “首字母” y1
大,就规定在字典序下 λ 比 μ 大,反之则规定 μ 比 λ 大。如果 x1 = y1 ,那么就比较它们的下一个 “字母” x2 和 y2 . .
. . 这样继续下去,直到 λ 和 μ 在某一个位置上分出大小,根据这个位置上的大小关系来定义 λ 和 μ
之间的大小关系。在上面的例子中,我们就是按照字典序依次排列的 4 的分划。显然,( n ) 是所有分划中最大的,而 ( 1 , 1 , . . .
, 1) 则是所有分划中最小的。大家可以看到,这个比较 n 的分划的大小的规则和 C 语言比较字符串大小的规则是一样的。

p(n) 的值是多少?


有关 p(n) 的等式有很多,但是至今没有找到一个通项公式。由于 p(n) 在数论中的重要地位,因此大规模计算 p(n) 的值并从中发现规律,得出数学猜测就成为一个很重要的研究手段。
通常的递归法其实是最糟糕的办法,因此几乎不用(很小的 n 才用)。在计算机代数软件中广泛使用的办法主要有两种:
1. 基于欧拉五角数定理的递推方法。它可以把时间复杂度降低为 O( n^(1.5) ),但是它仍然要计算大量的中间结果(对所有小于 n 的 m 都要计算 p(m)),因此适合 n 是中等规模的情形。
2. 基于 Hardy - Ramanujan - Rademacher 等式的方法。HRR 等式是数论中最重要的等式之一,像 Riemann -
zeta 函数一样,它把数论中许多深刻的现象融合在一个等式内。HRR 等式给出的级数收敛到 p(n) 的速度很快 (第一项就是 p(n)
的渐进估计),因此对很大的 n ,基于 HRR 等式的算法是目前唯一的途径。
编辑本段怎样顺序打印输出一个整数的全部分划?
如果你在百度上搜索的话,会看到所有人都在使用递归的方法。这方法很直观,但是很不幸,效率也非常的低下。还记得 Fibonacci 数列吗 F(n) 吗? p(n) 和 F(n) 很类似:
1 . 它们都以指数的速度增长。
2. 如果你按照递推公式进行递归计算,会导致大量的函数调用和大量的重复计算并占用大量的空间。

实际上打印分划的算法十分的简单(按照逆字典打印的话绍复杂一点),代码如下:

void print_partition(int n)
{
  int i = 1;
  int m = 1;
  int h = 1;
  int t, r;
  int a[n + 1];

  for (; i < n + 1; ++i) a[i] = 1;
  a[1] = n;
  printf("%d \n", a[1]);

  while (a[1] != 1)
  {
    if (a[h] == 2)
    {
      a[h--]--;
      m++;
    }
    else
    {
      r = --a[h];
      t = m - h + 1;

      while (t >= r)
      {
        a[++h] = r;
        t -= r;
      }
      if (t == 0) m = h;
      else m = h + 1;
      if (t >= 2) a[++h] = t;
    }
    for (i = 1; i < m + 1; i++)
      printf("%d ", a[i]);
    printf("\n");
  }
}

为了便于在百科的网页中阅读,我加进去不少空白,所以如果你直接拷贝的话代码的缩进效果可能会不大好。:P 这也许是国内网页中最先出现的非递归的程序实现,其实这个算法在 Knuth 的《计算机程序设计艺术》第四卷组合算法中已经收录了。
算法想法很简单:这里的 h 代表最后一个大于等于 2 的元素的下标,(申请了 n + 1 的空间,a[ 0 ] 空着,a [ 1 ] 初始化为 n
,其他的全部初始化为 1), m 代表当前的分划的长度。每一次循环对当前的分划在尾部进行调整,调整为在字典序下的下一个分划,以 a[ 1 ] =
1 为循环结束的条件。
这个程序的好处很多:
1. 没有任何函数的递归调用,我们只是在不停的循环。
2. 整个过程全部在一个固定的长度为 n + 1 的数组上操作,再加上几个辅助变量,占用空间很少。
3. 不必担心整数溢出的问题。尽管 p(n) 增长的很快,但是我们使用的所有变量都不超过 n 。
4. 通过设置初始状态,你可以从某个固定的分划处开始打印,打印完以后你就知道这个分划在字典序下 “排行老几” ,这一点是递归方法做不到的。
5. 给定一个参数 K ,我们可以只打印排在第 K 位上的分划(在程序中再设置一个计数器即可),递归做不到这一点。
有道是 “天下程序一大抄”。希望这个程序能够帮助大家 “抛弃” “低级趣味” 的递归算法。

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

标签:C++

已有 4 条评论

  1. 匿名 匿名

    技术博呀!好啊,支持!肯定支持!

  2. 博主更倾向于分析算法?
    要么参加过奥赛,要么软件设计大赛....

    1. 奥赛没有,软件比赛倒是有...
      PS:你的主题好简洁华丽哦.看着真舒服

      1. 奥赛和软件比赛都差不多~
        欢迎围观,呵呵

添加新评论