試題四 (一個(gè)DFS題,看懂題意就可以做出來(lái))

/*
[說(shuō)明]
　　假設(shè)需要將N個(gè)任務(wù)分配給N個(gè)工人同時(shí)去完成，每個(gè)人都能承擔(dān)這N個(gè)任務(wù)，
但費(fèi)用不同。下面的程序用回溯法計(jì)算總費(fèi)用最小的一種工作分配方案，在該方案中，
為每個(gè)人分配1個(gè)不同的任務(wù)。
程序中，N個(gè)任務(wù)從0開(kāi)始依次編號(hào)，N個(gè)工人也從0開(kāi)始依次編號(hào)，主要的變量說(shuō)明如下：
c[i][j]：將任務(wù)i分配給工人 j的費(fèi)用；
task[i]：值為0表示任務(wù)i未分配。值為j表示任務(wù)i分配給工人j；
worker[k]：值為0表示工人k未分配任務(wù)，值為1表示工人k已分配任務(wù)；
mincost：最小總費(fèi)用。
[C程序]
*/
#include <iostream>
#define N 4 /*N表示任務(wù)數(shù)和工人數(shù)*/
int c[N][N];
unsigned int mincost = 65535; /*設(shè)置min的初始值，大于可能的總費(fèi)用*/
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 ++ ) /*分配任務(wù)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 ++)
{ /*設(shè)置每個(gè)任務(wù)由不同工人承擔(dān)時(shí)的費(fèi)用及全局?jǐn)?shù)組的初值*/
    worker [ i ] = 0; task [ i ] = 0; temp [ i ] = 0;
    for ( j = 0 ; j < N ; j ++)
        scanf ("%d",&c[ i ] [ j ]);
}
plan (0,0); /*從任務(wù)0開(kāi)始分配*/
printf("\n最小費(fèi)用 = %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){ //生成特定類(lèi)實(shí)例
//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空沒(méi)注意,想了半天  ...~