计算机算法设计与分析第四版课后答案
【篇一：计算机算法分析与设计(第四版)习题算法分析
部分详解(实验六)】
//6-1、6-6项目vc++6.0测试通过 //6-15项目vc2005测试通过 //6-1 最小长度电路板排列问题 //头文件stdafx.h
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but // are changed infrequently //
#pragma once
#define win32_lean_and_mean // exclude rarely-used stuff from windows headers #include stdio.h #include tchar.h
// todo: reference additional headers your program requires here
// sy61.cpp : defines the entry point for the console application. //
//description:
//分支限界法 6_1 最小长度电路板排列问题 //#include my.h #include stdafx.h #include iostream #include queue
using namespace std; int n,m;
//#include outofbounds.h //定义节点类
class boardnode{
friend int fifoboards(int **,int ,int,int *);//非类成员，可以访问私有成员的函数，最优序列查找 public:
operator int() const{return cd;}//返回常数 cd int len();
public:
int *x,s,cd,*low,*high;//x表示当前节点的电路板排列，s表示当前节点排列好的电路板的数
//表示当前节点的最大长度，low，high分别表当前节点表示每一个连接块的第一个，和最后一个电路板 //的位置 };
//编写类的len()函数,求出当前节点的连接块长度的最大值 int boardnode::len() {
int tmp=0;
for(int k=1;k=m;k++)
if(low[k]=n high[k]0 tmphigh[k]-low[k]) tmp=high[k]-low[k]; return tmp; }
int fifioboards(int **b,int n,int m,int *bestx)//n为电路板的数量，m为连接块的数量 { // int bestd;
queueboardnode q;//声明boardnode类的节点队列q boardnode e;
e.x=new int[n+1];//为数组指针x分配n+1个动态空间，存储当前的排列
e.s=0;//最初时，排列好的电路板的数目为0 e.cd=0;
e.low=new int[m+1];//存储每个连接块的第一个电路板的位置
e.high=new int[m+1];//存储每个连接块的最后一个电路板的位置 for(int i=1;i=m;i++) {
e.high[i]=0;//初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入e.x的排列中
e.low[i]=n+1;//初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入e.x的排列中 }
for(i=1;i=n;i++)
e.x[i]=i;//初始化e.x的排列为1，2,3.....n int bestd=n+1;//最优距离
bestx=0;//记录当前最优排列 do{
if(e.s==n-1)//当已排列了n-1个时 {
//判断是否改变每个连接块的最后一个电路板的位置 for(int j=1;j=m;j++)
if(b[e.x[n]][j] ne.high[j]) e.high[j]=n;
int ld=e.len();//存储当前节点的各连接块长度中的最大长度 //如果当前的最大长度小于了n+1 if(ldbestd) {
delete[] bestx; bestx=e.x;
bestd=ld;//最优距离 }
else delete[] e.x;//删除分配给e.x的数组空间 delete[] e.low;//删除分配给e.low的数组空间 delete[] e.high;//删除分配给e.high的数组空间 }
else {
int curr=e.s+1;//rr记录现在应该排列第几个电路板
for(int i=e.s+1;i=n;i++)//处理扩展节点下一层所有子节点 {
boardnode n;
n.low=new int[m+1];//与if中的意思相同 n.high=new int[m+1]; for(int j=1;j=m;j++) {
n.low[j]=e.low[j];//将e.low[]中的值赋给n.low[] n.high[j]=e.high[j]; if(b[e.x[i]][j]) {
if(currn.low[j])
n.low[j]=curr;//若当前节点连接块j的第一个电路板的位置比现在正在排列的电路板的位置还小 if(currn.high[j])
n.high[j]=curr; } }
n.cd=n.len();
//如果，当前节点的最大长度小于了最优长度则： if(n.cdbestd) {
n.x=new int[n+1]; n.s=e.s+1;
for(int j=1;j=n;j++) n.x[j]=e.x[j];
n.x[n.s]=e.x[i];//交换位置 n.x[i]=e.x[n.s];//交换位置
q.push(n);//将节点n加入队列中 }
else {
delete[] n.low; delete[] n.high; }
//printf(%d,bestd); }
delete[] e.x;//当前扩展节点所有子节点均考虑，变成死结点 //try{
if(!q.empty()){
e=q.front(); //取队列首节点作为扩展节点 q.pop();
}else return bestd; //}
//catch(outofbounds) //{
//return bestd; //}
//printf(finish);
}while(!q.empty()); return bestd; return 1; }
//测试
}