首页 > > 程序设计 > C/C++ >

用回溯法和栈解决阿里面试题排队问题

2018-06-17 21:15:58来源：未知阅读 ()

最近在网上搜索有关Catalan number的资料时发现了一道有关Catalan number的很有趣的问题。题目为有12位高矮不同的人，将他们排成两排，每排六人，要求每排六人均从矮到高排列且第二排每个人的身高均大于第一排对应的人的身高，问满足要求的排列方法有多少种。关于这个问题，不妨直接考虑一般情形，12人为2n人，网上对此的分析已经铺天盖地，答案就是Catalan number n+1/C(n,2n)，具体的分析过程这里就不再重复赘述了，这里我们主要考虑用计算机解决排队问题，不仅要用高效的算法求出排法总数，还要逐一输出所有的排法。这一编程问题网上已有众多大神给出解答，个个漂亮，但我个人认为我所能搜到的解法还是稍显繁琐，循环套循环，循环接循环，一些一维二维数组，运行效率较低，而且还用到了递归，这样在n非常大，也就是递归深度较深时容易引起堆栈溢出问题。这里我自己考虑了一个算法，避免使用递归，用简单的以循环实现回溯法就可以解决，用到的体积最大的数据结构也就是一个长度为2*n的一维数组，这样就能尽可能降低空间复杂度和时间复杂度，先讲一下求解思路：这篇文章http://blog.csdn.net/jiyanfeng1/article/details/8036007 的分析给出一种可能的求解思路。试想将2n个人按从矮到高的顺序排成一个序列，每个人若在第一排就以1表示，若在第二排就以2表示，这样在2n个人中选取n个人视为1，剩下的n个人视为2，这样就得到了一个候选解，这个候选解中第一排的n个人和第二排的n个人都是从矮到高排列。现在我们的任务是从所有候选解中选出可行解。满足第二排每个人的身高均大于第一排对应的人的身高的候选解就是可行解。那么由n个1n个2组成的候选解满足什么条件时就是可行解呢？

考察第m个2，为了满足可行解的要求，第m个1必须在第m个1的前面，这样第二排第m个人的身高才能高于第一排第m个人的身高，于是很自然的第m个2前面的1的个数必须大于等于第m个2前面且包括第m个2在内的2的个数m。这样满足以下条件的候选解就是可行解：

候选解中的每个2前面的1的个数大于等于该2前面的所有2且包括该2本身的个数

于是接下来只要编写算法利用以上条件从候选解中筛选出所有可行解就可以了

怎么筛选？

想筛选出可行解，需要按一定的先后次序将n个1和n个2依次放入保存可行解的队列，由于是从队头起依次放入，因此这是典型的入栈操作，每当一个2被放入后，需要检查栈中包含这个2的部分序列是否是可行解的一部分，若是则继续按一定的规则执行入栈的操作，若不是需要将该2弹出栈(回溯过程)，然后若新的队尾为1，则将1换为2，若为2则继续回溯，将2弹出栈，然后对栈中剩下的部分序列继续判断执行回溯或入栈操作。每次入栈时，一般以1优先入栈，如果n个1已全部入栈或2n-1个0和1已全部入栈(这意味着还有最后一个数需要入栈，这个数只能为2)，则以2入栈。需要注意的是，首先入栈的必须是1(如果为2则为不合法解的一部分),此外，如果检测到栈中只剩下位于栈底的一个元素1，则所有结果均已求出，终止回溯过程。如果检测到栈满，则找到一个候选解，再检查该候选解是否为可行解，如果是输出找到的一个可行解，否则不做操作。然后再将栈底的2弹出栈，继续向后回溯。值得注意的是，以下实现上述算法的代码不仅能够保证回溯过程中的任意时刻入栈的1不超过n，也能保证入栈的2不超过n，各位看官可以想想为什么。

这就是回溯法求解排队问题的算法实现思路。代码实现过程中需要两个计数变量x1和x2记录回溯过程中某一时刻栈中序列中1和2的个数，通过对命题x1>=x2的真值的判断就可判断栈中的部分序列是否合法，还需要计数变量count记录可行解的个数。另外需要用一个重要的布尔变量TF表示新一轮回溯操作开始时上一轮回溯操作中是否已经将栈顶的2弹出使得弹出后的栈顶即为本轮回溯操作的栈顶，从而为本轮操作是继续入栈还是弹出回溯提供依据。最后，我们需要声明重要的标志变量i记录栈顶位置，在整个回溯过程中，i会不断变动，利用i可以方便地判定栈是否只剩栈底元素以及是否栈满，同时需要利用i操作栈顶，执行压入弹出操作。以下就是具体的C语言代码实现：（代码中部分TF赋值语句可删去，但为了逻辑和结构清晰仍予以保留）

