算法设计实验报告

算法设计与分析实验报告姓名:学号:班级:指导教师:实验一1, 分别用递归法和动态规划法求Fibonacci数，给出实2. 现代码，并填写下表：表1：F(N)的值F(N)N=2328657N=333524578N=43433494437N=484807526976表2：不同方法所用时间(ms)递归法动态规划其他N=23 时， 所用时间10N=33 时， 所用时间1370N=43 时， 所用时间168990N=48 时，所用时间2208130实现代码：递归算法：#include stdio.h#include conio.h#include time.hdouble fibonacci(int n)if(n=1lln=2)return 1;return fibonacci(n-1)+fibonacci(n-2);int main()int n;double p;clock_t start,end;scanf(%d,&n);start=clock();p=fibonacci(n);end=clock();printf(%f,p);printf(The different is %lf msn,(double)(end-start);system(pause);return 0;动态规划算法：#include stdio.h#include conio.h#include time.hlong fib(long n) long a,b,c;if(n=1) return n;a=1;b=0;for(int i=2;i=n;i+)c=a+b;b=a;a=c;return c;int main()long p;long q;clock_t start,end;scanf(%ld,&p);start=clock();q=fib(p);end=clock();printf(%ld,q);printf(The different is %lf msn,(float)(end-start);return 0;2.当问题规模N 100时，插入排序、快速排序和合并排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：插入排序所需时间（ms）快速排序所需时间（ms）合并排序所需时间（ms）N=20010N=200040N=200004053N=2000004116542N=2000000566实现代码：插入排序和#include #include #include #include #define MAXSIZE 2000000typedef structdouble rMAXSIZE+1;int length;SqList,*PSqList;PSqList Init_PSeqList() PSqList PL;PL=(PSqList)malloc(sizeof(SqList);if(PL)PL-length=0;return (PL);void StraightInsertSort(SqList *S) int ij;for(i=2;ilength;i+)S-r0=S-ri;j=i-1;while(S-r0rj)S-rj+1=S-rj;j;S-rj+1=S-r0;main() int i,b,n;time_t start, finish;double elapsed_time;struct _timeb timebuffer;int startm, finishm;PSqList h;h=Init_PSeqList();printf( number:);scanf(%d,&n);h-length=n;srand( (unsigned)time( NULL );for( i = 0; i ri=rand();printf( %.0fn,h-ri);_ftime( &timebuffer );startm= timebuffer.millitm;start= timebuffer.time;printf( Working.n);StraightInsertSort(h);_ftime( &timebuffer );finishm= timebuffer.millitm;finish= timebuffer.time;elapsed_time = difftime( finish, start );elapsed_time= 1000* elapsed_time+ finishm-startm;printf( Program takes %.0f millisecondsnn, elapsed_time);快速排序算法：#include #include #include #include #define MAXSIZE 2000000typedef structint rMAXSIZE+1;int length;SqList,*PSqList;PSqList Init_PSeqList() PSqList PL;PL=(PSqList)malloc(sizeof(SqList);if(PL)PL-length=0;return (PL);int QuickSort1(SqList *S,int low,int high) int p;S-r0=S-rlow;p=S-rlow;while(lowhigh)while(lowrhigh=p) high-;S-rlow=S-rhigh;while(lowrlowrhigh=S-rlow;S-rlow=S-r0;return low;void QuickSort(SqList *S,int low,int high) int pi;if(lowlength=n;srand( (unsigned)time( NULL );for( i = 0; i ri=rand();printf( %dn,h-ri);_ftime( &timebuffer );startm= timebuffer.millitm;start= timebuffer.time;printf( Working.n);QuickSort(h,0,n-1);_ftime( &timebuffer );finishm= timebuffermillitm;finish= timebuffer.time;elapsed_time = difftime( finish, start );elapsed_time= 1000* elapsed_time+ finishm-startm;printf( Program takes %.0f millisecondsnnn, elapsed_time);合并排序算法：#define N 10000#include stdio.h#include conio.h#include#include void merge(int c,int d,int l,int m,int r)( int i=l;int j=m+1;int k=l;int q;while(iv=m)&(jv=r)if(cim)for(q=j;q=r;q+)dk+=cq;elsefor(q=i;q=m;q+) dk+=cq;void merge_sort(int a, int b ,int left, int right) int c10000;if(left=right) bright=aright;else int i=(left+right)/2;merge_sort(a,c,left,i);merge_sort(a,c,i+1, right);merge(c, b, left, i, right);int main()int cN,dN;long i;double m_time;clock_t m_start,m_end;for(i=0;iN;i+)ci=rand();m_start=clock();merge_sort( c, d,0,N-1);m_end=clock();m_time=(double)(m_end-m_start);printf(%ld个随机数进行归并排序用时%.0f毫秒n,N, m_time); return 0;