最近在网上搜索有关Catalan number的资料时发现了一道有关Catalan number的很有趣的问题。题目为有12位高矮不同的人将他们排成两排每排六人要求每排六人均从矮到高排列且第二排每个人的身高均大于第一排对应的人的身高问满足要求的排列方法有多少种。关于这个问题不妨直接考虑一般情形12人为2n人网上对此的分析已经铺天盖地答案就是Catalan number n1/C(n,2n)具体的分析过程这里就不再重复赘述了这里我们主要考虑用计算机解决排队问题不仅要用高效的算法求出排法总数还要逐一输出所有的排法。这一编程问题网上已有众多大神给出解答个个漂亮但我个人认为我所能搜到的解法还是稍显繁琐循环套循环循环接循环一些一维二维数组运行效率较低而且还用到了递归这样在n非常大也就是递归深度较深时容易引起堆栈溢出问题。这里我自己考虑了一个算法避免使用递归用简单的以循环实现回溯法就可以解决用到的体积最大的数据结构也就是一个长度为2*n的一维数组这样就能尽可能降低空间复杂度和时间复杂度先讲一下求解思路这篇文章12个高矮不同的人,排成两排/Catalan数_jiyanfeng1的专栏-CSDN博客 的分析给出一种可能的求解思路。试想将2n个人按从矮到高的顺序排成一个序列每个人若在第一排就以1表示若在第二排就以2表示这样在2n个人中选取n个人视为1剩下的n个人视为2这样就得到了一个候选解这个候选解中第一排的n个人和第二排的n个人都是从矮到高排列。现在我们的任务是从所有候选解中选出可行解。满足第二排每个人的身高均大于第一排对应的人的身高的候选解就是可行解。那么由n个1n个2组成的候选解满足什么条件时就是可行解呢考察第m个2为了满足可行解的要求第m个1必须在第m个2的前面这样第二排第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的个数通过对命题x1x2的真值的判断就可判断栈中的部分序列是否合法还需要计数变量count记录可行解的个数。另外需要用一个重要的布尔变量TF表示新一轮回溯操作开始时上一轮回溯操作中是否已经将栈顶的2弹出使得弹出后的栈顶即为本轮回溯操作的栈顶从而为本轮操作是继续入栈还是弹出回溯提供依据。最后我们需要声明重要的标志变量i记录栈顶位置在整个回溯过程中i会不断变动利用i可以方便地判定栈是否只剩栈底元素以及是否栈满同时需要利用i操作栈顶执行压入弹出操作。 以下就是具体的C语言代码实现代码中部分TF赋值语句可删去但为了逻辑和结构清晰仍予以保留以下代码在visual studio 2022编译环境下运行通过n6时可行解总数为132#include stdio.h #include malloc.h #include string.h int main() { int x1, x2; int i, n; //n表示排队问题中问题的规模 int count; bool TF; //为true表明上一轮弹出2否则上一轮为入栈操作 int* p; //用于指向动态创建的一维数组,也就是保存可行解的栈 printf(请输入n\n); scanf_s(%d, n); //输入问题的规模 p (int*)malloc(2 * n * sizeof(int)); //创建栈 memset(p, 0, 2 * n * sizeof(int)); //初始化栈 i 0; x1 1; x2 0; TF false; count 0; //初始化栈顶标志i,部分序列1,2个数x1,x2,弹出标志TF和可行解的计数变量count p[i] 1; //首次入栈栈空,关键变量值已在上方确定,1首先入栈,x1自增1 while (1) { if (i ! 2 * n - 1) //栈未满 { //非首次入栈栈不空 if (TF false) { if (p[i] 1 || x2 x1) //部分序列合法执行入栈操作 { if (x1 ! n) //1未全部入栈,栈中空位大于1 { p[i] 1; //1入栈 x1; } else //1全部入栈或栈中只有一个空位 { p[i] 2; //2入栈 x2; } continue; } else { TF true; } } else //之前将2弹出栈 { if (p[i] 1) //栈顶为1 { if (i 0) //只剩下栈底元素1,回溯结束 break; else //栈中元素个数大于1 { p[i] 2; //2压入栈取代1,x1自减1,x2自增1 x2; --x1; TF false; continue; } } } } else //栈满找到候选解 { count; //这里必定有x2 x1,因为最后入栈2时,n个1已经全部入栈 printf(第%d个排列:\n, count); int j; for (j 0; j 2 * n; j) { if (p[j] 2) printf(%d , j 1); } printf(\n); //候选解为可行解,输出,count自增1 for (j 0; j 2 * n; j) { if (p[j] 1) printf(%d , j 1); } printf(\n); TF true; } --x2; --i; //2弹出栈回溯 } printf(总共有%d个排列\n, count); //输出可行解总数 return 0; }运行结果: 用回溯法和栈解决阿里面试题排队问题
最近在网上搜索有关Catalan number的资料时发现了一道有关Catalan number的很有趣的问题。题目为有12位高矮不同的人将他们排成两排每排六人要求每排六人均从矮到高排列且第二排每个人的身高均大于第一排对应的人的身高问满足要求的排列方法有多少种。关于这个问题不妨直接考虑一般情形12人为2n人网上对此的分析已经铺天盖地答案就是Catalan number n1/C(n,2n)具体的分析过程这里就不再重复赘述了这里我们主要考虑用计算机解决排队问题不仅要用高效的算法求出排法总数还要逐一输出所有的排法。这一编程问题网上已有众多大神给出解答个个漂亮但我个人认为我所能搜到的解法还是稍显繁琐循环套循环循环接循环一些一维二维数组运行效率较低而且还用到了递归这样在n非常大也就是递归深度较深时容易引起堆栈溢出问题。这里我自己考虑了一个算法避免使用递归用简单的以循环实现回溯法就可以解决用到的体积最大的数据结构也就是一个长度为2*n的一维数组这样就能尽可能降低空间复杂度和时间复杂度先讲一下求解思路这篇文章12个高矮不同的人,排成两排/Catalan数_jiyanfeng1的专栏-CSDN博客 的分析给出一种可能的求解思路。试想将2n个人按从矮到高的顺序排成一个序列每个人若在第一排就以1表示若在第二排就以2表示这样在2n个人中选取n个人视为1剩下的n个人视为2这样就得到了一个候选解这个候选解中第一排的n个人和第二排的n个人都是从矮到高排列。现在我们的任务是从所有候选解中选出可行解。满足第二排每个人的身高均大于第一排对应的人的身高的候选解就是可行解。那么由n个1n个2组成的候选解满足什么条件时就是可行解呢考察第m个2为了满足可行解的要求第m个1必须在第m个2的前面这样第二排第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的个数通过对命题x1x2的真值的判断就可判断栈中的部分序列是否合法还需要计数变量count记录可行解的个数。另外需要用一个重要的布尔变量TF表示新一轮回溯操作开始时上一轮回溯操作中是否已经将栈顶的2弹出使得弹出后的栈顶即为本轮回溯操作的栈顶从而为本轮操作是继续入栈还是弹出回溯提供依据。最后我们需要声明重要的标志变量i记录栈顶位置在整个回溯过程中i会不断变动利用i可以方便地判定栈是否只剩栈底元素以及是否栈满同时需要利用i操作栈顶执行压入弹出操作。 以下就是具体的C语言代码实现代码中部分TF赋值语句可删去但为了逻辑和结构清晰仍予以保留以下代码在visual studio 2022编译环境下运行通过n6时可行解总数为132#include stdio.h #include malloc.h #include string.h int main() { int x1, x2; int i, n; //n表示排队问题中问题的规模 int count; bool TF; //为true表明上一轮弹出2否则上一轮为入栈操作 int* p; //用于指向动态创建的一维数组,也就是保存可行解的栈 printf(请输入n\n); scanf_s(%d, n); //输入问题的规模 p (int*)malloc(2 * n * sizeof(int)); //创建栈 memset(p, 0, 2 * n * sizeof(int)); //初始化栈 i 0; x1 1; x2 0; TF false; count 0; //初始化栈顶标志i,部分序列1,2个数x1,x2,弹出标志TF和可行解的计数变量count p[i] 1; //首次入栈栈空,关键变量值已在上方确定,1首先入栈,x1自增1 while (1) { if (i ! 2 * n - 1) //栈未满 { //非首次入栈栈不空 if (TF false) { if (p[i] 1 || x2 x1) //部分序列合法执行入栈操作 { if (x1 ! n) //1未全部入栈,栈中空位大于1 { p[i] 1; //1入栈 x1; } else //1全部入栈或栈中只有一个空位 { p[i] 2; //2入栈 x2; } continue; } else { TF true; } } else //之前将2弹出栈 { if (p[i] 1) //栈顶为1 { if (i 0) //只剩下栈底元素1,回溯结束 break; else //栈中元素个数大于1 { p[i] 2; //2压入栈取代1,x1自减1,x2自增1 x2; --x1; TF false; continue; } } } } else //栈满找到候选解 { count; //这里必定有x2 x1,因为最后入栈2时,n个1已经全部入栈 printf(第%d个排列:\n, count); int j; for (j 0; j 2 * n; j) { if (p[j] 2) printf(%d , j 1); } printf(\n); //候选解为可行解,输出,count自增1 for (j 0; j 2 * n; j) { if (p[j] 1) printf(%d , j 1); } printf(\n); TF true; } --x2; --i; //2弹出栈回溯 } printf(总共有%d个排列\n, count); //输出可行解总数 return 0; }运行结果: