[算法设计与分析]出栈顺序解法
原创空间,  软件技术,  电脑与网络,  科学研究

binaryluo 发表于 2006/8/11 15:56:02

　　 原题： 有四个元素a, b, c, d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列。 该题有两种思路：1.直接找出所有正确的解；2.在全集中排除不正确的解，剩余的即为正确解。我将要给出的是第二种思路——间接法求解的过程。间接法的优点：可以对随机输入的一组序列进行判断，看是否是正确的出栈序列。间接法的缺点：如果要求解全部正确的出栈序列，需先求出全排列，然后用该判断函数对全排列中的每一组序列进行检验，将正确的序列输出。简介：由于题目已经隐性规定“a在b先入栈，b在c先入栈，c在d先入栈，……”如果原始序列用s表示，那么题目隐含条件可归纳为“s[ i ]在s[ i + 1]先入栈”。因此，在出栈的时候，若若j < m < n < k，且s[ j ]和s[ k ]均已出栈，则s[ m ]必不可能在s[ n ]之前出栈。例：s = a, b, c, d若出栈序列的前两个元素是：c, d，则说明a, b还在栈中（a要退栈的前提是b先退栈），此时可以确定正确的出栈序列是：c, d, b, a。  检测函数： int sost(char **a, char *s, int p, int n,   void (*view)(char **a, int m, int n)){ int count; int flag; int i, j, k; Stack *st;  /* disp(a, p, n); */ count = 0; st = (Stack *)malloc(sizeof (Stack)); stack_init(st);    /* initiate the stack */ for (i = 0; i < p; i ++) /* M is the number of records in list a */ {  flag = 1;  j = 0;  k = 0;     /* deal with a records */  while (j < n && k < n)  {   /* if the element of record match to source's */   if (a[i][j] != s[k])   {    /* revert the sequence out stack */    if (!stack_empty(st) && a[i][j] == peep(st))    {     pop(st);     ++ j;    }    else    {     push(st, s[k]);     ++ k;    }   }   else   {    ++ j;    ++ k;   }  }   /* test if the sequence is ok */  while (!stack_empty(st) && j < n)  {   if (a[i][j] != pop(st))   {    flag = 0;    break;   }    ++ j;  }   /* print the valid record */  if (flag)  {   count ++;   (*view)(a, i, n);  }   /* clear the stack */  stack_clear(st); }  stack_destroy(st); if (st) free(st); flag = count;  return flag;} 附完整原代码：500)this.width=500'>  编译：用VC++ 6.0打开SOST.dsw。  运行： >sostUsage: sost [-t record] [-a number]Options:    -t record   test the record is valid out-stack sequence or not.    -a number   find all valid solutions of the number of full-permutation.>sost -t cbacbaValid seqence.>sost - t cabNOT valid sequence.> sost -a 5edcbadecbacedbadcebacdebabedcabdecacbedabcedadcbeacdbeabdceacbdeabcdeaaedcbadecbacedbadcebacdebbaedcabedcbadecabdeccbaedbcaedacbedbacedabceddcbaecdbaebdcaecbdaebcdaeadcbeacdbebadceabdcecbadebcadeacbdebacdeabcdecount of total solutions is 42.> 

回复:出栈顺序解法
原创空间,  软件技术,  电脑与网络,  科学研究

东方不败(游客)发表评论于2008/9/6 15:44:49

以下引用自由人(游客)在2006-8-11 17:33:54的评论: 博主的算法好难，需要理解出栈规律再去推算。我写了一个简单的递归，但只能用来计算共可能的情况总数。 解决： 根据元素的进出栈过程，可以抽象出一个中间状态。 这个状态就是：  k个元素在等待进入栈               A个元素存放于栈中               B个元素已经出栈 而后续的新状态就是从这个状态衍生出去的，有两种情况：            1. 一个新元素进入堆栈，此时形成新的状态为：               k-1               A+1               B            2. 堆栈中的一个元素出栈，此时形成新的状态为：               k               A-1               B+1 只要根据这个衍生规律，就可以写出递归程序来解决。 还剩下一个问题就是：如何判断已经有一个完整的出栈序列(此时表示出现一个新的情况)。 方法是：            判断 B == n，就是判断是否全部元素都出栈了。   递归程序： #include <stdio.h>   /*sum作为全局变量记录共可能多少种情况*/ int sum = 0;   /* 描述：递归计算共可能出现的出栈序列，无返回值 参数：inStack -- 目前存放于栈中的元素个数          wait -- 目前还未进栈的元素个数          out -- 目前已经出栈的元素个数          num -- 一共有多少个元素 */ void f(int inStack, int wait, int out, int num) {     /*如果全部元素都出栈，表明有了一种新情况，总数加一*/     if (out == num)        sum++;     /*否则继续递归衍生新的状态*/     else {        /*衍生方法1：让一个元素出栈*/        if (inStack > 0)            f(inStack-1, wait, out+1, num);        /*衍生方法2：让一个元素进栈*/        if (wait > 0)            f(inStack+1, wait-1, out, num);     } } /*用main函数调用*/ void main() {     /*一共有n个元素*/     int n = 6;     /*刚开始时栈中有0个元素，有n个元素等待，有0个元素出了栈，共有n个元素*/     f(0, n, 0, n);     int result = sum;     printf ("%d\n", sum); }     

回复:出栈顺序解法
原创空间,  软件技术,  电脑与网络,  科学研究

hinus(游客)发表评论于2007/6/6 11:01:14

楼主赞～ 楼上的搞笑呢吧，大家都知道所有的情况数是C(n,2n)/(n+1)．多此一举～ 

回复:出栈顺序解法
原创空间,  软件技术,  电脑与网络,  科学研究

自由人(游客)发表评论于2006/8/11 17:33:54

博主的算法好难，需要理解出栈规律再去推算。我写了一个简单的递归，但只能用来计算共可能的情况总数。 解决： 根据元素的进出栈过程，可以抽象出一个中间状态。 这个状态就是：  k个元素在等待进入栈               A个元素存放于栈中               B个元素已经出栈 而后续的新状态就是从这个状态衍生出去的，有两种情况：            1. 一个新元素进入堆栈，此时形成新的状态为：               k-1               A+1               B            2. 堆栈中的一个元素出栈，此时形成新的状态为：               k               A-1               B+1 只要根据这个衍生规律，就可以写出递归程序来解决。 还剩下一个问题就是：如何判断已经有一个完整的出栈序列(此时表示出现一个新的情况)。 方法是：            判断 B == n，就是判断是否全部元素都出栈了。   递归程序： #include <stdio.h>   /*sum作为全局变量记录共可能多少种情况*/ int sum = 0;   /* 描述：递归计算共可能出现的出栈序列，无返回值 参数：inStack -- 目前存放于栈中的元素个数          wait -- 目前还未进栈的元素个数          out -- 目前已经出栈的元素个数          num -- 一共有多少个元素 */ void f(int inStack, int wait, int out, int num) {     /*如果全部元素都出栈，表明有了一种新情况，总数加一*/     if (out == num)        sum++;     /*否则继续递归衍生新的状态*/     else {        /*衍生方法1：让一个元素出栈*/        if (inStack > 0)            f(inStack-1, wait, out+1, num);        /*衍生方法2：让一个元素进栈*/        if (wait > 0)            f(inStack+1, wait-1, out, num);     } } /*用main函数调用*/ void main() {     /*一共有n个元素*/     int n = 6;     /*刚开始时栈中有0个元素，有n个元素等待，有0个元素出了栈，共有n个元素*/     f(0, n, 0, n);     int result = sum;     printf ("%d\n", sum); }