試題四[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;
}
//派生,繼承,方面的東西幾乎忘干凈了！