实验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只。要用100块钱刚好买100只鸡，问有多少种买法，每种买法

2、中公鸡、母鸡、小鸡的数量各为多少？设计一个实验方案，验证求解此问题的算法的正确性，比较并分析各算法的优劣。c)设计实验方案。方案中应包括i.多种问题求解算法ii.算法执行时间获取方法iii.抗时间“噪声”方法iv.时间结果分析对比方法d)根据算法和实验方案设计实验程序e)设计求解此问题的多种算法，并将它们转换成相应程序。f)分析各算法（程序）的特点，比较它们的优劣。g)安装程序设计语言系统。h)输入各个程序，验证它们的正确性。i)设计并运行能统计各程序执行时间并能抗“噪声”的程序，统计各算法的时间开销，并与之前所做的理论分析比较，看是否一致。实验环境硬件：Intel(R)Pentiu

3、m(R)CPURAM:4G软件：Myeclipse2013实验前准备41、算法设计：见实验步骤22、程序设计：见实验步骤3实验步骤1、利用spark语言写出初步的算法，再用java作为程序实现语言，实验利用的IDE为myelcipse2013，若直接在机器上编译运行需要安装JDK2、spark程序如下：PROGRAM百钱买百鸡（）IntegerM=100Integerx,y,z,n,kIntegert1,t2t1ßgettime()Forkß1toMdo//控制重复次数//nß0Forxß0to100doForyß0to100doForzß0to100doIf(100-5*x-3*y

4、)*3=zandx+y+z=100Thennßn+1print(n,x,y,z)endifrepeatrepeatrepeatrepeatt2ßgettime()print((t2-t1)/M)//取计算平均值，消除噪声//END.3、在Java中用System.currentTimeMillis()获取时间，为抗时间“噪声”，增加一个数组a[][10],将每次结果加到数组中在，降低输出对计算时间的干扰4、为比较精确计算出每个算法的时间，将每个算法计算100000遍，算出它们的平均值5、保证每种核心算法外部变量环境和操作方法一致（如在时间的计算方法上，结果的存储，计算的重复次数上一致

5、），只改变核心算法，以使几种算法在最终时间效率的比较上比较可靠6、根据spark语言写出对应的Java程序，并提出改进方案：为减少环境的其它因素对结果的影响，写出通用的主程序如下publicclassBaiji{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintM=100000;intn=0,k;int[][]a=newint[50][3];longt1,t2;t1=System.currentTimeMillis();//开始计时for(k=0;k

6、f1(a);//调用不同的方案，每次运行的时候只需要要将其替换成f1,f2,f3即可4}t2=System.currentTimeMillis();//停止计时System.out.println("计算一次平均耗时："+(float)(t2-t1)/M+"毫秒共有"+n+"种买法");//l输出结果for(inti=0;i

7、一：intx,y,z;intn=0;for(x=0;x<100;x++){for(y=0;y<100;y++){for(z=0;z<100;z++){if((x+y+z==100)&&((100-5*x-3*y)*3==z)){a[n][0]=x;a[n][1]=y;a[n][2]=z;//将结果输出保存到一个数组中n+=1;//结果加一}}}}returnn;}}方案二：由于公鸡5元一只，母鸡2元一只，而小小鸡最多买100只，可进一步缩小循环的次数，核心