算法设计与分析的实验报告

《算法设计与分析的实验报告》由会员分享，可在线阅读，更多相关《算法设计与分析的实验报告（13页珍藏版）》请在装配图网上搜索。

1、实验一 递归与分治策略一、实验目的1加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2提高学生利用课堂所学知识解决实际问题的能力；3提高学生综合应用所学知识解决实际问题的能力。二、实验内容1、 设aO:n-l是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返 回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同， 均为x在数组中的位置。 写出三分搜索法的程序。三、实验要求（1）用分治法求解上面两个问题；（ 2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a0

2、:n-1是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元 素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大 小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果 xa2（n-1）/3,贝帜需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时， 则在数组中间的三分之一部分中继续搜索X。五、实验结果分析二分搜索法：；.汽E: I新建文杵夹erDebuger. exePPress any key to continue时间复杂性：二分搜索

3、每次把搜索区域砍掉一半，很明显时间复杂度为O(logn)。(n代表集合中元素的 个数) 三分搜索法：O(3log3n) 空间复杂度：0(1)。六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也 理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只 看是不够的还要动手分析一下，这样才能学好算法。七、附录：(源代码)二分搜索法：#include#includeint binarySearch(int a,int x,int n)int left=0;int right=n-1;int i,j;while(leftamiddle)

4、left=middle+1;else right=middle-1;i=right;j=left;return 0;int main() int a10=0,1,2,3,4,5,6,7,8,9;int n=10;int x=9;if(binarySearch(a,x,n)coutvv找到vvendl;elsecoutvv找不到vvendl;return 0;实验二 动态规划求解最优问题一、实验目的1加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2提高学生利用课堂所学知识解决实际问题的能力； 3提高学生综合应用所学知识解决实际问题的能力。二、实验内容1、用两台处理机

5、A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是ai, 若由机器B来处理，则所需要的时间是bi。由于各作业的特点和机器的性能关系，很可 能对于某些i，有ai=bi，而对于某些就j，j!=i,有aibj。既不能将一个作业分 开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这 两台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总的时 间)。研究一个实例：(a1,a2,a3,a4,a5,a6)=(2, 5, 7, 10, 5, 2); (b1,b2,b3,b4,b5,b6)= (3, 8, 4, 11, 3, 4)。2、长江游艇俱乐

6、部在长江上设置了 n个游艇出租站1，2n。游客可在游艇出租站租用 游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金 r (i，j) 1二ij二n。设计一个算法，计算出游艇1到游艇n所需最少租金。三、实验要求(1)用动态规划思想求解最优问题；( 2)再选择自己熟悉的程序设计语言实现所有算法；(3)分析所设计的算法的时间/空间复杂性。四、实验过程设计(算法设计过程)1、对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理 完这n个作业的时间最短。2、对于给定的游艇出租站i到游艇出租站j之间的租金为r (i, j), 1二ij二n,计算出游 艇

7、1到游艇n所需最少租金。五、实验结果分析 独立任务最优调度问题：2 4 52 5 7 111为为为为为为a ba bab abba aaabb abbaba页页页页页页R1ET.E-ET.R1ET.E-ET.EET.E-ET. 口 T-I口 T-I口 T-I口 T-I口 T-I口 T 右1- - - 1- - - 1- - - 1- - - 1- - - 1- - 务务务务务务 任任任任任任 项项项项项项asssss兀 .亠mm 要要要要要要租用游艇问题：时间复杂性：独立任务最优调度问题：O(n*Sum)六、实验体会对于算法来说,没有最好,只有更好,算法的结果不一定是最佳答案,但至少是最接近最

8、佳 答案的。在权衡算法时间复杂度和空间复杂度的情况下,找到一个在时间和空间都能接受的 算法才是上上之策。七、附录：(源代码)独立任务最优调度问题：using System;namespace zyddclass Programstatic void DlrwZydd(int a, int b, int n, int least, string result)for (int i = 0; i n; i+)leasti = 99;int aSum = 0, bSum = 0;for (int i = 0; i n; i+)aSum += ai; bSum += bi;int Sum = 1 +

