查人人中国名人网凤铝铝材门窗270一平方:能详细地介绍栈吗？
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/30 11:58:45
如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。
出口← ← 1 2 3 4 5
S↓
解题程序如下：
#include <stdio.h>
#include <stdlib.h>
int path[8];
int search(int level, int stack, int remain, int last_in_stack)
{
int total = 0;
if (remain == 0 && stack == 0)
{
for (int i = 0; i < level; i++)
{
printf("%d ", path[i]);
}
printf("\n");
return 1;
}
if (remain > 0)
{
path[level] = 1;
total += search(level + 1, stack, remain - 1, 0);
path[level] = 2;
total += search(level + 1, stack + 1, remain - 1, 1);
}
if (stack > 0 && !last_in_stack)
{
path[level] = 3;
total += search(level + 1, stack - 1, remain, 0);
}
return total;
}
int main()
{
int stack = 2;
int remain = 2;
int total = search(0, stack, remain, 0);
printf("total=%d\n", total);
return 0;
}
运行结果：
1 1 3 3
1 3 1 3
1 3 3 1
2 1 3 3 3
3 1 1 3
3 1 3 1
3 2 1 3 3
3 3 1 1
3 3 2 1 3
total=9
即9种可能排列，它们分别是：
3 4 5 2 1
3 4 2 5 1
3 4 2 1 5
3 5 4 2 1
3 2 4 5 1
3 2 4 1 5
3 2 5 4 1
3 2 1 4 5
3 2 1 5 4