1、非数值计算Non-numeric Calculations朔州市实验中学校朔州市实验中学校 李娜目标目标运用合适的算法形成解决问题的方案。GOALSGOALS体验递归算法，并结合具体问题开展编程实践。了解算法设计中的分治思想，并运用二分查找解决实际问题。计算的一定是数吗？导入点击添加标题计算一定是数吗？计算一定是数吗？除了数还有什么？除了数还有什么？这些属于数值计算吗？这些属于数值计算吗？计算一定是数吗？计算一定是数吗？0101除了数还有什么？除了数还有什么？02020303这些属于数值计算吗？这些属于数值计算吗？导入导入在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领域。计算
2、的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话，那么非数值计算更多探讨 算法”问题。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归分治、递归、解析等。分治算法：重要的二分法分治策略点击添加标题 小问题小问题小问题小问题小问题小问题难以解决的较大问题难以解决的较大问题小问题小问题小问题小问题分治策略分治策略 分治的设计思想，是将个难以直接解决的大问题，分割成些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找二分查找实际上一就是分治策略的种典型运
3、用。点击添加标题二分查找二分查找二 分二 分直 接直 接点击添加标题二分查找二分查找import randomx=random.randint(1,1000)while 0 x1000:y=int(input(请输入这个数：)if xy:print(小了)else:print(就是,x)breakrandom包可以称为随机包，它有如下函数：random.randint(1,10)#产生 1 到 10 的一个整数型随机数 random.random()#产生 0 到 1 之间的随机浮点数random.uniform(1.1,5.4)#产生 1.1 到 5.4 之间的随机浮点数，区间可以不是整数r
4、andom.choice(tomorrow)#从序列中随机选取一个元素random.randrange(1,100,2)#生成从1到100的间隔为2的随机整数小游戏：如何找出1-1000之间的某个数？点击添加标题 二分查找二分查找 二分查找又叫折半查找，该方法主要将数列有序排列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后可以将查找区域缩小一半。第一次分割第二次分割第三次分割点击添加标题二分查找二分查找x=int(input(请输入要查找的整数:)step=0low=1
5、high=1000while(lowx:high=mid-1 elif midx:low=mid+1 else:breakprint(查找次数为：,step)input(运行完毕，请按回车键退出.)思考：如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？点击添加标题二分查找二分查找x=int(input(请输入要查找的数据：)step=0#记录查找次数flag1=1#目标区域左边界flag2=1000#目标区域右边界if flag1=x=flag2:while(flag1x:flag2=mid-1 elif mid,t)#将一个盘子从s移动到t else:hanno(n
6、-1,s,t,m)#将前n-1个盘子从s移动到m上 print(s,-,t)#将最底下的最后一个盘子从s移动到t上 hanno(n-1,m,s,t)#将m上的n-1个盘子移动到t上#主程序n=int(input(请输入汉诺塔的层数：)hanno(n,A,B,C)input(运行完毕，请按回车键退出.)代码实现点击添加标题l 2个金片，移动几次汉诺塔游戏汉诺塔游戏l 4个金片，移动几次l 5个金片，移动几次l 3个金片，移动几次l 3次l 15次l 31次l 7次点击添加标题 一种思维模式，抽象表达的手段，求解问题的方法。直接或间接地调用自身的方法，可以简单类比为具有自相似性重复的事物。基本思想
7、：把规模较大的问题层层转化把规模较大的问题层层转化为规模较小的同类问题求解为规模较小的同类问题求解递归算法递归算法举例：斐波那契数列“1，1，2，3，5，8”可定义为点击添加标题数学领域的递归算法数学领域的递归算法用函数自身来定义该函数“分分”“”“治治”合合”(1)分：将原问题分解成K个子问题。(2)治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。(3)合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解递归的重要组成递归的重要组成递推关系、边界条件（保证递归能在有限次计算后
8、得出结果，而不会产生无限循环地情况）递归算法递归算法分治（二分法）+递归课堂测试总结总结CONTRACTEDPURE AND FRESHWealth is like water.If its a Wealth is like water.If its a glass of water,you can enjoy glass of water,you can enjoy it alone.If its a bucket of it alone.If its a bucket of water,you can leave it at home;water,you can leave it at home;But if its a river,you have But if its a river,you have to learn to share it.to learn to share it.数值计算数值计算 ：迭代法：迭代法非数值计算：分治算法（二分法）、非数值计算：分治算法（二分法）、递归算法递归算法感谢感谢观看CONTRACTEDPURE AND FRESH朔州市实验中学校朔州市实验中学校李娜