以下代码在VC6.0编译环境下运行通过，n=6时可行解总数为132

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include <string.h>
  4 
  5 void main()
  6 {
  7     int x1, x2;
  8     int i, n;    //n表示排队问题中问题的规模
  9     int count;
 10     bool TF;  //为true表明上一轮弹出2否则上一轮为入栈操作
 11     int *p;   //用于指向动态创建的一维数组,也就是保存可行解的栈
 12 
 13     printf("请输入n\n");
 14     scanf("%d", &n);    //输入问题的规模
 15 
 16     p=(int *) malloc(2*n*sizeof(int));   //创建栈
 17     memset(p, 0, 2*n*sizeof(int));      //初始化栈
 18 
 19     i=-1;
 20     x1=x2=0;
 21     TF=false;
 22     count=0;   //初始化栈顶标志i,部分序列1,2个数x1,x2,弹出标志TF和可行解的计数变量count
 23 
 24     while (1)
 25     {
 26         if (i!=2*n-1)  //栈未满
 27         {
 28             if (i==-1)  //首次入栈，栈空
 29             {
 30                 i++;
 31                 p[i]=1;
 32                 x1++;    //1首先入栈,x1自增1
 33             }
 34             else   //非首次入栈栈不空
 35             {
 36                 if (p[i]==1)  //栈顶为1
 37                 {
 38                     if (TF==true)    //之前将2弹出栈
 39                     {
 40                         if (i==0)   //只剩下栈底元素1,回溯结束
 41                             break;
 42                         else    //栈中元素个数大于1
 43                         {
 44                             p[i]=2;
 45                             x2++;
 46                             x1--;
 47                             TF=false;    //2压入栈取代1,x1自减1,x2自增1
 48                         }
 49                     }
 50                     else
 51                     {
 52                         if ((x1!=n)&&(x1+x2+1!=2*n)) //1未全部入栈,栈中空位大于1
 53                         {
 54                             p[++i]=1;
 55                             x1++;
 56                             TF=false;   //1入栈
 57                         }
 58                         else    //1全部入栈或栈中只有一个空位
 59                         {
 60                             p[++i]=2;
 61                             x2++;
 62                             TF=false;   //2入栈
 63                         }
 64                     }
 65                 }
 66                 else  //栈顶为2
 67                 {
 68                     if (TF==true)
 69                     {
 70                          p[i]=0;
 71                          x2--;
 72                          i--;
 73                          TF=true;  //2弹出栈,回溯
 74                     }
 75                     else
 76                     {
 77                        if (x2<=x1)  //部分序列合法执行入栈操作
 78                        {
 79                           if (x1+x2+1==2*n)
 80                           {
 81                              p[++i]=2;
 82                              x2++;
 83                              TF=false;   //2入栈
 84                           }
 85                           else
 86                           {
 87                              if (x1!=n)  //1未全部入栈
 88                              {
 89                                 p[++i]=1;
 90                                 x1++;
 91                                 TF=false;   //1入栈
 92                              }
 93                              else
 94                              {
 95                                 p[++i]=2;
 96                                 x2++;
 97                                 TF=false;    //2入栈
 98                              }
 99                           }
100                        }
101                        else    //部分序列不合法,回溯
102                        {
103                          p[i]=0;
104                          x2--;
105                          i--;
106                          TF=true;   //2弹出栈,回溯
107                        }
108                     }
109                 }
110             }
111         }
112         else   //栈满，找到候选解
113         {
114             if (x2<=x1)   //判断候选解是否为可行解
115             {
116                 count++;
117                 printf("第%d个排列:\n", count);
118                 int j;
119                 for (j=0; j<2*n; j++)
120                 {
121                     if (p[j]==2)
122                         printf("%d ", j+1);
123                 }
124                 printf("\n");           //候选解为可行解,输出,count自增1
125 
126                 for (j=0; j<2*n; j++)
127                 {
128                     if (p[j]==1)
129                         printf("%d ", j+1);
130                 }
131                 printf("\n");
132             }
133             p[i]=0;
134             x2--;
135             i--;
136             TF=true;   //栈底2弹出栈回溯
137 
138         }
139     }
140     printf("总共有%d个排列\n", count);   //输出可行解总数
141 }