第三章 栈和队列

第三章栈和队列一、八皇后问题题目要求：八皇后问题是在8*8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够吃掉任何其他一个，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一对角线。算法分析：算法基本思想如下：从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2,……，8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其它皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置;若当前试探的列位置不安全，则用下一列进行试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。算法抽象描述如下：（1） 置当前行当前列均为1；（2） while（当前行号〈=8〉（3） ｛检查当前行，从当前列起逐列试探，寻找安全列号；（4） if（找到安全列号）（5） 放置皇后，将列号记入栈中，并将下一行置成当前行，第一列置为当前列；（6） else（7） 退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为当前列;（8） ｝结束程序。二、表达式求值问题题目要求：表达式求值是编译系统中的一个基本问题，目的是把人们平时书写的算术表达式变成计算机能够理解并能正确求值的表达方法。表达式计算是实现程序设计语言的基本问题之一，也是栈和队列应用的一个典型例子。具体要求是：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的运算符优先关系，实现对算术四则运算表达式的求值。算法分析：为实现表达式求值，需要完成两个步骤：1、 利用栈，将中缀表达式转换成后缀表达式；2、 利用队列，将后缀表达式求值并输出。三、马踏棋盘题目要求：“马踏棋盘”又叫“马的遍历”、“骑士巡游”或者“骑士游历”，它是由上世纪中叶被欧洲的几位数学家提出的，后来由著名大数学家欧拉将各种解法归纳总结，系统的解决了这个问题。“马踏棋盘”具体内容是：在8行X8列的棋盘上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即达到棋盘上的每一格，并且每格只能到达一次。算法分析：贪婪算法贪婪算法就是一步一个最优解，每步都是有去无回的架势，做出这些最优解的策略号称贪婪准则(greedycriterion)。在设计程序解决“骑士游历”问题时，可以发现，外层格子比在棋盘中心附近的格子更难移动到。事实上，最难访问的是四角的格子。回溯法：棋盘的表示方法我们可以用一个8X8的二维数组A(I，J)来表示国际象棋的棋盘，在马还没有开始周游棋盘时，棋盘上所有的格都置为零。以后，马跳到哪个格，就将马跳跃的步数记录在相应的空格里。马的跳跃方向的确定在国际象棋的棋盘上，一匹马共有八个可能的跳跃方向。我们设置一组坐标增量来描述这八个条约方向：①(1，2)②(2，1)③(2，-1)④(1，-2)⑤(-1，-2)⑥(-2，-1)⑦(-2，1)⑧(-1，2)马的跳跃方向的表示设I表示行，J表示列，行增量为DI(R)，歹U增量为DJ(R)，则马向某个方向试探性地跳跃一步之后的新坐标应该表示为：NI=I+DI(R)，NJ=J+DJ(R)。朝某个方向试探性地跳跃一步再看下一步(取下一步最小可走方向(处理边角问题))，任何一点的坐标加上要试探方向的坐标增量之后，都要判断一下是否已经超出了棋盘的边界。即：当I<0，或I>8,或J<0，或J>8时，都表示已经超出了棋盘的边界，这时，应该放弃该方向，转向试探下一个方向，在不出界的情况下，如果A(NI，NJ)=0，则表示该方向的前方有通路，可以继续向前跳跃。如果A(NI，NJ)>0，则表示该格已经走过了，不能再走。放弃该方向，并转向下一个方向进行试探。四、汉诺塔问题题目要求：传说所罗门庙里有一个塔台，台上有3根用钻石做成的标号为A、B、C的柱子，在A柱上放着64个金盘，每一个金盘都比下面的略小一点。把A柱上的金盘全部移到C柱上的那一天就是世界末日。移动的条件是，一次只能移动一个金盘，移动过程中大金盘不能放在小金盘上面。庙里的僧人一直在移个不停。因为全部移动次数是264-1，如果每秒移动一次的话，需要500亿年。算法分析：汉诺塔盘子之间的移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，可以这样设想：以C杆为临时杆，从A杆将1至N-1号盘移至B杆。将A杆中剩下的第N号盘移至C杆。以A杆为临时杆，从B杆将1至N-1号盘移至C杆。可以看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同，唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题。即：HANOI(N,A,B,C)可转化为HANOI(N-1,A,C,B)与HANOI(N-1,B,A,C)其中HANOI中的参数分别表示需移动的盘数、起始盘、临时盘与终止盘，这种转换直至转入的盘数为0为止，因为这时已无盘可移了。这就是需要找的递归调用模型。采用非递归算法可以用栈实现。米用递归算法实现，其流程为：五、舞伴问题题目要求：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。如两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。算法分析：由题目可知，先入队的男士和先入队的女士会先出队配成舞伴。因此，本问题具有典型的先进先出性，可以用队列作为算法的数据结构。六、台阶问题题目要求：

