《《算法分析与设计》_实验指导书》由会员分享，可在线阅读，更多相关《《算法分析与设计》_实验指导书（29页珍藏版）》请在金锄头文库上搜索。
1、 编编 著著 说说 明明 本书是为配合算法分析与设计实验教学大纲而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1） 、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2） 、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3） 、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。本书共分 810 个实验，其具体要求和步骤如下：目目
2、录录实验一、C/C+环境及递归算法.实验二、递归与分治策略.20实验三、动态规划算法（一）.24实验四、动态规划算法（二）.27实验五、贪心算法（一）.30实验六、贪心算法（二）.32实验七、回溯法（一）.35实验八、回溯算法（二）.37实验九、分支限界法.39实验十：随机化算法（选学）.44实验二、递归与分治策略实验二、递归与分治策略一、实验目的与要求一、实验目的与要求1、进一步熟悉 C/C+语言的集成开发环境；2、通过本实验加深对递归与分治策略的理解和运用；二、实验内容：二、实验内容：1、分析并掌握“棋盘覆盖问题”的递归与分治算法示例；2、分析并掌握“二分搜索问题”的递归与分治算法示例；3
3、、练习使用递归与分治策略求解众数问题或集合划分问题；三、实验题三、实验题 众数问题众数问题：给定含有 N 个元素的多重集合 S，每个元素在 S 中出现的次数称为该元素的重数，多重集合 S 中重数最大的元素称为多重集合 S 的众数，众数的重数称为多重集合 S 的重数，试求一个给定多重结合的重数和众数；例如：S=a,b,b,b,f,f,4,5的重数是 3，众数是 b 集合划分问题：集合划分问题：N 个元素的集合1，2，N可以划分为若干个非空集合的子集，例如，当 N=4 时，集合1，2，3，4可划分为 15 个不同的非空子集如下：1，2，3，4； 1，2，3，4； 1，3，2，4；1，4，2，3；
4、2，3 ，1，4； 2，4，1，3 ；3，4 ，1，2； 1，2 ，3，4； 1，3 ，2，4；1，4 ，3，2 ； 2，3，4，1； 1，3，4，2；1，2， 4，3； 1，2，3，4； 1，2，3，4；给定正整数 N，计算出 N 个元素的集合1，2，N可以划分多少个非空集合的子集；四、实验步骤四、实验步骤 1理解递归和分治策略的基本思想和算法示例；2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、递归与分治算法示例程序五、递归与分治算法示例程序1、棋盘覆盖问题、棋盘覆盖问题：在一个 2k2k 个
5、方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的 4 种不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖；void chessBoard(int tr, int tc, int dr, int dc, int size)if (size = 1) return;int t = tile+, / L 型骨牌号s = size/2; / 分割棋盘/ 覆盖左上角子棋盘if (dr = tc + s) / 特殊方格在此棋盘中chessBoard(tr, tc+s, dr,
6、dc, s);else / 此棋盘中无特殊方格boardtr + s - 1tc + s = t; / 用 t 号 L 型骨牌覆盖左下角/ 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);/ 覆盖左下角子棋盘if (dr = tr + s else boardtr + stc + s = t; / 用 t 号 L 型骨牌覆盖左上角chessBoard(tr+s, tc+s, tr+s, tc+s, s); / 覆盖其余方格2、二分搜索问题：、二分搜索问题：、设：a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x 不在数组中时，返回小于
7、 x 的最大元素的位置 I 和大于 x 的最大元素位置 j。当搜索元素在数组中时，I 和 j 相同，均为 x 在数组中的位置。、设：有 n 个不同的整数排好序后存放于 t0:n-1中，若存在一个下标I，0in，使得 ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为 O（logn） 。、用 I，j 做参数，且采用传递引用或指针的形式带回值。bool BinarySearch(int a,int n,int x,intint right=n-1;while(leftamid)left=mid+1;elseright=mid-1;i=right;j=left;return
8、 false;int SearchTag(int a,int n,int x)int left=0;int right=n-1;while(leftamid)right=mid-1;elseleft=mid+1;return -1;实验三、动态规划算法（一）实验三、动态规划算法（一） 一、实验目的与要求一、实验目的与要求通过动态规划算法的示例程序理解动态规划算法的基本思想；运用动态规划算法解决实际问题加深对动态规划算法的理解和运用；二、实验内容：二、实验内容：分析并掌握“最长公共子序列” 问题的动态规划算法求解方法；练习使用动态规划算法求解“游艇租用”问题；三、实验题三、实验题 游艇租用问题游
9、艇租用问题：长江旅游俱乐部在长江上设置了 N 个游艇出租站 1，2，3，N,游客在这些站中租用游艇，并在下游的任何一个游艇出租站归还，游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j),1i=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;void LCS(int i ,int j, char *x ,int *b)if (i =0 | j=0) return;if (bij= 1)LCS(i-1,j-1,x,b);printf(“%c“,xi);else if (bij= 2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b)
10、;实验四、动态规划算法（二）实验四、动态规划算法（二）一、实验目的与要求一、实验目的与要求 1、通过动态规划算法的示例程序进一步理解动态规划算法的基本思想；2、运用动态规划算法解决实际问题进一步加深对动态规划算法的理解和运用；二、实验内容：二、实验内容：1、分析并掌握“最大字段和” 问题的动态规划算法求解方法；2、练习使用动态规划算法求解“石子合并”问题； 三、实验题三、实验题 石子合并问题石子合并问题：在一个圆形操场的四周摆放着数量相同或不同的 N 堆石子，现将N 堆石子有序地合并一堆，规定每次只能将相邻的 2 堆石子合并成新的一堆石子，并将新的一堆石子数记为该次合并的得分，试设计一个算法，
11、计算出将 N 堆石子合并成一堆的最小和最大得分；四、实验步骤四、实验步骤 1理解动态规划算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、动态规划算法示例程序五、动态规划算法示例程序最大字段和问题最大字段和问题：若给定个整数（可能有负整数）组成的序列，求nnaaa,21L该序列中形如形如， （ ）的字段和的最大值。 jikkanji1int MaxSum(int n,int *a,int for(int i=1;isum)sum=thissum;besti=i;bestj=j;
12、return sum;int MaxSum(int n,int *a,int for(int i=1;isum)sum=thissum;besti=i;bestj=j;return sum; 实验五、贪心算法（一）实验五、贪心算法（一）一、实验目的与要求：一、实验目的与要求：1、通过贪心算法的示例程序理解贪心算法的基本思想；2、运用贪心算法解决实际问题加深对贪心算法的理解和运用；二、实验内容：二、实验内容：1、分析并掌握“多机调度” 问题的贪心算法求解方法；2、练习使用贪心算法求解“会场安排”问题； 三、实验题三、实验题 会场安排问题会场安排问题：假设在足够多的会场里安排一批活动（N 个活动） ，每个活动事先给定活动的开始时间和结束时间，试用贪心算法求出最少需要多少会场，并求出每个活动安排在第几个会场；例如:5 个活动的开始时间和结束时间和会场安排如下活动 i12345开始时间112252736结束时间2328358050会场安排一二一三一四、实验步骤四、实验步骤 1理解贪心算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、贪心算法示例程序五、贪心算法示例程序多机调度问题多机调度问题：要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加
