算法设计及实验报告.pdfVIP

算法设计及实验报告

实验报告1递归算法

一、实验目的

掌握递归算法的基本思想；

掌握该算法的时间复杂度分析；

二、实验环境

电脑一台，TurboC运行环境

三、实验内容、步骤和结果分析

以下是四个递归算法的应用例子：用C语言实现

1.阶乘：

main()

{inti,k;{inti,k;

k=factorial(i);

}

intfactorial(intn)

{ints;

if(n==0)s=1;

elses=n*factorial(n-1);//执行n-1次

returns;

}

阶乘的递归式很快，是个线性时间，因此在最坏情况下时间复杂度为O(n)。

2.Fibonacci数列：

main()

{inti,m;{inti,m;

m=fb(i);

}

intfb(intn)

{ints;

if(n=1)return1;

elses=fb(n-1)+fb(n-2);

returns;

}

Fibonacci数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由

n

递归方程式可以知道他的时间复杂度T(n)是O(2)，该数列的规律就是不停的赋

值，使用的内存空间也随着函数调用栈的增长而增长。

3.二分查找（分治法）

#includestdio.h

#defineconst8

main()

{inta[]={0,1,2,3,4,5,6,7,8,9};

intn=sizeof(a);

ints;

s=BinSearch(a,const,n);

}

BinSearch(inta[],intx,intn)

{intleft,right,middle=0;

left=0;right=n-1;

whlie(left=right)

{middle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(xa[middle])left=middle+1;

elseright=middle-1;

}

return-1;

}

二分搜索算法利用了元素间的次序关系，采用分治策略，由上程序可知，每执行

一次while循环，数组大小减少一半，因此在最坏情况下，while循环被执行了

O（logn）次。而循环体内部只需运算O（1）的时间，因此该算法在最坏情况下

的时间复杂度为O（logn+1），即O（logn）。

4.合并排序（分治法）

MergeSort(intlow,inthigh,int*array)

{

intmiddle=(high+low)/2;//将数组划分为2分

if(lowhigh)

{

MergeSort(low,middle,array);//对前一部分进行递归处理

MergeSort(middle+1,high,array);//对后一部分进行递归处理

HeBing(low,middle,middle+1,high,array);//将排序后的,前后两部分,

进行合并

}

returntrue;

}

HeBing(intlow1,inthigh1,intlow2,inthigh2,int*array)

{

int*temp,

i=low1,

j=low2,

k=0;

temp=(int*)malloc((high2-low1+1)*sizeof(int));//temp用于临时存储

合并后的数组

while(i=high1j=high2)//对两个有序数组进行合并

{

if(array[i]array[j])

{

te