利用随机化算法对顺序表进行搜索

《利用随机化算法对顺序表进行搜索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、随机化算法实验要求1.理解计算机随机数的产生；1.理解随机化算法原理及一般应用；2.编程实现典型随机算法，理解算法思想，并对算法进行验证分析。实验内容利用随机化算法对顺序表进行搜索：l随机抽取有序表元素；l从最接近待查元素开始搜索。实验结果定义一个60000个元素的数组，元素值依次为2,4,6…120000。随机抽取300次，根据抽取的元素就近查找某数是否存在。输入元素为待查找整数，结果为元素下标位置（从0开始）。--------------------------------------------示

2、例输入：1999示例输出：-1--------------------------------------------示例输入：6示例输出：2源代码：：//科目：算法实验//题目：利用随机化算法对顺序表进行搜索：//随机抽取有序表元素；//从最接近待查元素开始搜索。//作者：武叶//语言：C语言//创作时间：2012年5月6日#include#include#defineM60000longm[60000];longn[60000];intsuiji[300];ints

3、earch(intresult){intaddress,address1,address2,min,j,k,temp;intlocate=-1;intb=245;intc=23;n[0]=m[0];suiji[0]=0;for(k=0;k<299;k++){suiji[k+1]=(suiji[k]*b+c)%M;}//对suiji[300]数组的随机值进行冒泡排序for(k=0;k<=299;k++){for(j=0;j<300-k;j++)if(suiji[j]>suiji[j+1]){temp=su

4、iji[j];suiji[j]=suiji[j+1];suiji[j+1]=temp;}}//根据suiji数组的值将相应的x数组中的值存在y数组中for(k=0;k<300;k++){j=suiji[k];n[j]=m[j];}min=(int)fabs(n[0]-result);//求result与抽取数组中的元素之差的绝对值address=0;for(k=0;k

5、bs(n[k]-result);address=k;}}//判断元素在x数组中的位置if(min==0){returnaddress;}else{address1=address-min/2;//元素可能出现下标位置范围address2=address+min/2;for(k=address1;k<=address2;k++){if(result==m[k])//查找下标{locate=k;break;}}returnlocate;}}intmain(){inti,search_num,location

6、;//location为查找元素的位置search_num为要查找的数for(i=0;i<60000;i++)m[i]=(i+1)*2;//定义m[i]为2,4,6…120000。scanf("%d",&search_num);if(search_num<0

7、

8、search_num>120000

9、

10、search_num%2==1){printf("-1");}else{location=search(search_num);printf("%d",location);}return0;}答销网真

11、情提供：：：：www.daxiao51.com文章出处：：：：：：http://www.daxiao51.com/forum.php?mod=viewthread&tid=1545&extra=page%3D1