《计算机算法设计与分析》实验指导书（第一版）前言计算机算法分析与设计是面向设计的，它是计算机科学的核心。
无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。
通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。
前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。
开发环境不限，本书采用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 linknode{elemtype data;struct linknode *next;}nodetype;/*定义结点类型，确定线性表的链式存储结构*/nodetype *create();/*通过读数据文件input.txt中的数据建立一个不带头结点的单链表，通过函数的值返回头指针*/void disp(nodetype *h); /*遍历显示以h为头指针的单链表*/void invert(nodetype *h);/*逆序打印单链表*/所有函数（算法）实现放在test.cpp源文件中，如：#include <stdio.h>#include <malloc.h>#include "linklist.h"nodetype *create(){。
}void disp(nodetype *h){。
}void invert(nodetype *h){。
}最后由一个主源文件main.cpp完成调用，如：#include <stdio.h>#include <malloc.h>#include "linklist.h"void 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 21 31 42 4实验一递归与分治实验目的：理解递归与分治算法设计思想和方法。
实验课时：4学时实验原理：一个规模为n的复杂问题的求解：可以划分成若干个规模较小<n的子问题进行求解，再将子问题的解合并成原问题的解，这便是分治的思想。
若划分成的每一个子问题都与原问题的性质相同，可用相同的求解方法；当子问题规模划分一定小时，子问题的解已知，则逆求原问题的解，这是递归的思想。
实验题目：基本题：1、二分查找问题（1）设a[0:n-1]是一个已排好序的数组。
请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
（2）设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i ＜n，使得t[i]=i，设计一个有效的算法找到这个下标。
要求算法在最坏的情况下的计算时间为O（logn）。
2、快速排序问题在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。
3、设计一个递归算法生成n个元素的全排列提高题：1、汉诺塔（hanoi）问题。
设有A、B、C 共3 根塔座，在塔座A 上堆叠n个金盘，每个盘大小不同，只允许小盘在大盘之上，最底层的盘最大，如下图所示。
现在要求将 A 上的盘全都移到C 上，在移的过程中要遵循以下原则：每次只能移动一个盘；圆盘可以插在A、B 和 C 任一个塔座上；在任何时刻，大盘不能放在小盘的上面。
2、求正整数n的不同划分个数。
3、棋盘覆盖问题在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的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学时实验原理：回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。