幻灯片1-VISIONatOCEANUniversityofChina.pptVIP

点击添加文本 点击添加文本 点击添加文本 点击添加文本 Fibonacci查找 实际上，减治策略本身并不要求向量切分点mi必须居中，关于上述改进思路，不妨按黄金比例来确定mi，为简化起见，不妨设向量长度n=fib(k)-1 于是如图所示，fibSearch(e,0,n)查找可以mi=fib(k-1)-1作为前、后子向量的切分点。如此，前、后子向量的长度将分别是： fib(k-1)-1、 fib(k-2)-1 = ( fib(k)-1) – ( fib(k-1)-1) – 1 于是，无论朝哪个方向深入，新向量的长度从形式上都依然是某个Fibonacci数减一，故这一手法可以反复套用，直至因在S[mi]处命中或向量长度收缩至零而终止。这种查找算法，亦称作Fibonacci查找 点击添加文本 点击添加文本 点击添加文本 点击添加文本 Fibonacci查找——实现 点击添加文本 点击添加文本 点击添加文本 点击添加文本 插值查找 ——原理与算法： 假设：已知有序向量中各元素随机分布的规律，比如，独立且均匀的随机分布 于是，[lo, hi) 内各元素应大致按照线性趋势增长 因此，通过猜测轴点mi，可以极大地提高收敛速度 以英文词典为例，Binary大致位于2/26处 Search大致位于19/26处 点击添加文本 点击添加文本 点击添加文本 点击添加文本 插值查找 ——实例 e=50 5. 10. 12. 14. 26. 31. 38. 39. 42. 46. 49. 51. 54. 59. 72. 79. 82. 86. 92 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 lo=0, hi=18 插值：mi=0+(18-0)*(50-5)/(92-5) ≈ 9.3 取 ：mi=9 比较：A[9]=46e lo=10, hi=18 插值：mi=10+(18-10)*(50-49)/(92-49) ≈ 10.2 取 ：mi=10 比较：A[10]=49e lo=11, hi=18 插值：mi=11+(18-11)*(50-51)/(92-51) ≈ 10.8 取 ： mi=11lo 查找完成( NOT_FOUND ) 点击添加文本 点击添加文本 点击添加文本 点击添加文本 评价 此种方法优势不明显，除非查找空间宽度极大，或者比较操作成本极高 比如，n=2^(2^5)=2^32=4G时 易受小扰动的干扰和“蒙骗” 需引入乘法除法运算 实际可行的方法： 首先通过插值查找，将范围缩小到一定的尺度，然后再进行二分查找 点击添加文本 点击添加文本 点击添加文本 点击添加文本 栈应用 点击添加文本 点击添加文本 点击添加文本 点击添加文本 进制转换 描述：给出一个任意10进制非负整数，将其转换为λ进制表示形式 例： (89)10~( 1001101 )2 可用短除法计算结果 89 44 22 11 5 2 1 0 1 0 0 1 1 0 1 余数 可观察得出：输入过程是自上而下，而输出过程是自下而上 后进先出 因此，有必要引入栈，来实现算法 点击添加文本 点击添加文本 点击添加文本 点击添加文本 进制转换 ——实现 点击添加文本 点击添加文本 点击添加文本 点击添加文本 括号匹配 ——任务 括号匹配是语法检查中的必须环节。 其任务是，对任意程序块，判断其中的括号是否在嵌套的意义下完全匹配。比如在以下两个表达式中，前者匹配，后者不匹配。 ( a [ i – 1 ] [ j + 1 ] ) + a [ i + 1 ] [ j – 1 ] ) * 2 //失配 ( a [ i – 1 ] [ j + 1 ] + a [ i + 1 ] [ j – 1 ] ) * 2 //匹配 点击添加文本 点击添加文本 点击添加文本 点击添加文本 括号匹配 ——思路 思路：括号成对出现，那么消去一对紧邻的左右括号，不影响对全局的判断。则可用栈记录已扫描的部分，并反复迭代。 凡遇（，则进栈，遇），则出栈。 点击添加文本 点击添加