9、Math.Min(aSum, bSum); int, timeA = new intn, Sum;int, timeB = new intn, Sum;int, timeMax = new intn, Sum;char, who = new charn, Sum;char tempRlt = new charn;for (int i = 0; i = a0; i+) timeA0, i = i; if (i a0)timeB0, i = b0; who0, i = b;elsetimeB0, i = 0; who0, i = a;timeMax0, i = Math.Max(timeA0, i

10、, timeB0, i);if (a0 = b0) least0 = a0; tempRlt0 = a; else least0 = b0; tempRlt0 = b; result0 = new String(tempRlt);for (int k = 1; k n; k+)int tempSum = 0;for (int temp = 0; temp = k; temp+) tempSum += atemp;for (int i = 0; i = tempSum; i+) timeAk, i = i;if (i ak) timeBk, i = timeBk - 1, i + bk; who

11、k, i = b;elseif (timeBk - 1, i + bk) = timeBk - 1, i - ak) timeBk, i = timeBk - 1, i + bk; whok, i = b;else timeBk, i = timeBk - 1, i - ak; whok, i = a; timeMaxk, i = Math.Max(timeAk, i, timeBk, i);for (int i = tempSum + 1; i aSum; i+) timeAk, i = tempSum; timeBk, i = 0;int flag = 0;for (int i = 0;

12、i 0 & timeMaxk, i 0 & flag 0; i-)if (tempRlti = a)flag -= ai;tempRlti - 1 = whoi - 1, flag;if (tempRlti = b)tempRlti - 1 = whoi - 1, flag;resultk = new String(tempRlt);static void Main(string args)const int N = 6;int a = new intN 2, 5, 7, 10, 5, 2 ;int b = new intN 3, 8, 4, 11, 3, 4 ;int least = new

13、 intN; string result = new stringN; DlrwZydd(a, b, N, least, result); Console.WriteLine();for (int i = 0; i N; i+) + resulti +Console.WriteLine( 按要求完成前0项任务的机器顺序为 时间为： 1 ,i+1,leasti);实验三 贪心算法一、实验目的1进一步理解算法设计的基本步骤及各步的主要内容、基本要求2加深对贪婪法算法设计方法的理解与应用3掌握将算法转化为计算机上机程序的方法4培养学生应用所学知识解决实际问题的能力。二、实验内容1、设有n个顾客同时等

14、待一项服务。顾客i需要的服务时间为ti, lv=iv=n。应如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是每个顾客等待服务时间 的综合。2、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，之处应 在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产生一个最优解。三、实验要求（1）设计用贪婪法求解“最优服务次序问题”及“汽车加油问题”的算法；（2）上机实现所设计的算法；（3）分析所设计的算法的时间/空间复杂性。四、实验过程设计（算法设计过程）1、首先将每个顾客所需要的服务时间从小到大排序。然后申请2个数组：st 是服务数组， stj为第j个队列上

15、的某一个顾客的等待时间；su是求和数组，suj的值为第j个队列 上所有顾客的等待时间；2、设加油次数为k每个加油站间距离为ai； i=0， 1，2，3n1.始点到终点的距离小于N,则加油次数k=0；2始点到终点的距离大于N， 加油站间的距离相等，即ai=aj=L=N，则加油次数最少k=n； 加油站间的距离相等，即ai=aj=LN,贝怀可能到达终点； 加油站间的距离相等，即a i=aj=LN，则加油次数k=n/N（n%N=O）或 k=n/N+1（n%N！=0） ； 加油站间的距离不相等，即a i ! =aj，则加油次数k通过下面的算法求解。五、实验结果分析最优服务次序问题：input the n

16、um of the seruer：input the need seruice tine of each CListoneFkJ4he least auerage waiting t ime is：13 iess any key to continue20No . 6ItsNo.7H：.B时间复杂度为 O(nlogn)汽车加油问题：行，可数MlI-U站距1lal12345266加加站距sF卸 话 贸 5555;, 人入入间间间间2121阖在在 输点点点点点点点IM3 4 6? 请请盘站站站站站站站汽分WWW加站需油nN idr力占占占占 : =:匕壬一 立立立立12 3 4 5 6 7 g 总

17、m.fn mmn -h - - n - - n - 5 HVI.,MlAU1JLrr Trrr Trrr Trrr Ikk ick vu_l _f r r 力力力力 个个时间复杂度为 O(n)。六、实验体会七、附录：(源代码) 汽车加油问题： #include #include namespace ConsoleApplication1 class Program static void Main(string args) Console.Write(请输入汽车加满油后可行驶路程：”)； int n = Convert.ToInt32(Console.ReadLine();Console.Wr

