4.3 非数值计算　课件-2022—2023学年高中信息技术教科版（2019）必修1

e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276 4.3 非数值计算 四、计算与问题解决 王娟 海南华海中学 高二4班 1 e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276 活动1：猜定价“赢”棉衣 寒冬将至，某公司正在推出一款棉衣，为迎接双12购物节，成功打入市场，现举行“猜定价，‘赢’棉衣”的活动。价格范围在1—400元之间。看看哪位同学能以最快的速度猜出棉衣的实际定价。 2 e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276 二分查找/折半查找 p112 二分思想：将数列有序排列，采用跳跃的方式查找数据。 左边界 flag1 右边界 flag2 目标数x 中间数 mid ！！！若中间数mid比目标数x大，则区间变为左半区间，右边界更新 左边界 flag1 右边界 flag2 目标数x 中间数 mid ！！！若中间数mid比目标数x小，则区间变为右半区间，左边界更新 在有n个元素的有序序列中，利用二分查找大约需要log2n次。 n = 1000 需要10次 方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。 找一半 按照顺序找一半， 一比较，舍一半。 继续找一半， 一半又一半， 快速找答案！ 3 e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276 分治策略： 其设计思想为，将一个难以直接解决的大问题，分割成较小的同类问题，各个击破，最终达到解决问题的目的。 A B C D E F G H I 需要解决的问题 第一次分割 第二次分割 第三次分割 二分查找 4 e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D