少儿python四级6.递推策略-李白沽酒.pptx

递推策略—李白沽酒 复习巩固 什么是算法 详解鸡兔同笼 详解隔沟算羊与枚举算法 使用计算机解决问题的步骤 算法的三种表示方法 自然语言、流程图、程序设计语言 算法的三种基本结构 顺序结构、选择结构、循环结构 课程大纲与授课思路 详解李白沽酒 什么是递推策略 编程解题：老王卖瓜 详解水手分椰子 什么是模拟策略 验证角谷猜想 李白沽酒 李白沽酒探亲朋,路途迢迢有四程, 行至一程多一倍,却被书童喝六升, 行到亲朋家里面,半点全无在酒瓶, 借问高朋能算士,几何原酒要分明 李白沽酒 李白买了酒去看望朋友， 路途很遥远分四段才能走到， 每走一段路程，就在路边酒馆中 按酒瓶中的酒量向酒瓶中添加一倍的酒， 每次添加会被随从的书童偷偷喝掉6升 当李白来到亲朋家里的时候， 却发现酒瓶是空的， 请问瓶中原来是多少酒呢？ 算法分析 李白最后没有酒了，如果时光能倒流就好了，李白倒着走，我能很快知道原来有多少酒 算法分析 时光倒流： 原来书童喝酒（-6），现在变成+6 原来添酒一倍（*2），现在变成÷2 如此反复推理4次 第一次：( 0 + 6 ) ÷ 2 = 3 第二次：( 3 + 6 ) ÷ 2 = 4.5 第三次：( 4.5 + 6 ) ÷ 2 = 5.25 第四次：( 5.25 + 6 ) ÷ 2 = 5.625 每次数字都不一样，计算机也没办法重复执行，如果需要推理100次，1000次怎么办…… 真相只有一个 算法分析 观察一下 第一次：( 0 + 6 ) ÷ 2 = 3 第二次：( 3 + 6 ) ÷ 2 = 4.5 第三次：( 4.5 + 6 ) ÷ 2 = 5.25 第四次：( 5.25 + 6 ) ÷ 2 = 5.625 如果n表示酒量 第i次：n = ( n + 6 ) ÷ 2 让计算机对这个式子进行4次迭代（重复计算），就能算出答案了 算法分析 开动脑筋，用编程实现吧 编程实现 编程课堂 递推策略 递推策略：利用计算公式进行若干次重复运算求解答案分为两种形式： 顺推法：由起始条件  最终结果 逆推法：由最终结果  起始条件 牛刀小试 老王卖瓜，自卖自夸。第1个顾客买了全部的一半又半个,第2个顾客买了剩余的一半又半个……当第9个顾客来时，已经没有西瓜可卖了,原来老王有几个西瓜? n=(n+0.5)*2 i=8? n=(n+0.5)*2 水手分椰子 有三名水手和一只猴子被困在一个荒岛上，他们发现岛上有椰子。水手们一起劳累了一天，收集了许多椰子。 天黑了，他们决定先睡觉，等第二天再分配椰子。当天夜里，一个水手醒来，把椰子分为相等的三堆，发现多出了一个椰子，于是把这个椰子给了猴子。接着他藏好了自己那份椰子就去睡觉了。不久，另一个水手也醒来，做了与第一个水手同样的事，也把多出的一个椰子给了猴子。而当第三个水手醒来后，他也跟前两个水手一样分了椰子，也把多出的一个椰子给了猴子。 第二天早晨，三名水手起来时，他们把椰子平分为三堆，每人一份，并把多出的一个椰子也给了猴子。 问：这一堆椰子最少有多少个？？？ 算法分析 总共分了4次，每次都给猴子一个，说明椰子最少也有4个 思考一 采用枚举法，让椰子数从4开始递增，然后判断椰子数能否用4次分完 思考二 假设有n个椰子，分椰子的过程是怎样的？应该是什么公式？ 思考三 算法分析 椰子分完？ 水手分椰子 第4次分椰子时： （ n – 1 ）%3 == 0 前3次分，每次椰子数是： n=（ n – 1 ）/ 3 *2 -1代表给猴子一个椰子 %3表示第二天早上3个人分 ==0表示给猴子一个后，正好分完 -1代表给猴子一个椰子 /3表示第二天早上3个人分 *2表示自己那份拿走后，剩下的2份 编程实现 根据思路，自己把水手分椰子的代码写出来吧 老师知道你们现在肯定都是懵的，无从下手吧，那下面的内容可要认真听了哦 编程实现 定义一个函数，用来模拟分椰子，并将分完后的结果抛回去 def allocate(n): #定义函数 for i in range(3): #夜里的3次分椰子 n=(n-1)/3*2 #分完椰子后的数量 return (n-1)%3==0 #将最后一次能否分完结果抛回去 设置椰子初始值 n=4 循环判断函数抛回来的值是否为True,如果不是，将椰子数+1 while not allocate(n): n=n+1 打印最终的椰子数量 print(n) 编程课堂 模拟策略 模拟策略：模拟现实世界中事物的变化过程，从而完成相应任务的方法 水手分椰子用到了模拟策略和枚举策略 牛刀小试