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

计算机算法分析与设计实验指导书 杨红云 适用专业：软件工程 江西农业大学软件学院 计算机算法分析与设计实验指导书 计算机算法分析与设计是面向设计的，它是计算机科学和软件工程应用的核心。无论是计算机系统、系统软件和解决计算机的各种应用课题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的精确的描述：分治法、贪心法、动态规划、回溯法等。并掌握算法分析的方法。从而将学生分析问题和解决问题的能力提高到高层理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 实验学时：16学时 目录 实验一 递归与分治 4 实验目的：理解递归与分治算法设计思想和方法。 4 实验课时：4学时 4 实验原理： 4 实验题目： 4 1、汉诺塔（hanoi）问题。 4 2、格雷码问题： 5 3、二分查找问题 6 4、快速排序问题 7 思考问题： 8 实验二 动态规划算法 9 实验目的：理解动态规划算法的思想 9 实验课时：4学时 9 实验原理： 9 实验题目： 9 1、多阶段决策问题-最短路径 9 2、长公共子序列问题 12 3、最长最大字段和问题 13 思考问题： 14 实验三 贪心选择算法 15 实验目的：理解贪心选择算法的思想 15 实验课时：4学时 15 实验原理： 15 实验题目： 15 1、单源最短路径 15 2、背包问题 17 3、多机调度问题 17 思考问题： 18 实验四 有哪些信誉好的足球投注网站算法 19 实验目的：理解有哪些信誉好的足球投注网站算法的思想 19 实验课时：4学时 19 实验原理： 19 实验题目： 19 1、n皇后问题 20 2、0-1背包问题 21 3、装载问题 23 思考问题： 23 实验一 递归与分治 实验目的：理解递归与分治算法设计思想和方法。 实验课时：4学时 实验原理： 一个规模为n的复杂问题的求解：可以划分成若干个规模较小n的子问题进行求解，再将子问题的解合并成原问题的解，这便是分治的思想。 若划分成的每一个子问题都与原问题的性质相同，可用相同的求解方法；当子问题规模划分一定小时，子问题的解已知，则逆求原问题的解，这是递归的思想。 实验题目： 1、汉诺设有 A、 C 共 3 根塔座， 在塔座 A 上堆叠 个金盘， 每个盘大小不同， 只允许小盘在大盘之上，最底层的盘最大，如图 所示。现在要求将 A 上的盘全都移到 C 上，在移的过程中要遵循以下原则：每次只能移动 一个盘；圆盘可以插在 A、B 和 C 任一个塔座上；在任何时刻，大盘不能放在小盘的上面。 hanoi问题递归求解思想： 我们把一个规模为n的hanoi问题：1到n号盘按照移动规则从A上借助B移到C上表示为H(A,B,C,n)；原问题划分成如下三个子问题： （1）将1到n-1号盘按照移动规则从A上借助C移到B上H(A,C,B,n-1); （2）将n号盘从A上直接移到C上； （3）将1到n-1号盘按照移动规则从B上借助A移到C上H(B,A,C,n-1); 经过三个子问题求解，原问题的也即求解完成。 hanoi问题递归求解代码： void H(char A,char B,char C,int n) { if(n0) { H(A,C,B,n-1); printf(“%d from %c to %c”,n,A,C); H(B,A,C,n-1); } } 2、格雷码问题： 对于给定的正整数n，格雷码为满足如下条件的一个编码序列： (1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串。 (2) 序列中无相同的编码。 (3) 序列中位置相邻的两个编码恰有一位不同。 例如：n=时的格雷码为：{0, 1}。n=2时的格雷码为：{00, 01, 11, 10}。时的格雷码为：{00, 001, 011, 010,110,111,101,100}。 gray码问题求解思想： 将一个规模n位gray码序列表示为G(n), G(n)以相反顺序排列的序列表示为G’(n)。则gray码的构造规则即子问题的划分规则为：G(n+1)= 0G(n) 1G’(n) 。 gray码问题代码：G(n+1)= G(n) 0G’(n)1 void gray(int n,char a[][256]) { if(n==1) { strcpy(a[0],0); strcpy(a[1],1); return; } gray(n-1,a); int i,p,q; p=int(pow(2.0,(n-1)*1.0)); q=int(pow(2.0,n*1.0)