《【精品】计算机算法设计与分析实验指导书》由会员分享，可在线阅读，更多相关《【精品】计算机算法设计与分析实验指导书（8页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析实验指导书本书是为配合算法分析与设计实验教学大纲|仃编写的上机指导，其目的是使学生消 化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程 和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：(1) 准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。(2) 上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题， 最好独立解决。(3) 上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、対 运行情况所作的分析。本书共分阶段6个实验，英具体要求和步骤如下：实
2、验一分治算法(2学时)一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题设aO:n-l是一-个己排好序的数纽，请改写二分搜索算法，使得当搜索元素x不在数 组中时，返冋小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中 时,i和j相同，均为x在数组中的位置。三、实验提示用i，j做参数，且采用传递引用或指针的形式带冋值。bool Bi nary Search (int a, in t n, i n t x, int& i, int& j)int left=0;int right二nT ;while(leftamid)left二mid+1;elseright二
3、midT;i=right;j=left;return false;实验二 动态规划算法(2学时)一、实验目的与要求1、熟悉最长公共子序列问题的算法;2、初步掌握动态规划算法;二、实验丿若给定序列X= xl, x2,xm,则另一序列Z=zl, z2,，zk,是X的子序列是指存在一个严格递增下标序歹!J il, i2,，ik使得对于所有j二1,2,k有：zj=xij0例如，序列 Z=B, C, D, B是序列X二A, B, C, B, D, A, B的子序列,相应的递增下标序列为2, 3, 5, 7。给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列吋，称Z是序列X 和Y的公共子序列。给
4、定2个序列X=xl, x2,xm和Y=yl, y2,yn,找出X和Y的最长公共子序列。 三、实验提示#include stdlib. h#include string, hvoid LCSLength (char *x , char *y, int in, int n, int *c, int *b)int1 ,j;for(i二 1;1=m；i+)for(i=1;1=n;i+)for(i=1;1=Hl；i+)for(j =1:;j=ci j-1) cij=ci-lj; bij=2;elsecij=cij-l;bi j二3;void LCS(int i , int j, char *x , in
5、t *b) if (i =0 :| j二二0) return;if (bij= 1)LCS(i-l, j-l,x, b); printf (”c： xi);else if (bij= 2)LCS(i-l, j, x,b);else LCS (i, j-1, x, b);实验三贪心算法(2学时)一、实验目的与要求1、熟悉最优装载问题的算法;2、初步掌握贪心算法；二、实验题给出n个物体，第i个物体重量为wz选择尽量多的物体，使得总重最不超过C-三、实验提示1、山于目标是物体的“数量”尽量多，所以装重的没有装轻的划算。只需把所有物体 按重量从小到大排序；2、依次选择每个物体，直到装不下为止。3、实际
6、上就是-种贪心法，因为每次都是选择能装下的最轻的物体，是一种“只顾眼 前”的策略，这样的策略却能保证得到最优解。完整的程序如下：#include #define N 100 int xN,讥N, tN;void Sort(int w, int t, int n)/将重量数组w从小到大排序,数纟11 ti表示数纽r第i小的元素在数纟|v中的下标 int i, j, temp, k, wl N;for(i=l;i=n;i+) /设辅助数纽.wl的作用是用于排序，原数纽w元素不移动 wl i=wi;for(i=l;i=n;i+)/初始化数纽t,记下原重量数纽w中每个元素的位置ti=i；for(i=l
7、;in;i+) /用选择排序法进行排序k=i;for(j=i+l;jwlj) k=j;if(k!=j) /将数组w中的元素进行交换，同时数纽.t中元素也交换/排序完成后，ti应为重量第i小的物体在原重量数纽*所处的位置(下标) temp二ti;ti=tk;tk二temp;temp二wli;wli=wk;wlk=temp;void Loading(int x, int w, int c,int n)int i;Sort (w, t, n) ; /对数组w进行排序,数组t记下数组w中元素的大小关系 for(i=l;i=n;i+)xi=0;/初始化数组 xfor(i=l;i=n & wti=c;i+
8、)贪心选择/数纽.x表示是否选择物体的状态，xti=l表示选择重量第i小的物体c-=wti;int mtiinOint i, n, c;int max二0;while(scanf (%d%d, &n, &c)! =EOF) /输入物体数 n,总重量 cfor(i=l ;i=n;i+)/输入重量数组w的元素scdnf&vi);Loading(x, w, c, n);printfC选择的物体为：n)；for(i=l;i二n;i+)/当xi=l选择数组w中第i个物体的wi(重量);当xi=0不选择 printf(”3d,xi);nidx+=wi*xi;/计算最大总重量maxprintf(n);pri
9、ntf (选择物体的最大总重昴为：%dn, max);运行结果：输入20 200125 89 142 65 298 100 150 86 88 42 55 16 129 238 45 110 217 168 180 80 输出结果选择的物体为：11110111111110110111选择物体的最大总重量为：1887说明：上而输出的一串0和1数字是数组x中的值，为1表示选择重量数纽w对应位置 的物体，否则不选择。实验四回溯算法(2学时)一、实验目的与要求1、掌握01背包问题的冋溯算法；2、进一步掌握冋溯算法；二、实验题：给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如 何选择装入背包的物殆，使得装入背包中物殆的总价值最大？三、实验提示tcmplateTypep Knap:Bound (int i)/计算上界Typew cleft = c - cw; / 剩余容量Typep b 二 cp;/以物品单位重量价值递减序装入物品while (i = n & wi = cleft) cleft -二 wi;b += pi； i+；/装满背包if (i H（1000）;T *Min0ut = new T n+1
