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

算法设计与分析课程设计报告学 号119074180姓 名都竞班 级 软件112指导教师王喜凤安徽工业大学计算机学院2014年5月1、 分别用递归法和动态规划法求Fibonacci数，并填写下表：表1:F(N)的值F(N)N=2328657N=333524578N=43433494437N=484807526976实验代码如下：#include#include long f(long n)if(n=1) return 1;else return f(n-1)+f(n-2); int main()long n;printf(please input n:n);scanf(%d,&n); printf(%ldn,f(n-1); 表2：不同方法所用时间（ns）递归法动态规划其他N=23时，所用时间547628042768365139673N=33时，所用时间2683748953789654276372N=43时，所用时间267392739854783926573829N=48时，所用时间4876327483273983876289871代码如下：#include#include#include#include long f(int n)long prev1,prev2,cur;int i; if (n =1) return n; prev2 = 0; prev1 = 1; for (i = 2; i = n; i +) cur = prev1 + prev2; prev2 = prev1; prev1 = cur; return cur;int main() int n;long start,finish,cur;printf(please input n:n);scanf(%ld,&n);start=clock(); printf(%ldn,cur);finish=clock();printf(%d ms,(finish-start);getchar();2、 当问题规模时，插入排序、快速排序和合并排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：插入排序所需时间（ns）快速排序所需时间(ns)合并排序所需时间（ns）N=200436579263786994678N=20003421077503865425773829N=20000207888675142893071200876549N=200000251876390762638965917247890834N=200000025873920928093827483插入排序:package Example_1;import java.util.Scanner;public class Example_1private static int Creat_Array(int num)int array=new intnum;for(int i=0;inum;i+)int randomNumber=(int)(Math.random()*num)+1;arrayi=randomNumber;return array;private static void StraightInsertSort(int array)int x,i,j;for(i=1;i=0;j-)if(xarrayj)arrayj+1=arrayj;arrayj+1=x;private static void Print_Array(int array,int num)for(int i=0;inum;i+)System.out.printf(%d ,arrayi);if(i+1)%10=0)System.out.println();public static void main(String args) System.out.println(输入数据规模：);Scanner reader=new Scanner(System.in);int num=reader.nextInt();reader.close();int array=Creat_Array(num);long startTime=System.nanoTime(); StraightInsertSort(array);long endTime=System.nanoTime();Print_Array(array,num);System.out.println(程序运行时间： +(endTime-startTime)+ns);快速排序:package Try;import java.util.Scanner;public class Tryprivate static int Creat_Array(int num)int array=new intnum;for(int i=0;inum;i+)int randomNumber=(int)(Math.random()*num)+1;arrayi=randomNumber;return array;private static int Partition(int array,int p,int r)int i = p, j = r; int x=arrayi; while(ij) while(ij&xarrayj) j-; arrayi=arrayj; while(i=arrayi) i+; arrayj=arrayi; arrayi=x; return i;private static void QuickSort_Array(int array,int p,int r)if (pr) int q=Partition(array,p,r); QuickSort_Array (array,p,q-1); /对左半段排序 QuickSort_Array (array,q+1,r); /对右半段排序 private static void Print_Array(int array,int num)for(int i=0;inum;i+)System.out.printf(%d ,arrayi);if(i+1)%10=0)System.out.println();public static void main(String args)System.out.println(输入数据规模：);Scanner reader=new Scanner(System.in);int num=reader.nextInt();int array=Creat_Array(num);long startTime=System.nanoTime(); QuickSort_Array(array,0,num-1);long endTime=System.nanoTime();Print_Array(array,num);System.out.println(程序运行时间： +(endTime-startTime)+ns);reader.close();合并排序：package Example_2;import java.util.Scanner;public class Example_2 private static int Creat_Array(int num)int array=new intnum;for(int i=0;inum;i+)int randomNumber=(int)(Math.random()*num)+1;arrayi=randomNumber;return array;private static void Merge(int r,int rf,int u,int v,int t)int i,j,k;for(i=u,j=v+1,k=u;i=v&j=t;k+)if(rirj)rfk=ri;i+;elserfk=rj;j+;while(i=v)rfk+=ri+;while(j=t)rfk+=rj+;private static void MSort(int array,int array1,int n,int t)int m;int array2=new intarray.length;if(n=t)array1n=arrayn;elsem=(n+t)/2;MSort(array,array2,n,m);MSort(array,array2,m+1,t);Merge(array2,array1,n,m,t);private static void MergeSort(int array)MSort(array,array,0,array.length-1);private static void Print_Array(int array,int num)for(int i=0;inum;i+)System.out.printf(%d ,arrayi);if(i+1)%10=0)System.out.println();public static void main(String args) System.out.println(输入数据规模：);Scanner reader=new Scanner(System.in);int num=reader.nextIn