信息学奥赛辅导czh

1、信息学奥赛辅导信息学奥赛辅导 湖中 吴 9.1 查找查找 查找也称检索，就是在一组给定的数据中查找满足某种条件的数据，查查找也称检索，就是在一组给定的数据中查找满足某种条件的数据，查 找通常需要根据某一关键字进行。例如，在找通常需要根据某一关键字进行。例如，在c盘中查找文件名为盘中查找文件名为“cgf.txt” 的文件。根据算法思想的不同，查找主要分为顺序查找和二分查找。的文件。根据算法思想的不同，查找主要分为顺序查找和二分查找。 1.顺序查找顺序查找 顺序查找是最基本的查找方法，它的基本思想是：从表的一端开始，顺顺序查找是最基本的查找方法，它的基本思想是：从表的一端开始，顺 序扫描线性表，一

2、一将扫描到的结点关键字和给定值序扫描线性表，一一将扫描到的结点关键字和给定值K比较。若当前扫比较。若当前扫 描到的结点关键字与描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关相等，则查找成功；若扫描结束后，仍未找到关 键字等于键字等于K的结点，则查找失败。的结点，则查找失败。 Ai x 23 25 3 5 138 200 110 89 17 20 【例【例9-1】 输入一个整数输入一个整数X，在已存在的一个整数数组中顺序查找在已存在的一个整数数组中顺序查找X是是 否存在，若找到，输出否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不在整数数组中所对应的位置，否则输出找不

3、 到的信息。（假设数组中没有重复数据）到的信息。（假设数组中没有重复数据） 算法分析：算法分析： （1 1） 先输入待查的值先输入待查的值K （2 2） 令令i=1，让让k与与ai比较比较 （3 3） 若若aik,则则i:=i+1，如果如果in，则退出循环，输出找不到的信息；若则退出循环，输出找不到的信息；若ai=k，则退出循环，则退出循环， 输出找到的信息。输出找到的信息。 参考程序参考程序: Program ex9_1; Const n=10 var x,k,i:integer; a:array1.n of integer; found:Boolean; begin for i:=1 to

4、 n do read(ai);readln; readln(x) i:=1;found:=false; while (ik,则由表的有序性可知则由表的有序性可知Rmid.n.keys均大于均大于K,因此若因此若 表中存在关键字等于表中存在关键字等于K的结点的结点,则该结点必定是在位置则该结点必定是在位置mid左边的子表左边的子表 R1.mid-1k中中,故新的查找区间是左边的子表故新的查找区间是左边的子表R1.mid-1。 2类似地，若类似地，若Rmid.keyK，则要查找的则要查找的K必在必在mid的右子表的右子表rmid+1.n 中，即新的查找区间中，即新的查找区间R1.n开始，每间经过一

5、次与当前查找区间的中开始，每间经过一次与当前查找区间的中 点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当 前的查找区间就缩小一半。这一过程重复直至找到关键字为前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，的结点， 或者直至当前的查找区间为空（即查找失败）时为止。或者直至当前的查找区间为空（即查找失败）时为止。 25 35 42 56 68 72 79 84 88 90 98 103 112 120 125 130 Ai f h mid 25 35 42 56 68 72 79 84 88 90 98 10

6、3 112 120 125 130 25 35 42 56 68 72 79 84 88 90 98 103 112 120 125 130 25 35 42 56 68 72 79 84 88 90 98 103 112 120 125 130 X=95 f f f h h h mid mid mid 【例【例9-2】输入一整数】输入一整数X，在已存的一个有序整数数组中二分查找在已存的一个有序整数数组中二分查找X是否是否 存在，若找到，输出存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的在整数数组中所对应的位置，否则输出找不到的 信息。（已知数组中没有重复数据）信息。（已知数组

7、中没有重复数据） 参考程序：参考程序： Program ex9_2 Const n=16 var m,f,h,x,i:integer; a:array1.n of integer; begin f:=1;h:=n; For i:=1 to n do read(ai); readln; Readln(x); Found: =false; While (f=h)and not (found) do Begin M:=trunc(f+h)/2); If x=am then found: =true Else if xam then h:=m-1 Else f:=m+1 End; If found t

8、hen writeln(x:6,at,m:6) Else writeln(not found!); End. 以点带面以点带面 二分查找二分查找 的递归出程序的递归出程序 const n=100; var a: array1.n of integer; x, i :integer; procedure search(x,top,bot:integer); var mid:integer; begin if ( )then begin mid:=(top+bot) div 2; if x=amid then writeln(yes) else if xamid then search( ) el

9、se search( ); end else writeln(no); end; begin for i:=1 to n do read(ai); readln(x); search(x,1,n); end. top=bot x,top,mid-1 x,mid+1,bot 二分查找二分查找 的递归出程序：的递归出程序： 分治法分治法 当我们处理大规模问题时，求解可能比较困难。对于这当我们处理大规模问题时，求解可能比较困难。对于这 类问题，我们往往类问题，我们往往先把它分解成若干个与原问题类型相同的先把它分解成若干个与原问题类型相同的 子问题求解，求出这几个子问题的解后，再找到合适的方法，子问题

10、求解，求出这几个子问题的解后，再找到合适的方法， 把它们组合成整个问题的解把它们组合成整个问题的解。如果处理子问题仍然有困难，。如果处理子问题仍然有困难， 则再次进行分割，直到可以直接求解为止。这种大化小的策则再次进行分割，直到可以直接求解为止。这种大化小的策 略称为分治策略。略称为分治策略。 二分查找、归并排序、快速排序二分查找、归并排序、快速排序都是应用分治策略的典都是应用分治策略的典 型例子。型例子。 用分治思想设计出的算法在每一层递归上都有三用分治思想设计出的算法在每一层递归上都有三 个步骤：个步骤： 、分割，将要解决的问题划分成若干个规模较、分割，将要解决的问题划分成若干个规模较 小

11、的同类问题；小的同类问题； 、求解，递归地解各个子问题，当子问题划分、求解，递归地解各个子问题，当子问题划分 得足够小时，则直接解之；得足够小时，则直接解之； 、合并，将子问题的解合并成原问题的解。、合并，将子问题的解合并成原问题的解。 由于分治策略是把问题分成较小的与原问题类型相同的子由于分治策略是把问题分成较小的与原问题类型相同的子 问题，对于问题的处理过程与原问题的处理过程是相同的，所问题，对于问题的处理过程与原问题的处理过程是相同的，所 以分治法处理问题过程，可以自然地写成一个以分治法处理问题过程，可以自然地写成一个递归递归的处理过程。的处理过程。 例例1、二分查找、二分查找 二分查找二分查找的基本思想的基本思想: 、原来的数据序列是有序的。、原来的数据序列是有序的。 、先检查要找的数与中间位置的元素值是否相等。若相、先检查要找的数与中间位置的元素值是否相等。若相 等，则查找成功等，则查找成功;若不等，如果查找数