信息学奥赛辅导czh.ppt

§9.1查找查找也称检索，就是在一组给定的数据中查找满足某种条件的数据，查找通常需要根据某一关键字进行。例如，在c盘中查找文件名为“cgf.txt”的文件。根据算法思想的不同，查找主要分为顺序查找和二分查找。1.顺序查找顺序查找是最基本的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，一一将扫描到的结点关键字和给定值K比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。A[i]【例9-1】输入一个整数X，在已存在的一个整数数组中顺序查找X是否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的信息。（假设数组中没有重复数据）参考程序:Programex9_1;Constn=10varx,k,i:integer;a:array[1..n]ofinteger;found:Boolean;beginfori:=1tondoread(a[i]);readln;readln(x)i:=1;found:=false;while(i<=n)andnot(found)doifa[i]=xthenfound:=trueelsei:=i+1;iffoundthenwriteln(‘kat’,i:6)elsewriteln(‘notfound’);end.参考程序:Programex9_1;Constn=8varx,k,i:integer;a:array[1..n]ofinteger;beginfori:=1tondoread(a[i]);readln;readln(x)i:=1;ForI:=1tondoifa[i]=xthenbeginwriteln(‘kat’,i:6);exit;endelseifI=nthenwriteln(‘notfound’);end.2.二分查找顺序查找要逐个比较表中元素，当表中元素非常多时,顺序查找的效率是很低的。二分查找是一种效率较高的查找方法，基于分治算法的思想，但二分查找要求线性表必须是有序的.我们不防设有序表是递增有序的。25【例9-2】输入一整数X，在已存的一个有序整数数组中二分查找X是否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的信息。（已知数组中没有重复数据）参考程序：Programex9_2Constn=16varm,f,h,x,i:integer;a:array[1..n]ofinteger;beginf:=1;h:=n;Fori:=1tondoread(a[i]);readln;Readln(x);Found:=false;While(f<=h)andnot(found)doBeginM:=trunc((f+h)/2);Ifx=a[m]thenfound:=trueElseifx<a[m]thenh:=m-1Elsef:=m+1End;Iffoundthenwriteln(x:6,’at’,m:6)Elsewriteln(‘notfound!’);End.以点带面constn=100;vara:array[1..n]ofinteger;x,i:integer;proceduresearch(x,top,bot:integer);varmid:integer;beginif()thenbeginmid:=(top+bot)div2;ifx=a[mid]thenwriteln('yes')elseifx<a[mid]thensearch()elsesearch();endelsewriteln('no');end;beginfori:=1tondoread(a[i]);readln(x);search(x,1,n);end.分治法用分治思想设计出的算法在每一层递归上都有三个步骤：１、分割，将要解决的问题划分成若干个规模较小的同类问题；２、求解，递归地解各个子问题，当子问题划分得足够小时，则直接解之；３、合并，将子问题的解合并成原问题的解。例1、二分查找