- 1、本文档共21页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
递推策略—李白沽酒
复习巩固
什么是算法
详解鸡兔同笼
详解隔沟算羊与枚举算法
使用计算机解决问题的步骤
算法的三种表示方法
自然语言、流程图、程序设计语言
算法的三种基本结构
顺序结构、选择结构、循环结构
课程大纲与授课思路
详解李白沽酒
什么是递推策略
编程解题:老王卖瓜
详解水手分椰子
什么是模拟策略
验证角谷猜想
李白沽酒
李白沽酒探亲朋,路途迢迢有四程,
行至一程多一倍,却被书童喝六升,
行到亲朋家里面,半点全无在酒瓶,
借问高朋能算士,几何原酒要分明
李白沽酒
李白买了酒去看望朋友,
路途很遥远分四段才能走到,
每走一段路程,就在路边酒馆中
按酒瓶中的酒量向酒瓶中添加一倍的酒,
每次添加会被随从的书童偷偷喝掉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)
编程课堂
模拟策略
模拟策略:模拟现实世界中事物的变化过程,从而完成相应任务的方法
水手分椰子用到了模拟策略和枚举策略
牛刀小试
文档评论(0)