算法设计与分析实验指导书bfm

《算法设计与分析》实验指导书运算机学院信息安全系毕方明本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对教学内容的理解，尤其是一些算法的实现及其应用，培育学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的熟悉。上机实验一般应包括以下几个步骤：（1） 、预备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2） 、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3） 、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情形所作的分析。本书共分阶段4个实验，每一个实验有大体题和提高题。大体题必需完成，提高题按照自己实际情形进行取舍。题目不限定如下题目，可按照自己兴趣爱好做一些与实验内容相关的其他题目，如动态计划法中的图象紧缩，回溯法中的人机对弈等。其具体要求和步骤如下：实验一分治与递归（4学时）大体题一：大体递归算法一、 实验目的与要求1、 熟悉C/C++语言的集成开发环境；2、 通过本实验加深对递归进程的理解二、 实验内容：掌握递归算法的概念和大体思想，分析并掌握“整数划分”问题的递归算法。三、 实验题任意输入一个整数，输出结果能够用递归方式实现整数的划分。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序;验证分析实验结果；整理出实验报告。大体题二：棋盘覆盖问题一、实验目的与要求一、 掌握棋盘覆盖问题的算法；二、 初步掌握分治算法二、 实验题：盘覆盖问题：在一个2kX2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格之外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、 实验提示voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,<m[k].s)k=i;}returnk;提高题一：用贪婪算法求解最小生成树、实验要求与目的1、 熟悉贪婪算法的大体原理与适用范围。2、 利用贪婪算法编程，求解最小生成树问题。二、实验内容1、 任选一种贪婪算法(Prim或Kruskal)，求解最小生成树。对算法进行描述和复杂性分析。编程实现，并给出测试实例提高题二：汽车加油问题一、实验目的与要求一、 掌握汽车加油问题的算法；二、 进一步掌握贪婪算法；二、 实验题一辆汽车加满油后能够行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停泊加油。并证明你的算法能产生一个最优解。三、 实验提示把两加油站的距离放在数组中，a[1..n]表示从起始位置开始跑，通过n个加油站，a[k]表示第k-1个加油站到第k个加油站的距离。汽车在运行的进程中若是能跑到下一个站则不加油，不然要加油。（算法略）实验四回溯算法和分支限界法（2学时）大体题一：符号三角形问题一、实验目的与要求一、 掌握符号三角形问题的算法；二、 初步掌握回溯算法；二、实验题图下面都是“-”。下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。++-+-+++----+-+++-在一般情形下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。三、实验提示voidTriangle::Backtrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){pEg；count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]Ap[j-1][t-j+2];count+=p[j][t-j+1];}Backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}大体题二：0—1背包问j、实验目的与要求、掌握0—1背包问题的回溯算法;、进一步掌握回溯算法；二、实验题：给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？三、实验提示template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){n)。旅行路径前缀1的开销为0，即cc=0，而且，rcost=n&&i=1时MinOut。在程序中，bestc给出了当前能找到的最少的花费值。初始时，由于没有找到任何旅行路径，因此bestc的值被设为NoEdge。旅行商问题的最小花费分枝定界算法templateTAdjacencyWDigraph::BBTSP(intv[]){s++;H.Insert(E);}elsedelete[];}else{Insert(N);}}//结束可行的孩子delete[];}//对本节点的处置结束try{(E);}//取下一个E-节点catch(OutOfBounds){break;}//没有未处置的节点}if(bestc==NoEdge)returnNoEdge;//没有旅行路径//将最优路径复制到v[1:n]中for(i=0;i<n;i++)v[i+1]=；while(true){//释放最小堆中的所有节点delete[];try{(E);}catch(OutOfBounds){break;}}returnbestc;提高题二：用回溯法求解跳马问题、实验要求与目的1、掌握回溯法的大体原理。2、利用回