`

C语言名题精选百则——排列,组合与集合

 
阅读更多

C语言名题精选百则——排列,组合与集合

 

尊重他人的劳动,支持原创

篇博文,D.S.Qiu将对《C语言名题精选百则——排列,组合和集合》进行整理推出,不光只是书上的名题,还会依据互联网的资源进行不断补充,加强。等全书各个章节都整理完,会做一个总汇。如果你有建议、批评或补充,请你不吝提出(email:gd.s.qiu@gmail.com,或者直接在本文末评论)。你的支持和鼓励(一个人整理真的很累,几度想放弃),我将渐行渐远!

《排列,组合和集合》主要是介绍了关于集合的子集以及子集字典排序,Gray码,排列以及字典排列,集合的分割,整数的分割等8个组合数学基本的问题,介绍比较繁复(废话比较多),只要看了就能理解(点击查看更多数组和字符串问题),相对简单,但是要是尽善进美还有待不断的挖掘。下一篇是《查找》(其实关于有序数组的一些问题),更多关注:http://dsqiu.iteye.com。

 

问题3.1列出所有子集(DIRECT.C )

 

编写一个程序,列出{1,2,3,…,n}这个集合的所有子集,包括空集合。

 

【说明】

列出一个集合的所有子集有很多做法,题目中并没有要求依某个特定的次序来排列, 因此是不难做出来的。

因为集合中一共有n个元素,所以总共就会有2^n子集;例如{1,2,3}有如下子集:

{}

{1} {2} {3}

{1,2} {1,3} {2,3}

{1,2,3}

 

【解答】

看到2^n,就想起了二进制数,可以使用二进制的第 i 位表示是否包含集合的第 i 个元素,如数字6的二进制形式是110,表示取集合的第2,3两个元素组成的子集。这样0~2^n -1的数字就可以表示全部子集,每一个数字代表一个子集,实现应该不难。

 

【问题实现】

 

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE   20
#define   LOOP       1

void main(void)
{
     char digit[MAXSIZE];
     int  i, j;
     int  n;
     char line[100];

     printf("\nDirect Generation of All Subsets of a Set");
     printf("\n=========================================");
     printf("\n\nNumber of Elements in the Given Set --> ");
     gets(line);
     n = atoi(line);

     /* ---You'd better check to see if n is too large--- */

     for (i = 0; i < n; i++)  /* clear all digits to 0    */
          digit[i] = '0';

     printf("\n{}");          /* outpout empty set {}     */
     while (LOOP) {
          for (i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++)
               ;              /* find first 0 position    */
          if (i == n)         /* if none, all pos. are 1  */
               break;         /* thus all elem. are in set*/
          else
               digit[i] = '1';/* now add one to this pos  */

          for (i = 0; i < n && digit[i] == '0'; i++)
               ;              /* find first 1 position    */
          printf("\n{%d", i+1);  /* show its numner and   */
          for (j = i + 1; j < n; j++) /* others           */
               if (digit[j] == '1')
                    printf(",%d", j + 1);
          printf("}");
     }
}
 

 

问题3.2列出所有子集——字典顺序(LEXICAL.C )

 

编写一个程序,用字典顺序(Lexical Order)把一个集合的所有子集找出来。

 

【说明】

如果不知道何谓字典顺序,在此作一个简单的说明。假设给定的集合有n个元素, 

{1,2,3,4}与{1,2,4}是两集合,它们前面的两个元素相同,但第三个不同,因此包含小的元 素的集合就排在前面。请回想一下,这与字符串的比较有什么不一样呢?完全相同,惟一 的差异,就是在集合中的元素要从小到大排好。

 

下面左边是n=3,右边是n=4的结果,如表3-1所示。

 

【解答】

事实上,这是一个十分简单的程序,除了空集合之外,最“小”的一个集合就是{1}再下一个就是包含1,而且再加上1的下一个元素(1+1=2)的集合,即{1,2};下一个元素 自然就是含有1与2,并且还有2的下一个元素(2+1=3)的集合{1,2,3}了。就这样一直到包含了所有元素为止,亦即{1,2,3,····,n}。下一个集合是谁?绝不是{1,2,3,…,n-1},.因为它 比{1,2,3,…,n}小,事实上应该是{1,2,3,…,n-2,n}。为什么呢?在{1,2,3,…,n-1,n}与 {1,2,3,…,n-2,n}之间,前n-2个元素完全相同,但是n-1<n,这不就证实了以上说法了吗?

由于以上原因,因此可以用一个数组set[]来存放集合的元素,一开始时set[0]=1,表 示{1};另外,用一个变量position,指出目前最右边的位置何在,在开始时自然就是1。 接下来,就陆续地产生下一个集合了。注意,目前集合中最右边的元素是set[position],如 果它的值比n小,那就表示还可以加进一个元素,就像是从{1,2,3}加上一个元素变成{1,2,3, 4}一样(n>4)。这倒是容易做,下一个元素在set[position+1],因此在那存入set[position+1] 这个值就行了;同时position也向右移一位。如果目前最右边元素set [position]已经是n, 因而不能再增加元素了。例如,当n=4时,如果有{1,3,4},那自然不能像前面所说的加入一个5。这时看最右边元素的位置,亦即position,是不是在第一位(如果n=6,而现在的集合是{6}),如果不在第一位,那就可以往回移一位,并且把那个位置的值加上1。例如, 如果现在有{1,3,4},而n=4;最右边(4)的位置不是在第一位,因而退回一位,等于是{1,3}; 但这是不对的,因为{1,3}比{1,3,4} “小”,要做得比{1,3,4}大,把3加上1而变成{1,4}就 行了。如果最右边(4)的位置是在第一位,那么程序就完成了。

 

【问题实现】

 

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE      20
#define   LOOP          1

void main(void)
{
     int  set[MAXSIZE];
     int  n, i;
     int  position;
     char line[100];

     printf("\nAll Possible Subsets Generation by Lexical Order");
     printf("\n================================================");
     printf("\n\nNumber of Elements in the Set --> ");
     gets(line);
     n = atoi(line);

     printf("\n{}");          /* the empty set            */
     position      = 0;       /* start from the 1st pos.  */
     set[position] = 1;       /* it gets a '1'            */
     while (LOOP) {           /* loop until done...       */
          printf("\n{%d", set[0]);  /* print one result   */
          for (i = 1; i <= position; i++)
               printf(",%d", set[i]);
          printf("}");

          if (set[position] < n) { /* this pos. can be inc*/
               set[position+1] = set[position] + 1; /* YES*/
               position++;    /* inc. next pos.           */
          }
          else if (position != 0)  /* NO, the 1st pos?    */
               set[--position]++;  /* backup and increase */
          else                /* NO, the 1st pos and can  */
               break;         /* not be inc. JOB DONE!    */
     }
}
 

 

【习题】

(1)有n个元素的集合的子集个数有2^n个,为什么前面所有的程序都不用一个for从 1数到2^n,而用break离开循环呢?(提示:想一想当n=50或100时会有什么后果)

(2)这个程序稍加改动就可以求出n个元素集合中元素个数不超过m(m<n)的所有子 集,请把它写出来。

(3)这个程序也可以改成求出n个元素的集合中元素个数恰好是m(m<n)的所有子 集,请把它写出来;请验查一下是否恰好有C(n,m)个?

注意:在编写(2)与(3)两题时,切不可以把所有子集都求出来,看看元素的个数, 如果在所要的范围,就提出该集合。这样的写法是不能接受的,虽然正确;应该在编写本 程序的概念上动动脑筋,只产生所要的集合,而不产生任何多余的部分才是正途。

(4)请写一个程序,把II个元素的集合的子集,用字典顺序的反顺序列出来(注意, 不能保存各个子集),然后用反顺序列出来,因为当n很大时内存就不够用了;试一试了解 上面所讲的观点,直接把程序列出来。

 

问题 3.3 产生 Gray 码(GRAYCODE.C )

 

编写一个程序,用Gray码(Gray Code)的顺序列出一个集合的所有子集。

 

【说明】

这个问题其实是在看有没有办法把Gray (人名)码用程序编写出来,有了Gray码, 找出对应的集合是件简单的事,问题3.2己经讲过了。

什么是Gray码? nbit的Gray码是一连串共有2^n个元素的数列,每一个元素都有nbit, 而且任何相邻的两个元素之间只有1bit的值不同。例如,3个bit的Gray码:

000 001 011 010 110 111 101 100

是一组Gray码,任何相邻两个元素都只有1bit值不同。但是,Gray码却并不是惟一的, 把它循环排列或是用反过来的顺序写,也会得到一组Gray码;比如说,如果把最后3个元 素放到最前面去,就会得到:

111 101 100 000 001 011 010 110

也是一组Gray码。

Gray码是一个很直观的几何意义,不妨把nbit看成是n度空间中一个点的坐标,因此 有2^n个坐标点,正好是n维空间中的一个正立方体的2^n个角落。如图3-1a所示,当n=2 时就是平方,是个正方形,如图3-1b所示,时就是个正立方体了。


 

如果能够从原点出发把每个顶点都走一次再回到原点,且每一个顶点都不重复,那么 沿途经过的点的坐标,就是一个Gray码。在图3-1a中,依箭头顺序,会得到00,10,11,01;对图3-1b而言,则是000,001,011,010,110,111,101,100。当然,用不同的走法,就会有不同的Gray码。例如在图3-1b中,000,100,101,011,111,110,010就是一个很好的例子。

看看下面n=4的Gray码:

0000 0001 0011 0010
0110 0111 0101 0100
1100 1101 1111 1110
1010 1011 1001 1000

仔细看看哪一个位置是从0变到1的,它与左右两个邻居的关系如何,或许就有办法写成程序了。或者,如图3-1b所示,沿途经过的方向有何变化,也可以编写出程序。这只是两点提 示,方法不止有这两个。

【解答】
把n=4的Gray码写出来:
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
如果位数是从右往左算,最右边一位是1,就会发现从第一个数到第二个数是第一位变了,第二个数到第三个数是第二位变了,把所有位置写下来有:
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
于是马上就可以归纳出:第奇数个的数(0000算是第0个)永远是改变上一个值最右边一位而得来的,可能是0变成1,也可能是1变成0;总之,变成了相反的值。
再看第偶数个的数(0011,0110,0101,1100,1111,1010,1001),它们是从改变上一个值的2,3,2,4,2,3,2这几位而来;再仔细看看,它们的邻位(1,2,1,3,1,2,1)值都是1,而且是从右边算过来的第一个1。因此:第偶数个的数(0000不计)的值是从改变上一个值中右边算来第一个1的左边邻位而得来。


 


不过,程序并不打算用递归的写法,不用递归也并不困难,看看前述的那两条规则就 行了。因为奇数位与偶数位是交错出现的,而且一开始最右边一位是第0位,也就是偶数位,所以可以用一个变量even,最先陚予其值为1,当处理完一位之后就把它改为1-even, 因为even的值就是1,0,1,0,…地变化;当值为1时,表示偶数位,值为0时是奇数位。如果目前是偶数位,就把最右边的位值改过来(0变成1, 1变成0);如果是奇数位,就从右向 左找,找出第一个值为1的位,把它左边的那一位的值改变。做完之后,把修订过的结果 显示出来。
为了程序编写方便,各个位的存放顺序,亦即digit[0],digit[1],…,digit[n-1]正好是第0 位(最左边),第1位,…,第n-1位(最左边),所以在显示位的值时要用相反的顺序,且在取出对应的元素来显示时,顺序也是相反的,仔细看看显示Gray码与集合用的for循环就 不难明白。程序的输出有两部分,左半是Gray码,右半是对应的集合。

【问题实现】
/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE         20
#define   YES             1
#define   LOOP            1

#define   FLIP_DIGIT(x)   x = ((x) == '0' ? '1' : '0')
#define   FLIP(x)         x = (1 - (x))

void main(void)
{
     char  digit[MAXSIZE];
     int   position[MAXSIZE];
     int   even;
     int   n;
     int   i, count = 0;
     char  line[100];

     printf("\nAll Subset Listing by Gray Code");
     printf("\n===============================");
     printf("\n\nNumber of Elements in Set Please --> ");
     gets(line);
     n = atoi(line);

     printf("\n");            /* initialization           */
     for (i = 0; i < n; i++) {
          digit[i] = '0';
          printf("0");
     }
     printf(" : {}\n");       /* the empty set            */

     even = YES;
     while (LOOP)  {
          if (even)           /* for even positions:0,2,..*/
               FLIP_DIGIT(digit[0]);  /* flip the 1st bit */
          else {              /* for odd positions...     */
               for (i = 0; i < n && digit[i] == '0'; i++)
                    ;         /* find the first 1 bit     */
               if (i == n-1) break; /* if it is the last..*/
               FLIP_DIGIT(digit[i+1]); /* NO, flip its nbr*/
          }
          for (count = 0, i = n - 1; i >= 0; i--) {
               printf("%c", digit[i]); /* print the bits  */
               if (digit[i] == '1')    /* and collect pos */
                    position[count++] = i + 1;
          }
          printf(" : {%d", position[count-1]);
          for (i = count - 2; i >= 0; i--) /* print pos   */
               printf(",%d", position[i]);
          printf("}\n");
          FLIP(even);         /* next will be odd(or even)*/
     }
}
 
【习题】
(1)记得河内之塔(Towers of Hanoi)这个游戏吗?有3个、4个与5个圆片,请用 手算方式找出被搬动的圆片号码与Gray码有什么关联。请写一个程序,用Gray码来解河内之塔这个问题,这样就有了不用递归、没有堆栈的直接解法了。
(2)找一本书看看何谓中国九连环游戏(Chinese Ring Puzzle),把各个环的移动顺序与环的号码写下来,这一组号码与Gray码有什么关系。于是,又有了一个不用递归来解九 连环游戏的解法。
(3)是否可以用递归的方法来写Gray码程序?会容易些吗?

问题3.4产生所有排列——旋转法(PERMUT_R.C)

编写一个程序,用旋转顺序(RotationOrder)列出n个元素的所有排列。

【说明】
旋转顺序并没有统一的定义,不过从下面4个元素的列法可以看出一点端倪。

在上面的例子中,4个元素经过上次旋转就会回到原来的样子,将前3个元素旋转一 次(见上面加框的地方),得到一个新的组合,这个组合旋转4次,又回到原样,因而再把前3个元素旋转一次;新组合旋转4次又还原,于是前3个元素再旋转一次,不过3个元 素经过3次旋转之后又会还原,所以这3个元素的前两个元素还要旋转一次,一直到两个元
素的旋转也还原了,所有组合完全显现出来了。因为n个元素旋转n次就还原,所以就旋转前n-1个元素,这就产生了 n(n-1)个排列;但是前n-1个元素经过n-1旋转之后又会还原,因此又得旋转前n-2个元素,于是就有了n(n-1)(n-2)个排列。继续这样做,不就一共产生出n!个不同的排列了吗?
注意,要检查有没有还原成原样不必大动手脚,因为开始时是1234…n,所以只要n回到第n位,就表示这n个元素旋转了 n次;同理,n-1回到第n-1位,表示前n-1个元素旋转了 n-1次后还原;依此类推,当i回到第i位时,就是前i位被旋转了 i次后还原。但重要的是,这里是以大旋转来控制小旋转的,也就是说,n次n个元素的旋转之后,接着是一次n-1个元素的旋转;n-1次n-1个元素的旋转之后,接着是一次n-2个元素的旋转;......,i次i个元素的旋转之后,是一次i-1个元素的旋转。要如何把这个概念化成程序呢?请熟悉上面的例子,有可能的话,不妨试一试5个元素;所有的提示都讲过了,等全然明白以后,把程序编写出来。

【解答】
回想一下在问题说明中提过的n个元素的排列,如果从1,2,3,…,n起旋转,n次之后就 会还原;换句话说,可以测试第n位,看它是否是n就知道还原了没有。如果还原了,旋 转一次前n-1位,如果又还原了,就旋转前n-2位等;用p表示目前要旋转的是前p位, 如程序12-4所示。

【程序】

程序12-4

while (还有位数可以旋转){
p=第n位;
旋转1到第p位;
while (第p位等于p而且p至少是第二位){
P--;
旋转1到第p位;
}
}
大循环是用来掌握整个n位的旋转的,所以在大循环里p就是第n位的位置;经过旋 转之后到达内循环,在内循环中先看看第p位是不是p,如果是,就表示还原了,因为把p减去1,接着旋转时就是前p-i位了,再次旋转之后很可能又还原,因此p又向左移了一 位,一直到p到达第一位为止,这时就无法左移,程序自然就结束了。不过,也有可能到某个p经过旋转之后并没有还原,于是又再度回到大循环,开始大旋转。
例如,如果在大循环中经过旋转后得到43125,因为第5位是5,所以大循环还原;进入内循环之后,就进行前4位的旋转,得到31245,不过第4位等于4,因此还不能离开内 循环;下一次是前3个元素的旋转,得到12345;这一次第3位是3,仍然不能离开,因此开始前两位的旋转,得到21345。终于第2位不是2,于是离开内循环而进入大循环,因此 大循环就会产生下一个排列,也就是52134,45213,34521,13452,21345;现在第5位还 原,......。
程序PERMUT_R.C就是用这个方法写成的;注意,C语言的数组是从0算起的,因此 第i位,脚码就是i-1,而不是i。程序中的变量position,就是上面的p,于是position值 是0〜n-1之间。另外,为了方便,ROTATE是定成一个集体指令而非函数,当然写成函数亦无不可,但是在执行时间上却不一定快速。

【问题实现】
#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE   20
#define   ROTATE(p) {  int  i, temp;              \
                       temp = perm[p];            \
                       for (i = p-1; i >= 0; i--) \
                            perm[i+1] = perm[i];  \
                       perm[0] = temp;            \
                    }

void main(void)
{
     int  perm[MAXSIZE];
     int  position;
     int  n;
     int  i;
     char line[100];

     printf("\nPermutation by Rotation Method");
     printf("\n==============================");
     printf("\n\nNumber of Elements --> ");
     gets(line);
     n = atoi(line);

     for (i = 0; i < n; i++)  /* initialize to 1,2,...,n  */
          perm[i] = i + 1;

     position = n - 1;           
     while (position != 0) {  /* if still have positions..*/
          printf("\n");       /* display result           */
          for (i = 0; i < n; i++)
               printf("%d ", perm[i]);

          position = n - 1;   /* starts from the last pos */
          ROTATE(position);   /* rotate them.             */
          while (perm[position]==position+1 && position!=0) {
               position--;    /* if last pos are equal and*/
               ROTATE(position); /* not zero, rotate again*/
          }
     }
}
 
【习题】
(1)有没有办法把这个旋转法写成递归程序?试试看。
(2)程序中,小旋转都是以左边第一位为基准的,如果要求把所有的旋转都放到右边 去,程序要做什么样的改变?请把程序写出来。
(3)下面的方法是由GLangdon在1967年提出的,如程序12-5所示,请了解其操作方式,并且写成程序。

问题3.5产生所有排列——字典顺序(PERMU—LR C )

编写一个程序,用字典顺序列出n个元素的所有排列(Permutation)。

【说明】
下面是一个n=4,用字典顺序列出来的所有排列,一共为4!=24个。
1234 2134 3124 4123
1243 2143 3142 4132
1324 2314 3214 4213
1342 2341 3241 4231
1423 2413 3412 4312
1432 2431 3421 4321
字典顺序的先后是这样定义的,如果a1a2…an与b1b2…bn是n个元素的两个排列, 于是有 a1=b1,a2 =b2,…,ai =bi,但 ai+1<bi+1,就是说 a1a2 …an 在b1b2 …bn 的前面,或者说前者较“小”;注意自i+2个之后的各个元素是没有影响的。其实’这就是用来决定 字符串大小的方式。举例而言,2314与2341,前两个元素相同,但第三个为1<4,所以 2314在前,2341在后;同理,1234与4321相比,1234在前,4321在后。
如何产生字典顺序的排列呢?据Hall与Knuth的考证,200年(1812年)前Fischer 与Kruse在他们的一本书中就己经提过这样的方法了。从123…n开始,首先从右到左找 出第厂对满足ai<ai+1的ai与ai+1,于是从ai+1起在它右边的就是越来越小的;有了七之后, 再一次地从右到左查一次,找出第一个满足ai<aj的aj。接着把的各个元素k过来
排,就是字典顺序的下一个了。下面来看看如何找出153642的下一个:从右到左第一组 满足ai<ai+1的是3与6,所ai就是3。接着从右到左去找第一个aj ,使得ai<aj则是4(3<4=;最后把3与4之间的元素反过来排,因此得到154632,这就是结果。
看另一个递归的做法,先看上面4!=24个排列的第一行,它们的第一个元素都是1,第一行最末一个是以1起头,用字典顺序排出来的最后一个,自然是1432。事实上,如果 是n个元素的排列,应该会想到最后一个应该是1n(n-1)…432。下一行是2开头,把n(n-1)…432中最小的一个与1互换,得到2n(n-1)…431,但这绝对不是1n(n-1)…432的下一个,不过如果把后面的n-1个元素反过来排,就会得到2134…(n-1)n,还是正确的顺序,于是就进入第二行。第二行的最末应该是2n(n-1)-431,但1已经在第1行出现过了,所以把倒数第二个 元素(自然是3)与2互换,得到3n(n-l)-421,再把后面的n-1个元素反过来排,有3124…(n-1)n是不是第三行的第一个呢?再做第三行,那是3n(n-l)…421,因为1与2已经在第一个位置出现过,这一次把4 换到头上去,得到4n(n-l)…321,再反过来排,就是4123…(n-1)n,正好是第四行。于是就可以归纳出一个递归的做法了,从1234…n起,用一个递归的程序:

(1) i = n 。
(2)排到n的排列(递归的)。
(3)把第i位与第一位互换。
(4)把后面的n-1位反过来排。
(5) i减去1。
(6)回到第(2)步。
请把这个想法发展成一个递归的程序。

【解答】
先讲递归的做法,n个元素一共有II!个排列,而1〜n都有可能出现在第一个位置,因为要用字符串顺序来排,所以这n!个排列是以1开头的(n-1)!个在前,接着是以2开始的 (n-1)!个,…,最后是以n开头的(n-1)!个。就用以i开头的为例,i已经在第1位,自第2 位起到第n位止中不会有i,因此以i开始的字典顺序以i 1 2 3…(i-1) (i+1)…(n-1) n 起,而以in (n-1)…(i+1) (i-1)…32 1结束。如果用递归方式,以字典顺序来排n-l个 元素的程序,不过是把该(n-1)!排列(其中不含i)排出来,接在i的后面而已。
当以i起头的(n-1)!个排完后,如何产生以i+1起头,字典顺序的下一个呢?再套用上 面的说法,这一组(n-1)!个排列以(i+1) 1 2 3…(i-1) i (i+2)…n起,到(i+1) n (n-1)···(i+2)i(i-1)…321止。可以把i起头的最后一个中的i+1 (它在倒数第i位)与i互换, 因此得到:
(i+1k)n(n-l)…(i+2)i(i-1)…32 1
再把后面的n-1个元素反转:
(i+1) 1 2 3 …(i-1)i(i+2)…(n-1)n
这不就是(i+1)起头的第一个元素吗?
在写程序时要注意:因为要处理在后面的n-1个元素,所以用两个变量L与R来指出要 处理的部分;如果用perrnu[]数组来存放一个排列的话,那么程序的架构就如程序12-7所示。

【程序】

程序12-7
while (1) {
排列perm [L+1]到permu [R]的部分;
把 perm [ L ]与 perm [ i ]互换;
把perm [L+1]到perm [R]反过来排;
i--;
}
当然,这还缺少递归的终止条件(以上面来看是永运不会停止的);不过这很简单,当 递归调用时,若L到R之间至少有3个元素,就做下去,而当只有两个元素时就不必递归 调用了,此时接下来的两步正好就是两个元素的排列(两个元素的排列只有两种,一种是 输入,另一种是两个元素互换——反过来排)。由此,递归韹序就可以写出来,这就是程序 PERMU—LR.C。

【问题实现】
#include <stdio.h>
#include <stdlib.h>

#define  LOOP         1
#define  SWAP(a,b)    { int t; t = a; a = b; b = t; }
#define  REVERSE(a,b) { int i, j;                            \
                        for (i=(a), j=(b); i < j; i++, j--)  \
                             SWAP(perm[i], perm[j]);         \
                      }
#define  DISPLAY(n)   { int i;                               \
                        printf("\n");                        \
                        for (i = 0; i < n; i++)              \
                             printf("%d ", perm[i]);         \
                      }
                        
void  again(int  perm[], int L, int R)
{
     int  i = R;

     while (LOOP) {
          if (R - L + 1 > 2) {
               again(perm, L+1, R);
               DISPLAY(R);
          }
          if (i > L ) {
               SWAP(perm[L], perm[i]);
               REVERSE(L+1, R);
               DISPLAY(R);
               i--;
          }
          else
               break;
     }
}


void permut(int perm[], int n)
{
     int  i;

     for (i = 0; i < n; i++)
          perm[i] = i + 1;
     again(perm, 0, n-1);
}


#define    MAXSIZE   20

void main(void)
{
     int   perm[MAXSIZE];
     char  line[100];
     int   n;

     gets(line);
     n = atoi(line);
     permut(perm, n);
}
 
【习题】
(1)在递归程序中R的值永远不变,因为它可以定成外部变量,因此wdls()函数的 参数就变成只有一个L。请问R这个值是多少?接着请把程序的递归去掉,转换成非递归 的程序。
(2)请证明Fischer-Kruse的方法是正确的;也就是说,如果己知一个排列,然后从 右向左找出一个决满足ai<ai+1;再从右向左找出一个j,使得ai<aj(如果找不出来又如 何?),接着把ai〜aj的元素反过来排,这就是给定排列在字典顺序中的下一个。
(3)本题的顺序是以字典顺序从小到大排的,请修改Fischer-Kruse以及递归程序, 使它可以用反字典顺序排列。
(4)请把Fischer-Kruse方法写成非递归的形式。

问题3.6所有K个元素的子集(KSUBSET.C )

编写一个程序,把一个n个元素的集合{1,2,3,•••,n}中所有k个元素的子集用字典顺序 列出来。

【说明】

还记得列出所有子集的程序吗?问题3.2己经介绍了一个把所有子集用字典顺序列出来的例子,事实上,只要把那个例子的程序稍作修饰就可以做出这个问题的答案。
如果n=5,那么所有3个元素的子集用字典顺序来列就是
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
注意在每一个子集变到下一个子集时究竟是哪一个位置有所变动;另外,特别重要的是,每一个位置都有该位置的最大值。例如,第三位可以到5,第二位只能到4 (因为它到 5的话,第三位就不可能放3),而第一位(最左边)则是3;这些最大值可以用n (总元素个数)、k (子集的个数)以及每一个元素的位置算出来。
了解这些想法之后,程序就很好写了,不妨自己动动脑筋。

【解答】
先列出{1,2,3,4,5}中3个元素的所有子集:
{1,2,3}
{1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{1,4,5}
{2,3,4}
{2,3,5}
{2,4,5}
{3,4,5}
在幵始时是{1,2,3},接着会发现最右边的数逐渐增加,到n(=5)为止,然后它的左边位 数进1,右边的位数则从下一个值开始;这个动作就像是一个里程表,各个位数不断增加, 所不同的是在例子中,从左向右的位数永远保持从小到大的位数。
正因为如此,只需要掌握在什么时候哪一位该进位就行了。能够产生出来的集合中最 “大”的一个{3,4,5},最后一位是最大元素,左边一位是5-1=4,再左一位是4-1(=5-2); 依次类推,如果原来的集合有n个元素,要取出的是k个元素的集合,那么最“大”的集合就是:
{n-k+1,···,n-2,n-1,n}

因此最后一位的值只能变到n,之后就退回一位,但右边第二位只能变到n-1,
如果仔细看看上面的例子,不难发现如下事实:
(1)如果最后一位的值小于n,那么再加1的位置永远是最后一位。
(2)如果从右边算来,每一位都等于它的最大值(最右边是n,右边第二位是n-1,…), 那么再加1的位置是从右边往左边算,第一个小于极大值的位置。
以{2,3,4}为例,最右边一位(4)小于n=5,所以加1的位置是最后一位,因而得到{2,3,5};但倒数第二位却不是,所以倒数第二位加1,得到{2,4,5},之后,第一位不到它的极大值,所以第一位加1,得到{3,4,5},每一位都递归完,结束。
不过每次都要从右往左查是一件很麻烦的事,有没有别的办法直接定出要加1的是哪一位呢?很简单,不过又要进一步的思考而已,主要关键是第二点。做法是,使用一个 变量(position),它一开始时是k-1 (注意,C语言中的数组从零算起,而要求出k个元素 的所有子集),表示要加1的是第k位。在往后的工作中,如果第k位的值小于n, position 的值就维持在k-1,在这种情况下,被加1的永远是第k位。但是,若第k位的值已经到达了 n,就不能再加1 了,就把position减1,表示position左边那一位要加1。看起来有点奇怪,但是举个例子就不难明白。例如,n=5,k=3,现在有:
{1,3,4}
加了底线的地方就是position的位置,因为第k位小于n,自然position就在那,加了
1之后变成:
{1,3,5}
因此最后一位的值只能变到n,之后就退回一位,但右边第二位只能变到n-1,

【问题实现】
#include  <stdio.h>
#include  <stdlib.h>

#define   MAXSIZE    20
#define   LOOP        1

void main(void)
{
     int  set[MAXSIZE];
     int  n;
     int  k;
     int  position;
     int  i, j;
     char line[100];

     printf("\nAll k Elements Subsets from a n Elements Set");
     printf("\n============================================");
     printf("\n\nNumber of Elements in the Set --> ");
     gets(line);
     n = atoi(line);
     printf("\n\nNumber of Elements in Subset ---> ");
     gets(line);
     k = atoi(line);

     for (i = 0; i < k; i++)  /* initialize the subset to */
          set[i] = i + 1;     /* {1,2,3,...,k}            */
     printf("\n{%d", set[0]); /* display it               */
     for (j = 1; j < k; j++)
          printf(",%d", set[j]);
     printf("}");


     position = k - 1;        /* 'position' indicates the */
     while (LOOP) {           /* pos to be increased      */
          if (set[k-1] == n)  /* if last pos is full, then*/
               position--;    /* move position left       */
          else                /* or if not full, then the */
               position = k - 1; /* pos is always the last*/
          set[position]++;    /* so add one to the pos.   */
          for (i = position+1; i < k; i++) /* add inc. all*/
               set[i] = set[i-1] + 1; /* pos to its right */

          printf("\n{%d", set[0]); /* display it.         */
          for (j = 1; j < k; j++)
               printf(",%d", set[j]);
          printf("}");

          if (set[0] >= n-k+1) break; /* if 1st pos full  */
     }
}
 

【习题】
(1)请用每一次都从左向右地找出position的值的方式(也就是解答中的两个事实)来改写程序。
(2)请写一个程序,把一个有n个元素的集合的所有子集依元素个数从小到大,而相 同元素的子集用字典顺序排出来;以3个元素的集合来看,就是{},{1},{2},{3},{1,2},{1,3}, {2,3},{1,2,3}。
(3)如果a是一个有n个元素的集合的元素,请写一个程序,列出所有包含a,以及 所有不包含a,并且元素个数都有k个的子集;请问,这各有多少个?这个数与n、k之间 的关系如何?

问题3.7集合的所有分割方式(SETPART.C )

一个集合S的分割(Partition),就是把S分解成若千个子集S1,S2,…,Sp,(打不了下标,抱歉)使得S1∪S2∪…USp=S,但对任意两个不同的子集Si与Sj而言,Si∩Sj=∅,换句话说,集合
的分割,就是把该集合分解成若干相互分离的子集。举例而言,{1,2,3}的分割就有 {1},{2},{3}; {1,2},{3}; {1,3},{2}; {2,3},{1}; {1,2,3}这 5 种。编写一个程序,读入 n,列出{1,2,3,…,n}的所有分割方式。

【说明】
一般而言,不会直接对{1,2,3,…,n}这个集合操作;聪明的做法是记录下哪一个元素在 哪一个分割中,就以{1,2,3,4}为例,它的分割方式有下面的15种,如表3-2所示。


 
在上面的写法中,右边的四位数表示1,2,3,4在哪一个分割中。例如,1213表示1与3 在第一个分割,2在第二个,3在第三个,所以分割就是{1,3},{2},{3}。再看1212,它指出 1与3在第一个分割,2与4在第二个分割,因此分割本身就是{1,3},{2,4}。这个四位数就 当作该分割的编码(Code),只要能找出编码本身有什么性质,分割就可以从编码重建出来。
这个编码有一个特色,在分割中从{1,2,3,4}起,总是在第一个部分保持最长的分割, 而把余下来的元素放到第二个分割中,接着就按这种形式把可能的方式都列出来,再把大的分割切成较小的部分,一直到不能再切割为止。更重要的是,永远把1所在的分割定成第一个,所以四位数中1这个元素的编码值永远是1。再看2这个元素,它的编码值永远不会大过2,为什么会这样呢?如果2在第三个分割中,就会有:
{1,…}••• {2,…}•••
因此中间分割中的元素值都大于3,但是可以把{2,…}这个部分换到前面而成为:
{1,…}{2,…}•••
因此2就在第二个分割中;这样做是正确的,因为分割本身并无次序性。推广开来, 如果把分割中的元素从小到大排列,而且再把分割以第一个元素的顺序来排,那么i这个 元素的编码一定小于或等于i。
不但如此,还可以证明:第i个元素的编码是小于或等于1,2,3,…,i-1这几个元素的编码的极大值再加上1。证明本身并不难,因为i在它所在的分割中,如果不是排在第一个(见 4个元素时的{3,4}),就是排在第一个后面(见4个元素时的{2,3},或{2,3,4})。在前者,i 的编码如上述所讲的,最大就是i,不过|所在的分割最多只会排在{1,…},{2,…},…,{i-1,…} 后面,在这种情况下,1,2,…,i-1的编码 i 正好是1,2,…,i-1,只要其中有两个合二为一,1,2,…, i-1的编码值就会降低,所以i的编码值不能超过1,2,…,i-1的编码的极大值加上1。如果i 不是排在最前面,那么将i所在的分割中排在最前面的元素设为j,就一定小于或等于i-1。 由上面的说明,i的编码值是1,2,…,j-1的编码的极大值加上1;更重要的是,在j+1到i-1 之间的元素一定落在1,2,…,j所在的分割之一,但因为i与j在同一个分割中,所以i也就 是等于1到i-1的编码极大值再加上1 了。
用这个条件,就可以写一个很简单的程序了(建议是,把上面的说明彻底弄清楚之后 再动手,不必忙着写程序)。

【问题实现】
#include <stdio.h>
#include <stdlib.h>           /* for malloc()             */

#define  ALWAYS   1

void  display(int *, int);

void  set_partition(int n)
{
     int  *code, *maxi;       /* arrays for code[], maxi[]*/
     int  i, j;

     code = (int *) malloc(sizeof(int)*n); /* get memory  */
     maxi = (int *) malloc(sizeof(int)*n);

     for (i = 0; i < n; i++)  /* initialization           */
          code[i] = 1, maxi[i] = 2;

     while (ALWAYS) {         /* loop until done.         */
          display(code, n);   /* display one partition    */
          for (i = n-1; code[i] == maxi[i]; i--)
               ;              /* find next 'increasible'  */
          if (i > 0) {        /* found ?                  */
               code[i]++;     /* YES, update              */
               for (j = i + 1; j < n; j++) {
                    code[j] = 1; 
                    maxi[j] = maxi[i]+((code[i]==maxi[i]) ? 1 : 0);
               }
          }
          else                /* NOT FOUND, done.         */
               break;
     }
     free(code);
     free(maxi);
}


/* ------------------------------------------------------ */
/* FUNCTION  display :                                    */
/*    This function displays the code of the partition.   */
/* ------------------------------------------------------ */

void  display(int *code, int n)
{
     int  i;
   
     printf("\n");
     for (i = 0; i < n; i++)
          printf("%3d", *(code+i));
}


/* ------------------------------------------------------ */

void main(void)
{
     char  line[100];
     int   n;

     printf("\nSet Partition Program for {1,2,3,...,N}");
     printf("\n=======================================");
     printf("\n\nN Please --> ");
     gets(line);
     n = atoi(line);
     printf("\nCodes of Partitions.");
     printf("\ni-th position = j means i in partition j\n");
     set_partition(n);
}
 
问题3.8整数的所有不同分割数目(INTPART#.C )

所谓的整数的分割(Partition of an Integer),指的就是把一个正整数写成若干个正整数 的和,但这里只计较有多少种分解方式,而不计较它的内容。例如,4=3+1,2+2,2+1+1,1+1 +1+1,再加上自己,就一共有5种分割方式。编写一个程序,输入一个正整数,输出它有 多少种分割方式。

【说明】

以下是几点重要的提示:
(1)要把n进行分割,其实不完全只针对n,还要看分割中最大的值是什么。例如, 要把10进行分割,若在分割中最犬的值是6,亦即10=6+…,那么“…”的部分充其量的值是4而已,不仅如此,和还须等于4;因此,如果知道“…”,亦即4,有多少种分割方 式,也正是在分割10时,最大值为6的分割方式!
(2)应该分析一下,n这个输入值,与在分割中的极大值(如(1)中的6)之间有什 么联系,找出来,问题就解决了。
(3)不要忘了,递归是非常有效的武器。

【解答】
用p(n,m)表示在n的分割中极大值最多为m的分割数目,亦即分割具有n=m +…,n=m+m+…,n=m+m+m+…这一类的形式。于是n与m的关系不外子以下几种情况。
(1)m为1:因为n的分割中的极大值为1,而且分割中又完全是正整数,所以整个分割就都是1。以4为例,就是4=1+1+1+1。于是有p(n,1)=1。
(2) n为1:因为要分割的数本身就是1,这已经是正整数中最小的值了,所以不论 如何分割,也不论m为何值,1 一定小于m, p(1,m)=l。
这两点就构成了递归调用的终止条件。在递归程序中,永远记住要找出能够令递归终 止而返回结果或控制权的条件。
(1) n=m:也就是n的分割中,极大值不超过n的个数。当然,极大值为n的分割只 有一个,也就是它自己。换言之,在4的分割中,4=4就是极大值正好是n的情況• 除 7这一个之后,极大值就不可能为n 了,最多是n-1而已。因此求出n的分割中极大值是 n-1的分割个数,再加上n=n这一个分割,就是p(n,n)。换句话说,p(n,n) = 1+ p(n,n-1)。
(2) n<m:要把n分割,但极大值最大可以为m,而且m〉n,这是不可能的事,因 为把n分割时,在的情况下就已经是最大可能了。所以说,在n的分割中,如果要求 极大倌最多可以到ni(>n),这是不切实际的,因为分割中不可能出现n+1,n+2,…这些值。
换言之,p(n,m) = p(m,n)。

(3) n>m:这是最常见的可能性了。在n的分割中,如果极大值最大可以为m,那 么这不外乎分割中有一个或若干个m,或者是根本就没有m。比如,在4的分割中,说极大值最多可以到2,那么因为4=2+2=2+1+1=1+1+1+1,于是有m=2的就是2+2与2+1+1, 完全没有m=2的则是1+1+1+1。如果n的分割中根本没有m,那么它的个数不就与n的分割中最大可以到m-1的个数(亦即p(n,m-1))相同吗?如果n的分割中至少有一个m,亦 即n = m +…,(注意,…部分可能有m),于是n-m=…,所以…的部分正好是n-m的一个 分割,它的极大值最多可以到m;因为n-m的分割中极大值最多可以到m的有p(n-m,m) 个,再加上p(n,m-1),这就是所有的情况,亦即p(n,m)=p(n,m-1)+p(n-m,m)。
这样就把所有的可能性都考虑到了。在程序中,compute()函数对应着p(n,m),变量 number是n,maximum则是m。它就依上述的5个情况分析,并且递归调用自己来求值。
那么n的分割数目是多少呢?是p(n,n),这是说n的分割中极大值最多是n个数,自 然地n的分割中不可能有大于n的情况。由上述的第(3)点,用compute(n,n)就可以得到结果了。但是,求n的分割只用到n—个参数而已,为什么要那么麻烦地写成computeOiji) 的两个呢?所以写一个额外的函数int_part_no()来做这件工作,把这件琐事处理掉(想想看, 万一有一天在使用compute()时只给一个参数会有什么后果?)。

【问题实现】
unsigned long  compute(int, int);
unsigned long  int_part_no(int);

unsigned long  int_part_no(int n)
{
     return compute(n, n);    /* convert to another form */
}


unsigned long  compute(int number, int maximum)
{
     if (number == 1 || maximum == 1)
          return 1;
     else if (number < maximum)
          return compute(number, number);
     else if (number == maximum)
          return 1 + compute(number, maximum-1);
     else
          return compute(number,maximum-1) + 
                 compute(number-maximum,maximum);
}

/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>

void  main(void)
{
     int  n;
     char line[100];

     printf("\nNumber of partitions of an Integer");
     printf("\n==================================");
     printf("\n\nN --> ");
     gets(line);
     n = atoi(line);
     printf("\nThere are %lu partitions.", int_part_no(n));
}



【习题】
(1)请把这个程序改写成非递归的形式。
提示:可以用一个表格来做这件事,如table[n][m],就存放了 p(n,m)的值,这个表格的计 算次序如何?
(2)一个集合的分割,就是把该集合分解成若干个两两分离的非空集合,并且这些子 集的合集等于已知的集合。例如,{3,2,1}的分割有{1},{2},{3}; {1},{2,3}; {1,2},{3}; {1,3},{2}; {1,2,3}这3种.请写一个程序,读入集合的元素个数,输出这个集合会有多少 种不同的分割方式,这个数叫做Bell数。
提示:与例题一样,此处的集合分割中,分解成几个部分的数目是非常重要的,囚此分解 成1个,2个,…,到n个(假设集合有n个元素)部分的不同做法都知道了,加起 来就是所有的分割方式,想法与此处的程序大同小异。
(3)请问在程序中一共用了多少个加法,递归调用了多少次?为了要算p(n,m),有必 要求出所有p(i,j)的值吗?此地1<=i<=n,1<=j<=n。
(4)用G(n)表示在有n位的二进制数中没有相邻的两个1的二进制数个数。比如,当 n=3 时,000,001,010,011,100,101,110,111 这 8 个数中只有 000,001,010,100,101 这 5 个是没 有相邻为1的,故G⑶=5。请写一个程序,输入n,输出G(n)的值。
提示:不应该000…000〜111…111 一个个地测试,请试一试“分而治之”的策略,把n位二进制数分成两部分,分别处理这两部分,并且小心地合并。

问题3.9整数的分割方式(INTPART.C )
对于一个正整数n而言,它的一个分割(Partition),就是把n写成若干个正整数的和, 但不计较书写的顺序。编写一个程序,输入n,把n的所有分割显示出来。

【说明】

如果n=7,那么有如下的分割。


 
一共有12个,仔细观察在各个输出中前后两者的差异,并且自己做一做其他的结果(比 如n-5时有7个,n=6时有11个等),就不难写出程序了。

【解答】
把正整数分割成若干正整数的和并不是一个十分困难的问题。如果回头看问题说明中 把7分解的例子,就不难发现从上一个分割方式到下一个分割式中,永远是最右边或是旁 边的一连串1的位数有所改变。其实在问题说明中的排列方式,正是所谓的反字符串顺序, 就以4、3为例,它的下一个是多少?因为最右边位数的3还有可以分解的余地,但比3小 的下一个分解是2,3就分解成2+1,故7=4+3=4+2+1;到了 4+2+1之后,1自然不能分解 了,但1左边的2还可以,所以把2分解成1+1,故得到7=4+1+1+1。接着,下一个可以 再度分解的是4,4可以分解成3,因此7=3+x,后面的x是多少呢?自然它们的和是7-3=4, 但此地不能用4,因为在此之前己经用过了,而用比3小的才行,要比3小,那只有2, 7=3+2+2,于是接下来的是7=3+2+1+1,…。这就是解题的基本想法。
不过为了要把题目解得漂亮,要有进一步的、好的数据结构才行。为什么呢?因为在 分解成正整数的和时,可能会有很多重复的部分,特别是要分解的数很大时就更是如此。 10=4+3+3=3+2+2+2+1=…就是一个例子,因此用两个数组来做这件事。partition□中储存了 分解出来的、不同的正整数,而1111111[]则用来记录对应的整数的重复次数;以 10=3+2+2+1+1+1 为例,partition[]中依次为 3、2、1,而 mult[]中则是 1、2、3,因为 3 有 1次,2有两次,而1有3次,为了说明方便起见,不用partition[0]与mult[0]。
在开始时,如果要分解的数是n,那么partitionfl]就是n,而mult[1]为1,表示只出现 一次,接下来就要把上面所讲的观点转化成程序了。用part_no记录下n在目前一共分解成多少个不同的整数,依照上面的说法,可以分成两个部分来说:
(1)最后一个值不是1:就以25=5+4+4+3+3+3+3为例,partition[]依次为5,4,3,而 mult[]则是1,2,4;因为最后一个数(3)不是1,所以可以把它分离出来,减去1就是下一个 数(2=3-1):
25=5+4+4+3+3+3+(2+···)
但因为分离出来的是3,它的下一个较小的值是2,那么有多少个2呢?很简单,3/2=1 个2,所以partition[]变成5,4,3,2,mult[]则是1,2,3,1;但是3不能被2整除,还有剩余的 数(也就是商数,它必定小于2),所以就加在最后面,因此得到:
25=5+4+4+3+3+3+2+1
总而言之,如果partition[part_no],也就是最后一个数值不为1,就可以把它取一个出 来,叫做sum,表示取出之后必须要加上sum的值才能得到和为n。其次,下一个数要比
partition[part_noj小,亦即值为partition[part_no]-1,把这个值存到size中;这代表在分割中 的下一个值。但是要注意一点,当mult[part_no]为1时,取出这个值之后原来的数就没有
了(例如,在16=5+4+4+3中取了 3之后,3这个部分就不存在了),所以当mult[part_no] 不是1时,可以多一个数;但当mult[part_n0]为1时,则不能多一个数。
因为size代表下一个值,所以把它存到part_no所指出的下一个位置中,它能够重复多 少次呢?前面说过,sum/size次;但若size不能整除sum,多出来的余数部分就是一个新 的值。例如,对25而言,如果partition[]中是5,4,3,mult[]为1,2,4;于是sum为3,表示 从最后的4个3中取了一个3出来,size是2,因为比3小的下一个值是2。由于取了一个 3,故mult[]的新值为1,2,3,多出来的这个sum可以被size分成3/2=1组,所以partitionf ] 为5,4,3,2,mult[]则是1,2,3,1;不过正因为sum不能被size整除,还余1,所以这个1就 形成一个新的部分,把它加到分割中,有partition□为5,4,3,2,1, muh[]为1,2,3,1,1。但若 25=11+11+3, partition□为 11,3,mult[]Sl;因此 sum=3, size 是 2;但因为 3 被取出之后,
在原来分割中就不存在了,所以新产生的分割(sum/size)就像它原来的位置,即结果中 partition[]为 11,11,2,1,mult[]是 2,1,1。
(2)如果最后一个值是1:这些1 一定在最后面,也就是partition [part_ no],有多少个则是在mult[part_no]中,因为mult[part_no]指出有多少个1,因此也正是由1所构成的部 分的总和。因为1已经不能再分解了,所以在求下一个分解方式时,这些1都要去掉,而 下一个值是从最后的一个不是1的值中取一个出来,再减去1;于是sum就是 mult[part_no]+1,而 size 则是 partition [part_no-1]-1;为什么 sum 是 mult[part_no]+1,而不是mult[part_no]呢?原因是,sum是加上的值而凑成n用的,因为下一个可以用的值是 partition[part_no-1]-1,少了 1,所以就要在sum中多加一个1来弥补了。例如 14=4+3+3+1+1+1+1, partition[]是 4,3,1,mult[]为 1,2,4,自然 sum 为 4,但因为最后一个不是1而为2,所以取出来又少了 1,因此在sum中加上1变成1作弥补:
14 = 4 + 3 + 3 + 1 + 1 + 1 + 1 =4 + 3 + 3 + (4)
=4 + 3 + (2 + 1) + (4)
=4 + 3 + 2 + (5)
于是sum是5, size为2,其他工作就与上一点相同了,从sum/size求出sum可以用 size分成多少组,加上从上一个值中取出的一组,就一共有sum/size+1。于是新的partition[] 是 4,3,2,1, mult[]为 1,1,3,1。

程序INTPART.C是完全按照上面的观点写成的,只不过是上面求sum与size的工作合 二为一而已,所以不应该会有任何困难。为了彻底地了解这个方法,建议找一个比较大的 数(比如8),从头开始用手算几个结果,就不难熟悉整个的处理过程。

【问题实现】
//* ------------------------------------------------------ */
/* PROGRAM  integer partition :                           */
/*    Given a positive integer n, this program lists all  */
/* partition of n in anti-lexical order.                  */
/*                                                        */
/* Copyright Ching-Kuang Shene               July/21/1989 */
/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>          /* for atoi()               */

#define   MAXSIZE   20

void  display(int [], int [], int);

void  main(void)
{
     int  partition[MAXSIZE+1]; /* the actuall partition  */
     int  mult[MAXSIZE+1];      /* multiplicity           */
     int  part_no;              /* no. of parts           */
     int  sum, size, remainder, count;
     int  n;
     char line[100];

     printf("\nPartition of Integer");
     printf("\n====================");
     printf("\n\nInput a Positive Integer --> ");
     gets(line);
     n = atoi(line);

     partition[1] = n;        /* at the biginning, we have*/
     mult[1]      = part_no = count = 1; /* only one part.*/
     display(partition, mult, part_no);

     do {                     /* size one sum in 'sum'    */
          sum  = (partition[part_no]==1) ? mult[part_no--]+1 : 1;
          size = partition[part_no] - 1; /* dec. size     */
          if (mult[part_no] != 1)  /* last part with mul=1*/
               mult[part_no++]--;  /* NO, cut this part   */
          partition[part_no] = size; /* set new part=size */
          mult[part_no]      = sum/size + 1; /* fill other*/
          if ((remainder = sum % size) != 0) {
               partition[++part_no] = remainder;
               mult[part_no]        = 1;
          }
          count++;
          display(partition, mult, part_no);
     } while (mult[part_no] != n);
     printf("\n\nThere are %d partitions in anti-lexical order",
             count);
}


/* ------------------------------------------------------ */
/* FUNCTION display :                                     */
/*    This routine displays the given partition.          */
/* ------------------------------------------------------ */

void  display(int partition[], int mult[], int part_no)
{
     int  i, j;

     printf("\n");
     for (i = 1; i <= part_no; i++)      /* for each part */
          for (j = 1; j <= mult[i]; j++) /* and its mult. */
               printf("%3d", partition[i]); /* show them  */
}
 
【习题】
此处所列的是反字典顺序,能否修改这个程序用字典顺序列出结果呢?换言之,把5 用 1+1+1+1+1,2+1+1+1,2+2+1,3+1+1,3+2,4+1 这 6 个顺序列出来。

参考:
C语言明天精选百则 冼镜光著

 

  • 大小: 30 KB
  • 大小: 46.9 KB
  • 大小: 37.4 KB
  • 大小: 28.7 KB
  • 大小: 35.5 KB
  • 大小: 29.8 KB
  • 大小: 11.5 KB
  • 大小: 94.7 KB
  • 大小: 98.5 KB
分享到:
评论

相关推荐

    C语言期末大作业——图书信息管理系统(C语言,单链表).zip

    【标题】中的“C语言期末大作业——图书信息管理系统(C语言,单链表)”表明这是一个使用C语言编写的程序,旨在实现一个图书信息管理的系统,而且数据结构选择了单链表。在C语言中,单链表是一种常见的数据结构,它...

    c语言——数据结构课件

    数组是最基础的数据结构,它是一组相同类型元素的集合,可以通过索引来访问。链表则是一种动态数据结构,每个元素(节点)包含数据和指向下一个节点的指针。 2. **栈和队列**:栈是一种后进先出(LIFO)的数据结构...

    组合数学——机械工业第四版课后答案(自己整理总结)

    组合数学是一门重要的数学分支,它主要研究在没有重复元素的集合中,如何选择或排列元素的方法。机械工业第四版的组合数学教材,提供了深入浅出的理论讲解和丰富的习题,帮助读者理解和掌握这一领域的核心概念。 在...

    C语言入门-leetcode练习之第47题全排列II.zip

    在本压缩包中,我们关注的是C语言的学习以及在编程挑战平台LeetCode上的一个问题——第47题“全排列II”。这是一个经典的计算机科学问题,它涉及到数组操作、回溯算法和递归等核心编程概念。下面我们将深入探讨这些...

    数据结构用C语言——唐策善

    第八章 排序:排序是将一组数据按照特定顺序排列的过程,本章将涵盖各种排序算法,如冒泡排序、插入排序、快速排序、归并排序和堆排序等,讨论它们的时间复杂度和稳定性。 第九章 查找:查找是在数据集合中寻找特定...

    c语言课件PPT和源代码

    “指针_课后习题.doc”则聚焦于C语言的核心特性——指针。指针可以被视为内存地址的引用,使得动态内存管理、函数参数传递和数据结构实现等变得可能。通过练习题,学习者可以加深对指针的理解和运用。 “12_链表....

    DSDemoC——《数据结构(C语言版)》配书光盘

    3. **排序与查找算法**:排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序等)用于对数据进行有序排列,查找算法(如顺序查找、二分查找、哈希查找)则用于在数据中寻找特定元素。 4. **堆数据结构**...

    数据结构(C语言版)(第2版) —— 严蔚敏 李冬梅 吴伟民.zip

    6. **排序与查找**:排序是将一组数据按照特定顺序排列的过程,常见的排序算法有冒泡排序、快速排序、归并排序和堆排序等。查找是在已排序或无序数据中寻找特定元素的方法,如线性查找、二分查找和哈希表查找。 7. ...

    C经典算法之产生可能的集合

    根据给定的文件信息,我们可以总结出两个与C语言编程相关的经典算法问题,涉及如何生成一个数字集合的所有可能子集。下面将详细解释这两个算法及其背后的逻辑。 ### 算法一:使用二进制表示法生成所有子集 #### ...

    C语言数据结构

    《C语言数据结构——线性表的深度解析》 在计算机科学中,数据结构是组织、存储和处理数据的方式,它是编程的基础之一。C语言,作为一种强大的系统编程语言,提供了丰富的功能来实现各种数据结构。其中,线性表是...

    c语言学习资料

    "单片机C语言程序设计实训100例——基于8051+Proteus仿真"很可能是包含这些实例的教程文档,它将详细介绍如何在8051单片机上使用C语言编程,并通过Proteus进行仿真验证,这样的实践教学方法可以帮助学习者从理论到...

    c语言课程设计范例

    在本篇中,我们将深入探讨一个大学C语言课程设计项目——员工工作量管理系统。这个系统旨在帮助用户实现员工工作量的记录管理,包括添加、修改、查询和删除等功能。通过这个项目,我们可以学习到C语言中的核心概念...

    C语言习题集

    - **D.** 集合型 —— 不属于C语言的基本数据类型。 **结论:** 选项 **C** (双精度型) 属于C语言数据类型。 ##### 16. 符合C语言语法的赋值语句 题目要求找出符合C语言语法的赋值语句。 **选项分析:** - **A.*...

    常用算法汇编(用C语言描述)

    本资源“常用算法汇编——用C语言描述”显然是一份集合了多种常见算法的代码库,旨在帮助开发者理解和应用这些算法。 1. **排序算法**:排序是数据处理的基础,包括冒泡排序、选择排序、插入排序、快速排序、归并...

    数据结构中的数组和广义表,C语言

    本章节主要探讨了两种基本数据结构——数组和广义表,并在C语言的上下文中进行了讲解。数组,特别是二维数组,是数据结构的基础,而广义表则是一种更灵活的数据结构,可以用来表示更复杂的关系。 5.1 数组的基本...

    C语言编写的学生成绩管理系统(数据结构课程设计)

    《C语言实现的学生成绩管理系统——数据结构与快速排序的应用》 在计算机科学领域,数据结构和算法是核心组成部分,它们是构建高效软件的基础。本项目“C语言编写的学生成绩管理系统”是一个典型的结合了数据结构和...

Global site tag (gtag.js) - Google Analytics