查找类问题.ppt

查找类问题 2012 12 18 数组 之 执教 顾井莲 以10个同学为例 55 78 84 60 72 96 85 88 57 92 思考 查找本次月考C语言成绩中有无分值为80分的同学 1分析问题 2设计算法 3编写代码 4执行调试 以10个同学为例 55 78 84 60 72 96 85 88 57 92 查找本次月考C语言成绩中有无分值为80分的同学 includevoidmain inti a 10 55 78 84 60 72 96 85 88 57 92 查找原理 假设为升序排列 没有相同记录 首先找到被查找的中间同学的成绩 这时会出现以下三种情况之一1该成绩小于目标分 此时应在后半部分同学中继续查找 2该成绩大于目标分 此时应在前半部分记录中继续查找 3该成绩等于目标分 那么就已找到了查找目标 查找结束 这种方法叫对半查找 折半查找或二分法查找 1顺序查找法 2对半查找法 要求 根据对半查找的原理 讨论对该算法的理解 并由各大组推选十名代表上台展示算法 该组剩下的同学来解说 每一轮查找由一名同学解说 几个同学解说就表示该查找经过了几轮比较 i a 10 low high mid a 10 low 0 high 9 mid mid low high 2 If 80 a mid elseIf 80 a mid else high mid 1 low mid 1 printf find n break printf nofind n includevoidmain inti a 10 55 57 60 72 78 84 85 88 92 96 intlow mid high low 0 high 9 while low80 high mid 1 elseif a mid high printf nofind n 1文献综述 1顺序查找 2对半查找 分析比较 改错 已知两集合A 94 18 52 44 42 6 67 12 B 12 6 94 编程判断集合B是否为A的子集 若B中的数在A中均存在 则称B是A的子集 includeVoidmain inti j temp inta 8 94 18 52 44 42 6 67 12 intb 3 12 8 6 if fine a b printf B是A的子集 elseprintf B不是A的子集 sort ints intn inti j k t for i 0 i n 1 i k i for j i 1 j n 1 j FOUND if s k s j k j if k i t s i s i s k s k t intfine inta intb inti q h m f 1 FOUND sort b 3 for i 0 ia m q m 1 elseh m 1 m q h 2 if b i a m f 0 break returnf 1顺序查找 2对半查找 选用合适的查找方法编写程序 查找本次月考中C语言成绩在85分及以上的人数 并上机调试 书面完成调试报告和实验结果 课后作业 ThankYou pleasegivesomequestions Anymoreinformation includevoidmain inti a 10 55 78 84 60 72 96 85 88 57 92 for i 0 i9 printf nofind n includevoidmain inti a 10 55 57 60 72 78 84 85 88 92 96 low 0 high 9 while