18、ite请输入途经加油站总数：”)； int k = Convert.ToInt32(Console.ReadLine()； int distance = new intk + 1；/加油站间距 int note = new intk;记录加油站点 Console.WriteLineC请输入加油站间距！ ”)； for (int i = 0； i = 0) if (count = 0) Console.WriteLineC汽车不用加油就可到达终点！ ”)； elseConsole.WriteLineC汽车在旅途中需口0次油！ , count); Console.WriteLineC分别在以下加油

19、站加了油：”)； for (int i = 0; i note.Length; i+) if (notei != 0) /输出需加油站点Console.WriteLineC第+ notei + 个加油站！ ”)； elseConsole.WriteLineC汽车无法到达终点！ ”)； Console.ReadKey();class Problempublic int Greedy(int d, int note, int n)int i, j, s, add = 0, p = 0, k = d.Length；for (i = 0； i n)/不能到达目的地return -1；for (j =

20、0, s = 0； j n)/需要加油 add+； notep+ = j； s = dj；return add；实验四 回溯法一、实验目的1掌握能用回溯法求解的问题应满足的条件；2加深对回溯法算法设计方法的理解与应用；3锻炼学生对程序跟踪调试能力；4通过本次实验的练习培养学生应用所学知识解决实际问题的能力。二、实验内容1、设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij 是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不 超过c的最小重量机器设计。2、设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，

21、为每 一个人都分配 1 件不同的工作，并使总费用达到最小。三、实验要求（1）用回溯法算法设计方法求解最小重量机器设计问题和工作分配问题；（2）上机实现所设计的算法；（3）分析所设计的算法的时间/空间复杂性。四、实验过程设计（算法设计过程）1、a.部件有n个，供应商有m个，分别用wij和cij存储从供应商j处购得的部件i的 重量和相应价格， d 为总价格的上限。b. 用递归函数backtrack（i）来实现回溯法搜索排列树（形式参数i表示递归深度）。 若cpd,则为不可行解，剪去相应子树，返回到i-1层继续执行。 若cw=sum,则不是最优解，剪去相应子树，返回到i-1层继续执行。 若in，则算

22、法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行； 用for循环对部件i从m个不同的供应商购得的情况进行选择（1j=s，则不是最优解，剪去相应子树，返回到i-1层继续执行； 若i n，则算法搜索到一个叶结点，用s对最优解进行记录，返回到i-1层 继续执行； 采用for循环针对n个人对工作i进行分配（1WjWn）：1若vj=1，则第j个人已分配了工作，找第j+1个人进行分配；2若vj=0,则将工作i分配给第j个人（即vj=1 ），对工作i+1调用递归函数backtrack （i+1，total+cij）继续进行分配；3函数backtrack （i+1， total+cij，调

23、用结束后则返回vj=0，将工作i对第 j+1 个人进行分配；4 当 jn 时， for 循环结束； 当i=1时，若已测试完cij的所有可选值，外层调用就全部结束；c. 主函数调用一次backtrack （1，0）即可完成整个回溯搜索过程，最终得到的s即为 所求最小总费用。五、实验结果分析最小重量机器设计问题：程序中最大的循环出现在递归函数backtrack (i)中，而此函数遍历排列树的时间复杂度为 0(n!),故该算法的时间复杂度为O(n!)。工作分配问题：递归函数back track(i， tot al)遍历排列树的时间复杂度为0 (n！,主函数调用递归函 数 backtrack(1， 0

24、)，故该算法的时间复杂度为 O(n！)。六、实验体会七、附录：(源代码) 最小重量机器设计问题：#include#define N 1000 using namespace std;int n,m,d,cp=0,cw=0,sum=0;int cNN,wNN;void backtrack(int i)if(in)if(cwsum) sum = cw;return ;for(int j=1;j=m;j+) cw+=wij; cp+=cij; if(cwsum & cpnmd;for(int i=1;i=n;i+)for(int j=1;jcij;sum+=ci1;for(int k=1;k=n;k+)for(int j=1;jwkj;backtrack(1);coutsumendl; system(pause); return 0;