安徽工业大学算法设计与分析课程设计

《安徽工业大学算法设计与分析课程设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》课程设计报告学号119074180姓名都竞班级软件112指导教师王喜凤妥徽工业丈修针篇机曇院2014卑5月1、分别用递归法和动态规划法求Fibonacci数，并填写下表:表1:F(N)的值F(N)N=2328657N=333524578N=43433494437N=484807526976实验代码如下：#include#includelongf(longn){if(n<=l)return1;elsereturnf(n-1)+f(n-2);}intmain(){longn;pr

2、intf(Mplcascinputn:H);scanf(M%dr&n);primfC%ldrAF(n・l));}表2：不同方法所用时间(ns)递归法动态规划其他N=23时,所用时间547628042768365139673N=33时，所用时间2683748953789654276372N=43时,所用时间267392739854783926573829N=48时,所用时间4876327483273983876289871代码如下：#includc#include#include

3、e.h>#includelongf(intn){longprevI.prev2,cur;inti;if(n<=1)returnn:prev2=0;prevl=1;for(i=2;i<=n;i++)cur=prevl+prev2;prev2=prev1;prcvI=cur;}returncur;}intinain(){intn;longstartfinish,cur;printf(°pleaseinputn:H);scanf(H%ldM,&n);slart=clock();printf(M%ld*cu

4、r);finish=clock();printf(M%dmsf(finish-start));getcharO;2、当问题规模Nn100时，插入排序、快速排序和合并排序各需多少时间？写清机器配置,列出五种规模下各自需要的时间。按照下列表格提交：插入排序所需时间(ns)快速排序所需时间(ns)合并排序所需时间(ns)N=200436579263786994678N=20003421077503865425773829N=20000207888675142893071200876549N=200000251876390762638

5、965917247890834N=200000025873920928093827483插入排序:packageExamp]e_l;importjava.util.Scanner;publicclassExample1{privatestaticint[]Creat_Array(intn{intarray[]=newint[num]:for(inti二0;iCnum;i++){intrandomumber=(int)(Math・畑加沏0*num)+l;array[i]=randomNumber;returnarray;priv

6、atestaticvoidStraightlnserlSort(intarray[])intx,i,j;for(i=l;i=0;j—){if(xarray[j+l]=array[j]:}array[j+l]=x;}}privatestaticvoidPrint_Array(intarray[],intnum){for(inti=0;i

7、l)%10=0){System.out.println(z，/");}}}publicstaticvoidmain(String]]args){System,out.printing输入数据规模：")；Scannerreader二newScanner(System・巾)；intnum=reader・ncxtTntO;reader・close();intarray(num);longstartTime=System.nanoTimeO;StraightInsertSort^Y^y);longcndTimc二System・nanoT

8、imcOPrint_Array(.array,num);System,out.printlnC程序运行时间：(endTime-startTime)+//ns，z);}}快速排序：packageTry;importjava・uti1・Scanner;public