试题四[clrs上的装配调度,经典dp题]
/*
<1>f[0][0]=e[0]+a[0][0] f[1][0]=e[1]+a[1][0]
<2>f[0][j-1]+a[0][j]
<3>f[1][j-1]+a[1][j]<f[0][j-1]+t[0][j-1]+a[1][j]
<4>fi=f[0][n-1]+x[0] li=0
<5>fi=f[1][n-1]+x[1] li=1
(1) e0 和 e1 表示底盘分别进入装配线 0 和装配线 1 所需要的时间。
(2) 每条装配线有 n 个工位，第一条装配线的工位为 S0,0, S0,1, …, S0,n-1, 第二条装 配线的工位为 S1,0, S1,1, …, S1,n-1。其中 S0,k 和 S1,k（0≤k≤n-1）完成相同的任务，但所需时间可能不同。
(3) ai,j 表示在工位 Si,j 处的装配时间，其中 i 表示装配线（i=0 或 i=1），j 表示工位号（0≤j≤n-1）。
(4) ti,j 表示从 Si,j 处装配完成后转移到另一条装配线下一个工位的时间。
(5) x0 和 x1 表示装配结束后，汽车分别从装配线 0 和装配线 1 下线所需要的时间。
(6) 在同一条装配线上，底盘从一个工位转移到其下一个工位的时间可以忽略不计。
该算法的输入为：
n: 表示装配线上的工位数；
e[i]: 表示 e1 和 e2，i 取值为 0 或 1；
a[i][j]:表示 ai,j，i 的取值为 0 或 1，j 的取值范围为 0～n-1；
t[i][j]:表示 ti,j, i 的取值为 0 或 1，j 的取值范围为 0～n-1；
x[i]: 表示 x0 和 x1，i 取值为 0 或 1。
算法的输出为：
fi:最短的装配时间；
li:获得最短装配时间的下线装配线号（0 或者 1）。
算法中使用的 f[i][j]表示从开始点到 Si,j 处的最短装配时间。
*/
void Dp()
{
f[0][0]=e[0]+a[0][0];
f[1][0]=e[1]+a[1][0];
for(int j=1;j<n;++j)
{
if(f[0][j-1]+a[0][j]<f[1][j-1]+a[0][j]+t[1][j-1])
f[0][j]=f[0][j-1]+a[0][j];
else
f[0][j]=f[1][j-1]+a[0][j]+t[1][j-1];
if(f[1][j-1]+a[1][j]<f[0][j-1]+t[0][j-1]+a[1][j])
f[1][j]=f[1][j-1]+a[1][j];
else
f[1][j]=f[0][j-1]+t[0][j-1]+a[1][j];
}
if(f[0][n-1]+x[0]<=f[1][n-1]+x[1])
fi=f[0][n-1]+x[0],li=0;
else
fi=f[1][n-1]+x[1],li=1;
}
试题五[BFS,数据结构题]
函数 LevelTraverse()的功能是对给定树进行层序遍历。例如，对图 5-1 所示的树进 行层序遍历时，结点的访问次序为：D B A E F P C 。
对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如下表所示：
函数原型
说明
void InitQueue(Queue *Q)
初始化队列
Bool IsEmpty(Queue Q)
判断队列是否为空，若是则返回 TRUE,否则返回 FALSE
void EnQueue(Queue *Q,TreeNode p)
元素入队列
void DeQueue(Queue *Q,TreeNode *p)
元素出队列
Bool、Status 类型定义如下：
typedef enum {FALSE = 0,TRUE = 1} Bool;
typedef enum {OVERFLOW = -2,UNDERFLOW = -1,ERROR = 0,OK = 1} Status;
树的二叉链表结点定义如下：
typedef struct Node {
char data;
struct Node *firstchild,*nextbrother;
}Node,*TreeNode;
[函数]
Status LevelTraverse(TreeNode root)
{ /**//*层序遍历树，树采用孩子-兄弟表示法，root 是树根结点的指针*/
Queue tempQ;
TreeNode ptr,brotherptr;
if (!root)
return ERROR;
InitQueue(&tempQ);
(1) ; //(1) EnQueue(&tempQ,root)
brotherptr = root -> nextbrother;
while (brotherptr){ EnQueue(&tempQ,brotherptr);
(2) ; //(2)brotherptr = brotherptr -> nextbrother
} /**//*end-while*/
while ( (3) ) { // (3)!IsEmpty(&tempQ)
(4) ; // (4)DeQueue(&tempQ,ptr)
printf("%c\t",ptr->data);
if ( (5) ) continue; //(5)!ptr->firstchild
(6) ; //(6)EnQueue(&tempQ,ptr->firstchild)
brotherptr = ptr->firstchild->nextbrother;
while (brotherptr){ EnQueue(&tempQ,brotherptr);
(7) ;//(7)brotherptr = brotherptr -> nextbrother
} /**//*end-while*/
} /**//*end-while*/
return OK;
}/**//*LevelTraverse*/
//e 这题开始看题就看错了,以为是2叉树,想了半天,回头一看题,树的层次遍历..！orz..
试题六[考C++派生,继承]
[C++代码 1]
const int CLOSED = 1; const int OPENING = 2;
const int OPEN = 3; const int CLOSING = 4;
const int STAYOPEN = 5; //定义状态变量，用不同整数表示不同状态
class Door {
private:
int state; //传输门当前状态
void setState(int state){ this->state = state; } //设置当前状态
public:
Door():state(CLOSED){};
void getState(){ //根据当前状态输出相应的字符串
switch(state){
case OPENING: cout <<"OPENING" << endl; break;
case CLOSED: cout << "CLOSED" << endl; break;
case OPEN: cout << "OPEN" << endl; break;
case CLOSING: cout << "CLOSING" << endl; break;
case STAYOPEN: cout << "STAYOPEN" << endl; break;
}
}
void click() { //发生click事件时进行状态转换
if ( （1） ) setState(OPENING); //(1)state==CLOSED||state==CLOSING
else if ( （2） ) setState(CLOSING); //(2)state==STAYOPEN||state==OPENING
else if ( （3） ) setState(STAYOPEN);//(3)state==OPEN
}
void timeout(){ //发生timeout事件时进行状态转换
if (state == OPEN) setState(CLOSING);
}
void complete(){ //发生complete事件时进行状态转换
if (state == OPENING) setState(OPEN);
else if (state == CLOSING) setState(CLOSED);
}
};
int main(){
Door aDoor;
aDoor.getState(); aDoor.click(); aDoor.getState(); aDoor.complete();
aDoor.getState(); aDoor.click(); aDoor.getState(); aDoor.click();
aDoor.getState(); return 0;
}
[C++代码 2]
class Door {
public:
DoorState *CLOSED, *OPENING, *OPEN, *CLOSING, *STAYOPEN, *state;
Door();
virtual ~Door(){ …… //释放申请的内存，此处代码省略};
void setState(DoorState *state) { this->state = state; }
void getState(){
// 此处代码省略，本方法输出状态字符串，
// 例如，当前状态为CLOSED时,输出字符串为“CLOSED”
};
void click();
void timeout();
void complete();
};
Door::Door(){
CLOSED = new DoorClosed(this); OPENING = new DoorOpening(this);
OPEN = new DoorOpen(this); CLOSING = new DoorClosing(this);
STAYOPEN = new DoorStayOpen(this); state = CLOSED;
}
void Door::click(){ （4） ;} //(4)state->click()
void Door::timeout(){ （5） ; } //(5)state->timeout()
void Door::complete(){ （6） ; } //(6)state->complete()
class DoorState //定义一个抽象的状态，它是所有状态类的基类
{
protected: Door *door;
public:
DoorState(Door *door) { this->door = door; }
virtual ~DoorState(void);
virtual void click() {}
virtual void complete() {}
virtual void timeout() {}
};
class DoorClosed :public DoorState{ //定义一个基本的 Closed 状态
public:
DoorClosed(Door *door):DoorState(door) {}
virtual ~ DoorClosed (){}
void click();
};
void DoorClosed::click() { （7） ; } //(7)door->setState(door->OPENING)
// 其它状态类的定义与实现代码省略
int main(){
Door aDoor;
aDoor.getState(); aDoor.click(); aDoor.getState(); aDoor.complete();
aDoor.getState(); aDoor.timeout(); aDoor.getState(); return 0;
}
//派生,继承,方面的东西几乎忘干净了！