某人上楼梯，他一步可以迈一个台阶，两个台阶或三个台阶，共有n个台阶，编程输出他所有可能上法。如：有4个台阶，输出应是：TOC\o"1-5"\h\z1 1 11 1 21 2 131 121算法分析：首先考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。如果有3级台阶，那就有两种跳的方法了：一种是分三次跳，每次跳1级；另外一种就是一次跳2级，再一次跳一级；第三种是一次跳3级。讨论一般情况，把n级台阶时的跳法看成是n的函数，记为step(n)。递归函数step(N),分三种处理：第一步1级，再求step(N-1)第一步2级，再求step(N-2)第一步3级，再求step(N-3)。二■。二■■Mu二键七、键盘缓冲区题目要求：键盘缓冲区是一片连续的存储空间，键盘输入的字符可以临时存入键盘的缓冲区中。多任务的系统可以利用用户在键盘上输入内容的时候执行一下应用程序，对于用户输入的内容暂时不显示到屏幕上，而是存入到键盘缓冲区之中。在CPU执行其他应用程序的同时，系统不断地检查键盘状态，若用户在键盘上输入了内容，系统立即把它存入缓冲区中。等应用程序调度结束，系统再把输入到缓冲区中的内容显示到屏幕上，这个过程一直交替进行。本程序假设有两个进程同时存在于一个应用程序中。第一个进程连续在屏幕上显示字符“X”，第二个进程不断检查键盘上是否有输入，若有则读入用户键入的字符，将其保存到键盘缓冲区中。程序约定当用户键入一个逗号“，七表示第一个进程调度结束，系统开始显示那些在键盘缓冲区中的字符；接着继续执行第一个进程；当用户输入“；”时，结束整个程序。算法分析：为了充分利用缓冲区的空间，往往将缓冲区设计成循环队列的结构，并为循环队列结构的缓冲区设置一个队首指针和一个队尾指针。每输入一个字符到缓冲区中，就将尾指针后移，链入缓冲区的循环队列中；每输出一个字符号，就将队头指针前移，将它从缓冲区队列中删除。八、背包问题题目要求：假设有n件质量分别为w1,w2,……,wn的物品和应该最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装入背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即wx1+wx2++wxk=T。若能，则背包问题有解，否则背包问题无解。算法分析：只要不超过背包能承受的总重量，将物品从第一件开始放入背包，并入栈记录，不断尝试，直至最后。九、划分子集问题题目要求：划分子集问题的实际例子很多。如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能在同一时间内进行，问如何安排比赛进程，才能使总的日程最短。又如，学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，问如何安排这m科课程的考试才能使考试时间最短而又不冲突。算法分析：划分子集问题可以抽象成数学模型进行求解。模型为：已知集合A={a1,a2,……,an}和定义在集合上的关系R={(ai,aj)|a,aj£A，1WiWn,1WjWn,i尹j}，其中(ai,aj)表示ai和aj之间存在“冲突关系”现要求将A划分成K个互不相交的子集A1,A2,……,Ak(kWn)使得任何一个子集中的元素无冲突关系。同时，对于给定的集合A和关系R，希望划分的子集个数尽可能的少。十、迷宫问题题目要求：迷宫问题取自心理学的一个古典实验。把一只老鼠从一个没有顶的大盒子的门口放入，在盒子中设置了许多墙，对行进的方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。老鼠在迷宫中的每一点可以向四周八个方向进行搜索，依次为东、东南、南、西南、西、西北、北和东北八个方向。算法分析：在计算机中可以使用二维数组表示迷宫，一个M行N列的迷宫，可以用一个M行N列的数组进行存放。但为了处理方便，通常在迷宫的周围设置行和列的开始处设置边界，并把边界位置全部置换成1。因此可用一个M+2h行和N+2列的数组进行存放，即maze[0..M+1,0..N+1]的形式。maze[1,1]处为入口，maze[虬N]处为出口，并且入口和出口均设置为0。可以用队列记录所走过的路程，队列的结构定义如下：structmgtype{intx,y,pre;}queue[MAXSIZE];MAXSIZE为队列的最大长度，由于迷宫只有M行N列，所走过的路程最多为M*N个，实际上设置为M*N/2即可。queue队列中，x和y为坐标，pre为上一步号。老鼠在迷宫中的每一点可以向四周八个方向进行搜索，依次为东、东南、南、西南、西、西北、北和东北八个方向。如下表：[i-1,j-1]:i-1,j]:i-1,j+1][i,j-1][i,j][i,j+1][i+1,j-1][i+1,j][i+1,j+1]搜索路径可以放在队列中。为区分某一点是否已经被搜索过，可以将凡被搜索过的位置赋值为一1,以免下次重复搜索。十一、学生就餐问题题目要求：设计一个演示程序，模拟学生在食堂的就餐过程。学生在食堂买饭的过程：同学们到食堂按次序由上到下拿快餐