试题四 (一个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空没注意,想了半天  ...~