算法设计及分析实验指导.doc

算法分析与设计实验指导.实验一 锦标赛问题实验目的1. 基本掌握分治算法的原理.2. 掌握递归算法及递归程序的设计.3. 能用程序设计语言求解锦标赛等问题的算法.预习要求1. 认真阅读数据结构教材和算法设计教材,了解分治算法原理;2. 设计用分治算法求解背包问题的数据结构与程序代码.实验题【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1in，1jn-1。 实验提示我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1） （2） （3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 实验步骤1. 采用递归方式设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;2. 应用设计的算法和程序求锦标赛问题;3. 去掉测试程序,将你的程序整理成功能模块存盘备用. 实验报告要求1. 阐述实验目的和实验内容;2. 阐述分治算法原理;3. 提交实验程序的功能模块;4. 记录最终测试数据和测试结果。思考与练习【金块问题】老板有一袋金块(共n块，n是2的幂（n=2），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。实验二 背包问题实验目的4. 能用程序设计语言实现求解背包问题的算法;5. 基本掌握动态规划法（贪心）的原理方法.预习要求3. 认真阅读数据结构教材和算法设计教材,了解背包问题的常用算法原理;4. 设计用动态规划算法求解背包问题的数据结构和递归程序.实验题【背包问题】有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量W，但选中物品的价值之和最大。实验提示设n件物品的重量分别为w0、w1、wn-1，物品的价值分别为v0、v1、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option ，该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop 。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。对于第i件物品的选择考虑有两种可能：（1） 考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。（2） 考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。按以上思想写出递归算法如下：try(物品i，当前选择已达到的重量和，本方案可能达到的总价值tv)/*考虑物品i包含在当前方案中的可能性*/if(包含物品i是可以接受的)将物品i包含在当前方案中；if (in-1)try(i+1,tw+物品i的重量,tv);else/*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存;恢复物品i不包含状态；/*考虑物品i不包含在当前方案中的可能性*/if (不包含物品i仅是可男考虑的)if (in-1)try(i+1,tw,tv-物品i的价值)；else/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存;为了理解上述算法，特举以下实例。设有4件物品，它们的重量和价值见表：物品0123重量5321价值4431并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。Try(0,0,12)Try(1,5,12)Try(1,0,8)Try(2,5,8)Try(3,7,8)Try(2,3,8)Try(3,5,8)不能得到更好的解不能得到更好的解超重不能得到更好的解得到解：(1,0,1,0)maxv=7得到解：(0,1,1,1)maxv=8不能得到更好的解超重 实验步骤4. 设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;5. 应用设计的算法和程序求解背包问题;6. 去掉测试程序,将你的程序整理成功能模块存盘备用. 实验报告要求5. 阐述实验目的和实验内容;6. 阐述求解背包问题的算法原理;7. 提交实验程序的功能模块;8. 记录最终测试数据和测试结果。思考与练习请用其它的算法（如贪心、分支限界等）求解背包问题。实验三 作业调度问题实验目的1.熟悉多机调度问题的算法；2.进一步掌握贪心算法3.提高分析与解决问题的能力。 预习要求1.认真阅读教材或参考书, 掌握贪心算法的基本思想；2.写出求解“作业调度”的程序；3.设计好测试用例。实验题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。实验提示1.把作业按加工所用的时间从大到小排序；2.如果作业数目比机器的数目少或相等，则直接把作业分配下去；3.如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。typedef struct Job int ID;/作业号 int time;/作业所花费的时间Job;typedef struct JobNode /作业链表的节点 int ID; int time; JobNode *next;JobNode,*pJobNode;typedef struct Header /链表的表头 int s; pJobNode next;Header,pHeader;int SelectMin(Header* M,int m) int k=0; for(int i=1;im;i+) if(Mi.smk.s)k=i; return k;实验步骤1先用贪心算法求解该问题，并测试你的程序，直至正确为止；2针对问题实例，实录运行时的输入、输出文件；3将你的程序和实录的界面存盘备用。 实验报告要求阐述实验目的和实验内容；1提交模块化的实验程序源代码；2简述程序的测试过程，提交实录的输入、输出文件；3鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。实验四 回溯算法设计实验目的1. 掌握回溯法解题的基本思想；2. 掌握回溯算法的设计方法；3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。预习要求1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；2. 了解子集和数问题及解向量的定长和变长状态空间表示；3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；4. 分析深度优先扩展状态空间树节点或回溯的条件；5. 分析和设计生成解向量各分量可选值的实现方法；6. 设计和编制回溯算法的递归和迭代程序。实验题# include # define MAXN 100 int aMAXN; void comb(int m,int k) int i,j; for (i=m;i=k;i-) ak=i; if (k1) comb(i-1,k-1); else for (j=a0;j0;j-) printf(“%4d”,aj); printf(“/n”); void main() a0=3; comb(5,3); 【组合数】找出从自然数1，2，n中任取r个数的所有组合。# define MAXN 100 int aMAXN; void comb（int m,int r） int i,j; i=0; ai=1; do if （ai-iai，后一个数字比前一个大；（2）ai-i=n-r+1。按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a2上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a2回溯到a1，这时，a1=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a0再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下： void comb(int n,int r)int i,j; i=0;ai=1;do if (ai-i=n-r+1)/*还可以向前试探*/ if (i=r-1)/*已找到一个组合*/ for (j=0;jr;j+) printf(“%4d”,aj); printf(“n”); ai+; continue;i+;ai = ai-1 + 1; /*向前试探*/ else if (i=0) return;/*已找到所有解*/ a-i+; /*回溯*/while (1); 实验步骤1. 录入、修改并测试你的程序，直至正确为止；2. 针对问题实例，实录运行时的输入、输出界面；3. 将你的程序和实录的界面存盘备用。实验报告要求1. 阐述实验目的和实验内容；2. 提交模块化的实验程序源代码；3. 简述程序的测试过程，提交实录的输入、输出界面；4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。思考与练习1 在33个方格的方阵中要填入数字1到N（N10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。# include # define N 12 void write（int a ） int i,j; for （i=0;i3;i+） for （j=0;j0;i+） if （m=primesi） return 1; for （i=3;i*i=m;） if （m%i=0） return 0; i+=2; return 1; int checkmatrix 3= -1,0,-1,1,-1,0,-1,1,3,-1, 2,4,-1,3,-1,4,6,-1,5,7,-1; int selectnum（int start） int j; for （j=start;j=N;j+） if （bj） return j return 0; int check（int pos） int i,j; if （pos=0;i+） if （！isprime（apos+aj） return 0; return 1; int extend（int pos） a+pos=selectnum（1）； bapos=0; return pos; int change（int pos） int j; while （pos=0&（j=selectnum（apos+1）=0） bapos-=1; if （pos=0） void main（） int i; for （i=1;i=N;i+） bi=1; find（）； 2试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。3求出在一个nn的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“”的位置上的皇后就能与这个皇后相互捕捉。 1 2 3 4 5 6 7 8 Q 从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。 求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。得到求解皇后问题的算法如下： 输入棋盘大小值n； m=0; good=1; do if （good） if （m=n） 输出解； 改变之，形成下一个候选解； else 扩展当前候选接至下一列； else 改变之，形成下一个候选解； good=检查当前候选解的合理性； while （m!=0）； 在编写程序之前，先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组，但仔细观察就会发现，这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃是尽可能直接表示那些常用的信息。对于本题来说，“常用信息”并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇后，引入一个一维数组（col ），值coli表示在棋盘第i列、coli行有一个皇后。例如：col3=4，就表示在棋盘的第3列、第4行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设定col0的初值为0当回溯到第0列时，说明程序已求得全部解，结束程序运行。 为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组： （1） 数组a ，ak表示第k行上还没有皇后； （2） 数组b ，bk表示第k列右高左低斜线上没有皇后； （3） 数组 c ，ck表示第k列左高右低斜线上没有皇后； 棋盘中同一右高左低斜线上的方格，他们的行号与列号之和相同；同一左高右低斜线上的方格，他们的行号与列号之差均相同。 初始时，所有行和斜线上均没有皇后，从第1列的第1行配置第一个皇后开始，在第m列colm行放置了一个合理的皇后后，准备考察第m+1列时，在数组a 、b 和c 中为第m列，colm行的位置设定有皇后标志；当从第m列回溯到第m-1列，并准备调整第m-1列的皇后配置时，清除在数组a 、b 和c 中设置的关于第m-1列，colm-1行有皇后的标志。一个皇后在m列，colm行方格内配置是合理的，由数组a 、b 和c 对应位置的值都为1来确定。细节见以下程序： 【程序】 # include # include # define MAXN 20 int n,m,good; int colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1; void main（） int j; char awn; printf（“Enter n: “）； scanf（“%d”，&n）； for （j=0;j=n;j+） aj=1; for （j=0;j=2*n;j+） cbj=cj=1; m=1; col1=1; good=1; col0=0; do if （good） if （m=n） printf（“列t行”）； for （j=1;j=n;j+） printf（“%3dt%dn”，j,colj）； printf（“Enter a character （Q/q for exit）！n”）； scanf（“%c”，&awn）； if （awn=Q|awn=q） exit（0）； while （colm=n） m-; acolm=bm+colm=cn+m-colm=1; colm+; else acolm=bm+colm=cn+m-colm=0; col+m=1; else while （colm=n） m-; acolm=bm+colm=cn+m-colm=1; colm+; good=acolm&bm+colm&cn+m-colm; while （m!=0）； 试探法找解算法也常常被编写成递归函数，下面两程序中的函数queen_all（）和函数queen_one（）能分别用来解皇后问题的全部解和一个解。 【程序】 # include # include # define MAXN 20 int n; int colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1; void main（） int j; printf（“Enter n: “）； scanf（“%d”，&n）； for （j=0;j=n;j+） aj=1; for （j=0;j=2*n;j+） cbj=cj=1; queen_all（1,n）； void queen_all（int k,int n） int i,j; char awn; for （i=1;i=n;i+） if （ai&bk+i&cn+k-i） colk=i; ai=bk+i=cn+k-i=0; if （k=n） printf（“列t行”）； for （j=1;j=n;j+） printf（“%3dt%dn”，j,colj）； printf（“Enter a character （Q/q for exit）！n”）； scanf（“%c”，&awn）； if （awn=Q|awn=q） exit（0）； queen_all（k+1,n）； ai=bk+i=cn+k-i; 采用递归方法找一个解与找全部解稍有不同，在找一个解的算法中，递归算法要对当前候选解最终是否能成为解要有回答。当它成为最终解时，递归函数就不再递归试探，立即返回；若不能成为解，就得继续试探。设函数queen_one（）返回1表示找到解，返回0表示当前候选解不能成为解。细节见以下函数。 【程序】 # define MAXN 20 int n; int colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1; int queen_one（int k,int n） int i,found; i=found=0; While （！found&i i+; if （ai&bk+i&cn+k-i） colk=i; ai=bk+i=cn+k-i=0; if （k=n） return 1; else found=queen_one（k+1,n）； ai=bk+i=cn+k-i=1; return found;实验五 旅行商问题实验目的1掌握分支限界法算法的解题的基本思想和设计方法；2区分分支限界算法与回溯算法的区别，加深对分支限界法的理解；3理解分支限界法算法中的限界函数应遵循正确、准确、高效的设计原则。预习要求1认真阅读教材或参考书, 掌握分支限界法解题的基本思想；2设计状态空间树节点扩展的规范(限界)函数及实现方法；3分析和设计生成解向量各分量可选值的实现方法。实验题某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。view plaincopy to clipboardprint?#include #include using namespace std; /-宏定义- #define MAX_CITY_NUMBER 10 /城市最大数目 #define MAX_COST 10000000 /两个城市之间费用的最大值 /-全局变量- int City_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER; /表示城市间边权重的数组 int City_Size; /表示实际输入的城市数目 int Best_Cost; /最小费用 int Best_Cost_PathMAX_CITY_NUMBER; /最小费用时的路径 /-定义结点- typedef struct Node int lcost; /优先级 int cc; /当前费用 int rcost; /剩余所有结点的最小出边费用的和 int s; /当前结点的深度，也就是它在解数组中的索引位置 int xMAX_CITY_NUMBER; /当前结点对应的路径 struct Node* pNext; /指向下一个结点 Node; /-定义堆和相关对操作- typedef struct MiniHeap Node* pHead; /堆的头 MiniHeap; /初始化 void InitMiniHeap(MiniHeap* pMiniHeap) pMiniHeap-pHead = new Node; pMiniHeap-pHead-pNext = NULL; /入堆 void put(MiniHeap* pMiniHeap,Node node) Node* next; Node* pre; Node* pinnode = new Node; /将传进来的结点信息copy一份保存 /这样在函数外部对node的修改就不会影响到堆了 pinnode-cc = node.cc; pinnode-lcost = node.lcost; pinnode-pNext = node.pNext; pinnode-rcost = node.rcost; pinnode-s = node.s; pinnode-pNext = NULL; for(int k=0;kxk = node.xk; pre = pMiniHeap-pHead; next = pMiniHeap-pHead-pNext; if(next = NULL) pMiniHeap-pHead-pNext = pinnode; else while(next != NULL) if(next-lcost) (pinnode-lcost) /发现一个优先级大的，则置于其前面 pinnode-pNext = pre-pNext; pre-pNext = pinnode; break; /跳出 pre = next; next = next-pNext; pre-pNext = pinnode; /放在末尾 /出堆 Node* RemoveMiniHeap(MiniHeap* pMiniHeap) Node* pnode = NULL; if(pMiniHeap-pHead-pNext != NULL) pnode = pMiniHeap-pHead-pNext; pMiniHeap-pHead-pNext = pMiniHeap-pHead-pNext-pNext; return pnode; /-分支限界法找最优解- void Traveler() int i,j; int temp_xMAX_CITY_NUMBER; Node* pNode = NULL; int miniSum; /所有结点最小出边的费用和 int miniOutMAX_CITY_NUMBER; /保存每个结点的最小出边的索引 MiniHeap* heap = new MiniHeap; /分配堆 InitMiniHeap(heap); /初始化堆 miniSum = 0; for (i=0;iCity_Size;i+) miniOuti = MAX_COST; /初始化时每一个结点都不可达 for(j=0;j0 & City_GraphijminiOuti) /从i到j可达，且更小 miniOuti = City_Graphij; if (miniOuti = MAX_COST)/ i 城市没有出边 Best_Cost = -1; return ; miniSum += miniOuti; for(i=0;ilcost = 0; /当前结点的优先权为0 也就是最优 pNode-cc = 0; /当前费用为0（还没有开始旅行） pNode-rcost = miniSum; /剩余所有结点的最小出边费用和就是初始化的miniSum pNode-s = 0; /层次为0 pNode-pNext = NULL; for(int k=0;kxk = Best_Cost_Pathk; /第一个结点所保存的路径也就是初始化的路径 put(heap,*pNode); /入堆 while(pNode != NULL & (pNode-s) City_Size-1) /堆不空 不是叶子 for(int k=0;kxk ; /将最优路径置换为当前结点本身所保存的 /* * * pNode 结点保存的路径中的含有这条路径上所有结点的索引 * * x路径中保存的这一层结点的编号就是xCity_Size-2 * * 下一层结点的编号就是xCity_Size-1 */ if (pNode-s) = Cit