算法设计与分析期末论

《算法设计与分析期末论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析论文学院：计算机学院专业：计算机科学与技术姓名：龚振学号：311109010212分数20得分一、简答（任选两题，2×10分=20分）1.简述动态规划算法求解问题的一般步骤。答：⑴找出最优解的性质，并刻画其机构特征；⑵递归地定义最优值；⑶以自底向上的方式计算出最优值；⑷根据计算最优值时地带的信息，构造最优解。6.简述回溯法求解问题的一般步骤。答：(1)用回溯法解题通常包含一下3个步骤(2)针对所给问题，定义问题的解空间；(3)确定易于搜索的解空间；(4)以深度优先方式搜索解空间，并在搜索过程中用剪枝反函数避免无效搜索。分数二、算法设计

2、与程序实现（任选两题，2×40分=80分）统一要求（若该题有特殊要求，会在题中给出）：1.设计算法2.分析计算复杂度3.程序实现4.最后通过简例说明程序实现过程5.需将源程序附上，程序需有必要的注释语句6.需给出程序运行结果截图80得分1、工作分配问题：设有件工作分配给个人。将工作分配给第个人所需费用为。为每一个人分配一件不同的工作，并使总费用达到最小。1.1设计算法工作分配按照遍历应该有n!种分法，从中找出所需费用最少的费用。这里采用递归的方法解决问题对于每一条路径所需费用为expense=，其中表示第i建工作分配给第pi个人时所需费用，p1~p

3、n11互不相同，即每个人只能分配一件工作。在计算的时候可以设计expense(i)等于分配过第i件工作后这时所达到的总费用，分配第i+1i+1件工作，总费用expense(i+1)=expense(i)+,当i

4、0){x[j]=1;x[0]+=c[i][j];p[i]=j;if(ix[0]

5、

6、minexpense==-1){minexpense=x[0];for(intk=1;k<=n;k++)q[k]=p[k];}x[0]-=c[i][j];}x[j]=0;}}}1.2分析计算复杂度1.3程序实现进行宏定义N大小为100,在以后可以重新赋值#defineN100intq[N]={0};//定义全局变量q数组用来保存工作分配路径11intminexpen

7、se=-1;//定义全局变量用来保存分配中最小费用voidworkdistribute(inti,intn,intp[],intx[],intc[][N]);主函数voidmain(){intn=0;intc[N][N];intx[N]={0};intp[N]={0};printf("ttt1.工作分配问题n");printf("请输入人数");scanf("%d",&n);下面用来输入所需费用for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)scanf("%d",&c[i][j]);}调用workd

8、istribute(1,n,p,x,c);函数进行递归分配工作，递归结束后进行输出最小费用和此分法，以矩阵的形式显示workdistribute(1,n,p,x,c);printf("%d",minexpense);此循环用来输出最少费用的分配方法for(intk=1;k<=n;k++){for(intj=1;j<=n;j++){if(q[k]!=j)printf("");elseprintf("%d",c[k][j]);}printf("");}}//workdistribute(i,n,p,x,c)函数设计，传递进行分配的是第几件工作i

9、，已分配过的人X[],分配的路径p[]，以及费用数组c[][]，用X[]来保存已非配工作所需费用voidworkdistribute(inti,intn,int*p,intx[],intc[][N]){for(intj=1;j<=n;j++){if(x[j]==0){11x[j]=1;x[0]+=c[i][j];p[i]=j;if(ix[0]

10、

11、minexpense==-1

12、)//如果是最小分配或第一次分配，则保存此次分配数据{minexpense=x[0];for(intk=1;k<=n;k+