铁路调度问题 -- 递归 -- 栈 -- 笔试题目
前言
通过这个问题的解答，思考，感觉对递归掌握更深了一点，很棒的一道题。代码有详细解释，互相学习~
铁路调度问题 – 递归 – 栈 – 笔试题目
左边停了N个车厢，N个车厢依次编号为1-N。现希望通过中间的Y字型铁轨。将所有车厢拉到右边，所有车厢不允许走重复的路。
请列出所有列车到右边铁路后，右边列车所有可能的排法
注意并非全排列
#include <iostream>
#include <stdlib.h>
using namespace std;/*
问题：C语言编程。Y字形铁路如下图：铁路调度问题---》 ---》| || || |———左边停了N个车厢，N个车厢依次编号为1-N。现希望通过中间的Y字型铁轨。将所有车厢拉到右边，所有车厢不允许走重复的路。请列出所有列车到右边铁路后，右边列车所有可能的排法
解析：1.可以将Y字型中间看作一个栈2.每次都有只有两种处理方式：出栈/入栈。这是一种典型的递归问题
算法：根据解析可以用两重递归，入栈与出栈分别为一个递归。条件：
-- 进栈递归跳出条件为最后一个元素进栈，本题目可以用左侧编号=0表示，因为
-- 出栈递归跳出条件为栈空
*/// 定义一个简单的栈类
class myStack{
private:int top; /* 栈顶的下标 */int *data; /* 栈空间 */public:myStack( int n ){/* n为栈的大小 */top = -1;data = new int[n];}~myStack(){delete [] data;}
public:/* 三个操作函数 省略容错处理(解本题目可省略) */void push(int q){top ++ ;data[top] = q;}bool isEmpty(){return top==-1?true:false;}int pop(){return data[ top -- ];}
};/* __process递归函数声明，提供process调用,再process下面定义
参数都是记录当前处理的状态：mystack ---- Y字型中间栈的状态pos ----- 左侧待操作的车厢编号path[] ----- 记录右侧轨道状态的数组，存储编号排列curp ----- 记录右侧车厢数目*/
void __process( myStack &mystack , int pos , int path[] , int curp ); /* process函数，输入参数为左侧待操作车厢数目 */
void process( int N ){myStack mystack(N); /* 模拟Y字型中间栈 */int path[N]; /* 存放右侧车厢编号排列 */cout << "所有输出序列为："<< endl;__process( mystack , N , path , 0 ); /* 第一次操作 */
}
/*__process 函数 定义*/
void __process( myStack &mystack , int pos , int path[] , int curp ){/* 每次操作都为 -- 两个选择，入栈以及出栈 */// 1.入栈if( pos > 0 ) { // 入栈条件，左侧有车厢，即pos>0 mystack.push( pos ); __process(mystack , pos-1 , path , curp);// 进行下一次抉择mystack.pop(); // 恢复原状}// 2.出栈if(!mystack.isEmpty()) {int m = mystack.pop(); //把当前车厢出栈 path[curp] = m; // 出栈车厢放在右边__process(mystack , pos , path , curp + 1 ); // 进行下一次抉择mystack.push(m); // 恢复原状}// 3.最终 pos == 0 左侧无车厢 && isEmpty 栈空，栈中无车厢 , 此时右侧调度完成，输出结果 if( pos == 0 && mystack.isEmpty() ){for( int i = curp-1 ; i >= 0 ; i-- ){// 此时curp为 N ，车厢按照从左到右输出，最左侧为path最后一个元素cout << path[i] << " " ;}cout << endl;}
}
int main(){int n ;cout << "左侧车厢数量 ： " ;cin >> n;process(n);
}
测试结果
铁路调度问题 -- 递归 -- 栈 -- 笔试题目
前言
通过这个问题的解答，思考，感觉对递归掌握更深了一点，很棒的一道题。代码有详细解释，互相学习~
铁路调度问题 – 递归 – 栈 – 笔试题目
左边停了N个车厢，N个车厢依次编号为1-N。现希望通过中间的Y字型铁轨。将所有车厢拉到右边，所有车厢不允许走重复的路。
请列出所有列车到右边铁路后，右边列车所有可能的排法
注意并非全排列
#include <iostream>
#include <stdlib.h>
using namespace std;/*
问题：C语言编程。Y字形铁路如下图：铁路调度问题---》 ---》| || || |———左边停了N个车厢，N个车厢依次编号为1-N。现希望通过中间的Y字型铁轨。将所有车厢拉到右边，所有车厢不允许走重复的路。请列出所有列车到右边铁路后，右边列车所有可能的排法
解析：1.可以将Y字型中间看作一个栈2.每次都有只有两种处理方式：出栈/入栈。这是一种典型的递归问题
算法：根据解析可以用两重递归，入栈与出栈分别为一个递归。条件：
-- 进栈递归跳出条件为最后一个元素进栈，本题目可以用左侧编号=0表示，因为
-- 出栈递归跳出条件为栈空
*/// 定义一个简单的栈类
class myStack{
private:int top; /* 栈顶的下标 */int *data; /* 栈空间 */public:myStack( int n ){/* n为栈的大小 */top = -1;data = new int[n];}~myStack(){delete [] data;}
public:/* 三个操作函数 省略容错处理(解本题目可省略) */void push(int q){top ++ ;data[top] = q;}bool isEmpty(){return top==-1?true:false;}int pop(){return data[ top -- ];}
};/* __process递归函数声明，提供process调用,再process下面定义
参数都是记录当前处理的状态：mystack ---- Y字型中间栈的状态pos ----- 左侧待操作的车厢编号path[] ----- 记录右侧轨道状态的数组，存储编号排列curp ----- 记录右侧车厢数目*/
void __process( myStack &mystack , int pos , int path[] , int curp ); /* process函数，输入参数为左侧待操作车厢数目 */
void process( int N ){myStack mystack(N); /* 模拟Y字型中间栈 */int path[N]; /* 存放右侧车厢编号排列 */cout << "所有输出序列为："<< endl;__process( mystack , N , path , 0 ); /* 第一次操作 */
}
/*__process 函数 定义*/
void __process( myStack &mystack , int pos , int path[] , int curp ){/* 每次操作都为 -- 两个选择，入栈以及出栈 */// 1.入栈if( pos > 0 ) { // 入栈条件，左侧有车厢，即pos>0 mystack.push( pos ); __process(mystack , pos-1 , path , curp);// 进行下一次抉择mystack.pop(); // 恢复原状}// 2.出栈if(!mystack.isEmpty()) {int m = mystack.pop(); //把当前车厢出栈 path[curp] = m; // 出栈车厢放在右边__process(mystack , pos , path , curp + 1 ); // 进行下一次抉择mystack.push(m); // 恢复原状}// 3.最终 pos == 0 左侧无车厢 && isEmpty 栈空，栈中无车厢 , 此时右侧调度完成，输出结果 if( pos == 0 && mystack.isEmpty() ){for( int i = curp-1 ; i >= 0 ; i-- ){// 此时curp为 N ，车厢按照从左到右输出，最左侧为path最后一个元素cout << path[i] << " " ;}cout << endl;}
}
int main(){int n ;cout << "左侧车厢数量 ： " ;cin >> n;process(n);
}
发布评论