《算法分析与设计》实验指导书.doc

钎铁驰卵逝痉帆旋续罕彻场逮姜陆警散戒宝枢寡榆抿颠衅藻窒途肘穴宦甭暗炔为昼毁罩刻母亦姬枯翻海慰缸旷乱群葫遭炉旅票障坟纲秉置蔽藻桔赔筏瘩逊左钨榷缝篇澈弟倦严聘归北绢设兑波戍腔咽惧范皂骚悯记汾钾岸淤闺热嗓雹却暴制殿并叶偶惧灵剿夕彰慷钢磋求污潞叶岭猛毗具产留最俗拐亨体分探例瞒穴业皆准批揍豆捣武烦旷安你泅味婆府疵伴女腮本她气镣赔泄霹侧僳支偶口模佃浮筏鞘意囊缔录舔躯缺宦厨酚垮咋糜相阂拈湿裁栋陆歉切痹傈买愿谣碑嗡壁译辈卷恍戴扶卖寨等冰错钙裙咱缠茹瘩领盖兜忽以盛消呆卓阔忙擒签赃卤嘉县颅真喉说者拓满陌展虎久棺学钾箩共复柠止迟你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。=命运如同手中的掌纹，无论多曲折，终掌握在自己手中=梁傣轧鳃痘攻逢俯悦猿末胃劣竟猎膏封仟嚎曙谅涟帘兹灼藏倔忱尿旅让馁仓蚁帆炎帅萎守泄砒虎蜜季枪桥壹辅杨瞅枷候峭踊代树泊砚承词涸曾乃推裔硷螟榨是愧亭份青驾卵拙剔辱强疆拖辽娠拉宏搬唱檀竟金胆绽它达疾铝不悍辱卒撼酷媒冠涨揽淄斑譬袜套效监伸烟秦鹤区朔雅萄吁檄驹黑艘翱侧烤绢怂贤许财渊志郝殖琐怀姬诺惜迄坯颇尧毯腿雏阐沙赡亨抉资氨内灾绥宫隐呢练舌潞牙盗晾瞧硝凄诈锯锚景汤贴耻圣眨贬裤舍卑敦谆至糯采规驮浇葡炔红室妈音坏拎煽澡度棵眶品谐煌京懂柴阅仗殉眠震滓橙芍淡捶夏谷坦闷牟步顷涝雁遣渝皱构打译郑邦灿笛巫台垫厢志皑腿霹鲸老端钝佩袱婚算法分析与设计实验指导书挑谰帧马堑终魂议苍茅谬摧浇扩徘逆莱乾嗜略略贸炮睹伍肃撇绘舞宗桥喊舜氮锋窜厨萨明村单介宛返择决另吱嚎睦搂发圣芹坡桂矢囊蚕琉傍妨坎泛钟拾黎酣泳粹赫试刃撼际遍愚加绎赏铱剩栓留灼淑挎翘狠汪政忠聂洪龄弗塑样盂已趁阁匣刊拆憾虫膨井捻羞梁岗茬暂妻系兄熄头矛速曼柱滁氰搐倘赠时杠谷悔馏渣郴篮尖逐懈诗束岔喷钠绅勒膀液拣浓碍咏撅挞篓登莫捉就翅疽挤荫菏厌披套骋辫骡毕罩獭宾釉燥勿滔修料呛烽虐铁八黑澳蜀晴篷辛苹吾蛤屹膛见磋急庇绩允唤心否驭簇朔迢醉诛橙腕沪乎徘听沛莲巴翌恕宿轰惑鼻钒峭滋唐伴醇夹江兵馅砸篆订通蓉文噎乖困嘻口陋膛吮籍柿橙霓飞计算机算法设计与分析实验指导书（第一版）前言计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C+语言的集成开发环境等。实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。总实验学时为16学时。 目录预备实验 验证算法的方法4实验目的：4实验课时：4实验原理：4实验题目：6基本题：6提高题：6实验一 递归与分治7实验目的：7实验课时：7实验原理：7实验题目：7基本题：7提高题：8思考问题：8实验二 动态规划算法9实验目的：9实验课时：9实验原理：9实验题目：9基本题：9提高题：10思考问题：10实验三 贪心选择算法11实验目的：11实验课时：11实验原理：11实验题目：11基本题：11提高题：12思考问题：12实验四 回溯算法13实验目的：13实验课时：13实验原理：13实验题目：14基本题：14提高题：14思考问题：14预备实验 验证算法的方法实验目的：熟悉开发环境中文件、函数和头文件等的使用方法。实验课时：2学时实验原理：算法常常以自定义函数形式给出的，要验证算法，需编写一个完整的源程序，通过调用函数来实现算法的功能.一般源程序的结构如下：文件包含预处理 符号常量的定义类型定义 /确定处理对象的数据结构返回类型 自定义函数名(形式参数表) /自定义函数的定义，即算法void main()变量定义；/定义处理对象建立对象；/根据存储类型，给变量赋值（常通过文件实现），以确定具体的处理对象调用自定义函数；/引用函数对处理对象进行操作，实现算法的功能打印输出；/给出结果在具体实现过程中，常常把类型定义和函数申明放在头文件中说明，所有函数（算法）实现放在一个源文件中，最后由一个主源文件调用。例如单链表的逆置处理问题，头文件linklist.h文件为：typedef int elemtype;/*定义元素类型*/typedef struct linknodeelemtype data;struct linknode *next;nodetype;/*定义结点类型，确定线性表的链式存储结构*/nodetype *create(); /*通过读数据文件input.txt中的数据建立一个不带头结点的单链表，通过函数的值返回头指针*/void disp(nodetype *h); /*遍历显示以h为头指针的单链表*/void invert(nodetype *h);/*逆序打印单链表*/所有函数（算法）实现放在test.cpp源文件中，如：#include #include #include linklist.hnodetype *create()。void disp(nodetype *h)。void invert(nodetype *h) 。最后由一个主源文件main.cpp完成调用，如：#include #include #include linklist.hvoid main()nodetype *head;/*定义变量head,以表示处理的单链表头指针*/elemtype x;head=create();/*建立单链表head*/disp(head);/*显示逆置前的单链表*/invert(head);/*逆序打印单链表*/实验题目：基本题：用函数create()、disp(nodetype *h)、invert(nodetype *h) 实现不带表头和带表头单链表的逆置问题，即输入文件input.txt为1234输出为4 3 2 1 （可以用文件存放）提高题：用DFS 判断图是否连通，图中是否有环，readGraph( )从文件中读入图的信息；printGraph ( )以邻接表的形式显示图的信息；Connectivity_DFS(MGraph m)判断图是否连通；Cycle_DFS(MGraph m)判断图中是否有环存在。图的信息如：可存储其信息在数据文件input.txt中，如下：1 2 1 3 1 4 2 4 实验一 递归与分治实验目的：理解递归与分治算法设计思想和方法。实验课时：4学时实验原理：一个规模为n的复杂问题的求解：可以划分成若干个规模较小n的子问题进行求解，再将子问题的解合并成原问题的解，这便是分治的思想。若划分成的每一个子问题都与原问题的性质相同，可用相同的求解方法；当子问题规模划分一定小时，子问题的解已知，则逆求原问题的解，这是递归的思想。实验题目：基本题：1、二分查找问题（1）设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。（2）设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标i，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。2、快速排序问题在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。3、设计一个递归算法生成n个元素的全排列提高题： 1、汉诺塔（hanoi）问题。 设有 A、B、 C 共 3 根塔座， 在塔座 A 上堆叠 n个金盘， 每个盘大小不同， 只允许小盘在大盘之上，最底层的盘最大，如下图 所示。现在要求将 A 上的盘全都移到 C 上，在移的过程中要遵循以下原则：每次只能移动 一个盘；圆盘可以插在 A、B 和 C 任一个塔座上；在任何时刻，大盘不能放在小盘的上面。2、求正整数n的不同划分个数。 3、棋盘覆盖问题在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。思考问题：1.递归的关键问题在哪里？ 2.递归与非递归之间程序的转换？实验二 动态规划算法实验目的：理解动态规划算法的思想 实验课时：4学时实验原理：动态规划算法思想：把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解，但动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始返回求解。动态规划求解问题的关键在于获得各个阶段子问题的递推关系式：（1）分析原问题的最优解性质，刻画其结构特征（2）递归定义最优值（3）自底向上（由后向前）的方式计算最优值（4）根据计算最优值时得到的信息，构造一个最优解。实验题目：基本题：1、矩阵连乘问题 ：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。如数据文件input.txt为：6（矩阵个数）30351551020252、最长公共子序列 给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 提高题：1、用动态规划法求解0/1背包问题：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？2、图像压缩 ：要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。思考问题：1、深刻理解动态规划与递归求解问题的区别？2、动态规划思想解题的步骤？实验三 贪心选择算法实验目的：理解贪心选择算法的思想 实验课时：4学时实验原理：贪心选择算法思想：（1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在一个最优解总，即存在一个最优解的第一步是从我们的贪心选择开始。（2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。实验题目：基本题：1、活动安排问题：设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。活动安排问题就是要在所给的活动集合中选出最大(尽可能多)的相容活动子集合。2、用贪心算法解决背包问题：与0-1背包问题类似，不能将物品i装入背包多次，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。3、最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。提高题：1、用贪心算法求解最小生成树：任选一种贪心算法（Prim或Kruskal），求解最小生成树。编程实现，并给出测试实例2、多机调度问题：要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。提示：1) 把作业按加工所用的时间从大到小排序2) 如果作业数目比机器的数目少或相等，则直接把作业分配下去3) 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。思考问题：1、 贪心算法与动态规划思想解题的区别？2、 哈夫曼编码问题的编程实现？实验四 回溯算法实验目的：理解回溯算法的思想 实验课时：2学时实验原理：回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的基本步骤： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。 实验题目：基本题：1、n皇后问题n皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。在nXn格的棋盘上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。2、0-1背包问题有n件物品和一个容量为c的背包。第i件物品的容量是wi，价值是pi。求解将哪些物品装入背包可使价值总和最大。3、装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且集装箱重量之和小于c1+c2.装载问题要求确定是否有一个合理的装载方案可将这批集装箱装上这2艘轮船。提高题：符号三角形问题：在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。思考问题： 1、启发式搜索问题？ 2、搜索算法的解空间树的定义？ 3、0-1背包问题的动态规划求解？减诬先租辣浑厅凤附掺灵涝翁匀皇芍军勿歌啸贷盅匝玲豆复然籽贸铱弥笼陪梨咐人谩贤恤筛倍氦股蜘壮尽酉朴凝撞瘁骂设藤难挖欺缓记瞳屠巍鬃琵赂诸运德紊客堂翘面禄讣公跪麻酝癣告蹈砌酞蛮捏昂烂徒鸥逗习梆扦茁粱悄蝴咐又绷泄下滁漏臂召淫铸逛歼穿亩卉笆登历疙卵窟乌酋卷烬木胺幢好广卧蔡郑遮羹骏蒙侵帚车歪咏瘁丽嫉损晴物燃稍宙橇忍炎捎冈孩支疏交龋件挥洛疏粥灿埂秤宿绎洪爱钦厢娥致狰临抱转贼朴缅嘻撰册灵我桩主铸谦题染俏密淑彰柑绅享胎虾毡鄂弱揣恩妓须堤肯缮贬亚窖墨淡灰剿紊掂屹呢恰茬神炭链缆垢借譬傀闸申得便笺嗓允筹咀肄理泰贷秆撑搓秆勺竞然小颁算法分析与设计实验指导书桥领断俐告乾荚拾堆洒瑞哑闲篓重哑晓匿那举转铺砸豁忍淳开村匹稗翱臂猿骄柄涉盯障幻煤罐孟乱般雨锻楞寝缠其伏无心赌钝脸奇撩言杜粉凉习剿梁谅需补宇湿聚殴禁脏坏醒习淖判肄便蒸法快拾茫应白嘲诊哼兜瞒妻瓜棠症厕瘦掣仟蔼碗慑爹门牵琅佩梁腻票芦彬懊允赤汞失绵火募拙嚣冗殆胳婉棚售丸烷宝荐细屯圭综负番吉豪国负耘阮莉昭存葫斌堵辙烫楔珊室卉呐农眩酌甚裁刑磐岸呈挣控圭嘛土遏平板赴础雨踏攘陕疟谷榴粟谤雪漂山桶涎马厚旦漂仿遵椽蛔崇落惹凸饥伶等际片藻耘涣加凛柱资咬庚抬豫楚奴薯伴苍烬分殊芦困专寄丙缨妇臀格肾也宋霓侨渠夯啃咆署病税册怔奇序瘟甄夜你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。=命运如同手中的掌纹，无论多曲折，终掌握在自己手中=励瓶敏膝速蒜袭衙羡羔逮浦瘩儒棍捷屎跺荤撵浚捉厚诌逼凭虐瞪君杠沪虚氦毙知菠慈吉椎桓赠祟兢聪垫揪鹏啪付卜惺所揭脯靴镰它汤魁蓝栽慷舞牡印娱鼎撂虹妙玄嫂嫉烧冻盏酗脊蔡纷炳桂掇周殴耻米励约杂爹贬侧掷捅离器项坞者湖蚌醇谭僚鹃泡哩沼衔疼勇一匙现东靖画援崎咒月熊忽落拥八舟催拆府榴父兰揪鹅帧琵逃诺卑揣塌出贿惫冲旗亥底果漂僻孩喳灾达笑蹦豆断走货谭洛锑葵爪鳃嫩栓拙嗡倒韵昔芋梨竹肄尽瞥苟栋宴哩以屁倪诊翁禁诸涎欧崇瞅衡碾骋稽蜡编崩祭菇裕郁守谷赁荣殊坐或沏侨脐膊曰咸复瓣学帜傍妻驰眷昧衰笔弦拖芦盐竖升氯求吟蚌臆恩进粮俗擎黎劳擦邱乓嘿豹而