試題四 (一個DFS題,看懂題意就可以做出來)

/*
[說明]
　　假設需要將N個任務分配給N個工人同時去完成，每個人都能承擔這N個任務，
但費用不同。下面的程序用回溯法計算總費用最小的一種工作分配方案，在該方案中，
為每個人分配1個不同的任務。
程序中，N個任務從0開始依次編號，N個工人也從0開始依次編號，主要的變量說明如下：
c[i][j]：將任務i分配給工人 j的費用；
task[i]：值為0表示任務i未分配。值為j表示任務i分配給工人j；
worker[k]：值為0表示工人k未分配任務，值為1表示工人k已分配任務；
mincost：最小總費用。
[C程序]
*/
#include <iostream>
#define N 4 /*N表示任務數和工人數*/
int c[N][N];
unsigned int mincost = 65535; /*設置min的初始值，大于可能的總費用*/
int task[N],temp[N],worker[N];
void plan(int k,unsigned int cost)
{    int i;
     //if(_____(1)_____&& cost < mincost)
     if(k==N && cost<mincost)
    {
         mincost = cost;
         for (i=0;i<N;i++) temp[i]=task[i];
     }
     else
    {
        for ( i = 0 ; i<N; i ++ ) /*分配任務k*/
        if(worker[i]==0 && cost+c[k][i]<mincost)
        //if ( worker [i]==0 && ___(2)_____) //
        {
            //worker[i] = 1;task[k]=___(3)_____;//i
            //plan(_____(4)_____,cost+c[k][i]);//k+1
            //______(5)_______; task [k] = 0;//worker[i]=0
            worker[i]=1;task[k]=i;
            plan(k+1,cost+c[k][i]);
            worker[i]=0;
            task[k]=0;
        } /*if*/
    }
} /*Plan*/

int main ()
{ int i,j;
freopen("in.cpp","r",stdin);
for(i = 0;i < N;i ++)
{ /*設置每個任務由不同工人承擔時的費用及全局數組的初值*/
    worker [ i ] = 0; task [ i ] = 0; temp [ i ] = 0;
    for ( j = 0 ; j < N ; j ++)
        scanf ("%d",&c[ i ] [ j ]);
}
plan (0,0); /*從任務0開始分配*/
printf("\n最小費用 = %d\n",mincost);
for (i = 0; i < N; i ++)
printf ("Task%d is assigned to Worker%d\n",i,temp[ i ]);
return 0;
}/*main*/

 

試題五

#include <iostream>
//[代碼5-1]
class Circle : public___(1)____{ //Shape
private:
_______(2)________m_circle; //XCircle
public:
void display(){
m_circle._____(3)_____;//displayIt()
}
};

//[代碼5-2]
class Factory{
public :
_____(4)_____getShapeInstance(int type){ //生成特定類實例
//Shape *
switch (type){
case 0: return new point;
case 1: return new Rectangle;
case 2: return new line;
case 3: return new Circle;
default: return NULL;
}
}
};
void main (int argc , char *argv[]){
if (argc ! =2){
cout << “error parameters !”<<endl;
return;
}
int type = atoi (argv[ l ]);
Factory factory;
Shape *s;
s = factory._____(5)____;//getShapeInstance(type)
if (s ==NULL){
cout <<”Error get the instance !” << endl;
return;
}
c->display();
__(6)___;  //delete s
return;
}

第6空沒注意,想了半天  ...~