实验1算法效率与时空复杂度检验

《实验1算法效率与时空复杂度检验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》实验报告实验1算法效率与时空复杂度检验姓名XXX学号XXX班级XXXXXX时间：XXXX-XX-XX地点：XXX同组人：无指导教师：XXX实验目的1、掌握一门程序设计语言2、掌握算法及程序设计的一般策略与方法3、掌握算法实验的一般步骤4、掌握算法分析与设计、算法比较的一般方法5、掌握算法实验中的时空复杂度的分析方法6、掌握算法实验方案的设计方法实验内容a）选择一个合适的程序设计语言（如C、C++、PASCAL等）b）根据问题设计算法。问题如下（百钱买百鸡问题）假设公鸡5元钱一只，母鸡3元钱一只，小鸡一元钱3

2、只。要用100块钱刚好买100只鸡，问有多少种买法，每种买法中公鸡、母鸡、小鸡的数量各为多少？设计一个实验方案，验证求解此问题的算法的正确性，比较并分析各算法的优劣。c）设计实验方案。方案中应包括i.多种问题求解算法ii•算法执行时间获取方法iii.抗时间“噪声”方法iii.时间结果分析对比方法d）根据算法和实验方案设计实验程序e）设计求解此问题的多种算法，并将它们转换成相应程序。f）分析各算法（程序）的特点，比较它们的优劣。g）安装程序设计语言系统。h）输入各个程序，验证它们的正确性。i）设计并运行能统计各程序执行时间并能

3、抗“噪声”的程序，统计各算法的时间开销，并与之前所做的理论分析比较，看是否一致。实验环境硬件：Intel（R）Pentium（R）CPURAM:4G软件：Myeclipse2013实验前准备1、算法设计：见实验步骤22、程序设计：见实验步骤3实验步骤1.利用spark语言写出初步的算法，再用java作为程序实现语言，实验利用的IDE为myelcipse2013,若直接在机器上编译运行需要安装JDK2、spark程序如下:PROGRAM百钱买百鸡（）IntegerM=100Integerx,y,z,n,kIntegert1,t

4、2Fork^1toMdo〃控制重复次数〃n《0Forx<-0to100doFory<-0to100doForz<-0to100doIf(100-5*x・3*y广3二zandx+y+z=100Thenn《n+1print(n,x,y,z)endifrepeatrepeatrepeatrepeatt2<-gettime()print((t2-t1)/M)〃取计算平均值，消除噪声//END.3、在Java中用System.currentTimeMillis()获取时间，为抗时间“噪声”，增加一个数组aO[10],将每次结果加到数组

5、中在，降低输出对计算时间的干扰4、为比较精确计算出每个算法的时间，将每个算法计算100000遍，算出它们的平均值5、保证每种核心算法外部变量环境和操作方法一致(如在时间的计算方法上,结果的存储，计算的重复次数上一致），只改变核心算法，以使几种算法在最终时间效率的比较上比较可靠6.根据spark语言写出对应的Java程序,并提出改进方案：为减少环境的其它因素对结果的影响，写出通用的主程序如下publicclassBaiji{publicstaticvoidmain(String[]args){//TODOAuto・genera

6、tedmethodstubintM=100000;intn=0，k;int[][]a=newint[50][3];longtl,t2;tl=System.currentTimeMiLLis();//开始计时for(k=0;k

7、种买法”)；//1输出结果for(inti=0;i

8、出保存到一个数组中1;//结果加一&&((100-5*x・3水y)*3kz)){returnn;方案二：由于公鸡5元一只,母鸡2元一只,而小小鸡最多买100staticintf2(int[][]a){//方案J只,可进一步缩小循环的次数，核心算法如下:intx,y,z;intn=0;for