解析法课件(教育精品)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,常用算法及程序实现,第一节,解析法,一、解析法,定义：,通过分析问题各要素之间的关系，并经过一系列的推导得到解决问题的解析式，然后编程解决问题的方法,。,应用场合：,能根据已知条件，把问题求解归结到对方程、方程组、公式或函数求解的实际问题。,例：,用长度为,L,的铁丝制作一个面积为,S,的矩形框，,问：,矩形的长和宽各为多少？,二、娱乐一下,请点击教学系统主页上的,“,汉诺塔,”,链接进入游戏页面,;,游戏目标：,用,最少,的步数将,1,柱,上的盘片借助,2,柱,移到,3,柱,上；,游戏规则：,一次只能移动一片，不管在哪根柱上，,小片,必须,放在大片上面,；,我们的口号是：步数最少，时间最短！,三、提出问题,问：,将,n,个盘片从,1,柱借助,2,柱移至,3,柱至少需要多少步？,规则：,每次只允许移动一个盘片（为,1,步），无论在哪根柱上，小片必须放在大片上面。,1,2,3,四、分析问题,定义函数：,f(n),代表将,n,个盘片从,源柱,借助,中介柱,移至,目标柱,的过程，其函数值表示完成该移动过程至少需要多少步？,f(n),：,move(n,，源柱，中介柱，目标柱,),请思考：我们应从何处入手分析该问题？,分析,f(1),当,n=1,时，,f(1)=1,；,1,2,3,1,move(1,1,2,3);,分析,f(2),当,n=2,时，,f(2)=3,；,1,2,3,2,1,move(1,1,3,2);,move(1,1,2,3);,move(1,2,1,3);,move(1,1,2,3),分析,f(2),f(2)=,f(1),+1+,f(1),=2*f(1)+1=3,；,f(1)=,f(0),+1+,f(0),=2*f(0)+1=1,；,f(n)=,f(n-1),+1+,f(n-1),=2*f(n-1)+1,?,9,move(3,1,2,3),move(2,1,3,2),move(2,2,1,3),1,2,3,2,1,3,move(1,1,2,3),f(3)=,f(2),+,1,+,f(2),=2,*,f(2)+1=7,分析,f(3),当,n=3,时，,f(3)=7,；,10,move(3,1,2,3),move(2,1,3,2),move(1,1,2,3),move(1,1,3,2),move(1,3,1,2),move(1,1,2,3),move(2,2,1,3),move(1,2,3,1),move(1,2,1,3),move(1,1,2,3),1,2,3,2,1,3,分析,f(3),f(3)=f(2)+1+f(2)=(,f(1)+,1,+f(1),)+1+(,f(1)+,1,+f(1),),解析式一,f(n),=,f(n-1),+,1,+,f(n-1),=2,*,f(n-1)+1,，,(n=1),初始条件：,f(0)=0,f(n)=2*f(n-1)+1,f(0)=0,f(1)=2*0+1=1,f(2)=2*1+1=3,f(3)=2*3+1=7,f(4)=2*7+1=15,f(5)=2*15+1=31,f(6)=2*31+1=63,亲,O(_)O,：,你能看出这些函数值组成的数列有什么规律吗？,解析式二,f(n)=2n-1,，,n=0,五、算法实现,法,1,：利用循环和解析式,f(n)=2,*,f(n-1)+1,递推求解；,法,2,：直接将,n,代入解析式,f(n)=2n-1,求解；,六、练一练,登录高二同步教学系统，打开,“,VB,实验,E1,”,进行练习。,七、总结,用解析法编程解决问题的关键：,分析问题各要素之间,的,关系，灵活运用已有知识，构造解决问题所需的解析式。,谢谢大家,O(_)O,