“递归算法”的教学设计.doc

上传人:创****公 文档编号:1596414 上传时间:2019-03-07 格式:DOC 页数:36 大小:356KB
下载 相关 举报
“递归算法”的教学设计.doc_第1页
第1页 / 共36页
“递归算法”的教学设计.doc_第2页
第2页 / 共36页
“递归算法”的教学设计.doc_第3页
第3页 / 共36页
“递归算法”的教学设计.doc_第4页
第4页 / 共36页
“递归算法”的教学设计.doc_第5页
第5页 / 共36页
点击查看更多>>
资源描述

1、全国青少年信息学奥林匹克联赛算法讲义算法基础篇 .1算法具有五个特征: .2信息学奥赛中的基本算法(枚举法) .4采用枚举算法解题的基本思路: .4枚举算法应用 .4信息学奥赛中的基本算法(回溯法) .7回溯基本思想 .7信息学奥赛中的基本算法(递归算法) .10递归算法的定义: .10递归算法应用 .10算法在信息学奥赛中的应用 (递推法) .13递推法应用 .14算法在信息学奥赛中的应用 (分治法) .17分治法应用 .18信息学奥赛中的基本算法(贪心法) .20贪心法应用 .21算法在信息学奥赛中的应用(搜索法一) .24搜索算法应用 .24算法在信息学奥赛中的应用(搜索法二) .28广

2、度优先算法应用 .29算法在信息学奥赛中的应用(动态规划法) .32动态规划算法应用 .33算法基础篇学习过程序设计的人对算法这个词并不陌生,从广义上讲,算法是指为解决一个问题而采用的方法和步骤;从程序计设的角度上讲,算法是指利用程序设计语言的各种语句,为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法,因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂,一个好的程序必须有一个好的算法,一个没有有效算法的程序就像一个没有灵魂的躯体。算法具有五个特征:1、有穷性: 一个算法应包括有限的运算步骤,执行了有穷的操作后将终止运算,不能是个死循环; 2、

3、确切性: 算法的每一步骤必须有确切的定义,读者理解时不会产生二义性。并且,在任何条件下,算法只有唯一的一条执行路径,对于相同的输入只能得出相同的输出。如在算法中不允许有“计算 8/0”或“将 7 或 8 与 x 相加”之类的运算,因为前者的计算结果是什么不清楚,而后者对于两种可能的运算应做哪一种也不知道。 3、输入:一个算法有 0 个或多个输入,以描述运算对象的初始情况,所谓0 个输入是指算法本身定义了初始条件。如在 5 个数中找出最小的数,则有 5 个输入。4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果,这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在 5 个

4、数中找出最小的数,它的出输出为最小的数。如果一个程序没有输出,这个程序就毫无意义了; 5、可行性: 算法中每一步运算应该是可行的。算法原则上能够精确地运行,而且人能用笔和纸做有限次运算后即可完成。 如何来评价一个算法的好坏呢?主要是从两个方面:一是看算法运行所占用的时间;我们用时间复杂度来衡量,例如:在以下 3个程序中,(1)x:=x+1(2)for i:=1 to n dox:=x+1(3)for i:=1 to n do for j:=1 to n do x:=x+1含基本操作“x 增 1”的语句 x:=x+1 的出现的次数分别为 1,n 和 n2则这三个程序段的时间复杂度分别为 O(1)

5、 ,O(n) ,O(n 2) ,分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中,还有可能出现的有:对数阶 O(log n),指数阶 O(2n)等。在 n 很大时,不同数量级的时间复杂度有:O(1)0 then inc(t) else break;如果不在 st 中,则退出循环if t=9 then writeln(x, ,x*2, ,x*3);end;end.在枚举法解题中,判定条件的确定也是很重要的,如果约束条件不对或者不全面,就穷举不出正确的结果, 我们再看看下面的例子。例 一元三次方程求解(noip2001tg)问题描述 有形如:ax 3+bx2+cx+d=0 这样的一个一元三

6、次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根 (根的范围在-100 至 100 之间) ,且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后 2 位。提示:记方程 f(x)=0,若存在 2 个数 x1 和 x2,且 x1a2ar;(2) 其中第 i 位数(1r-i;我们按以上原则先确定第一个数,再逐位生成所有的 r 个数,如果当前数符合要求,则添加下一个数;否则返回到上一个数,改变上一个数的值再判断是否符合要求,如果符合要求,则继续添加下一个数,否则返回到上一个数,改变上一个数的值按此规则不断循环

7、搜索,直到找出 r 个数的组合,这种求解方法就是回溯法。如果按以上方法生成了第 i 位数 ai,下一步的的处理为:(1) 若 air-i 且 i=r,则输出这 r 个数并改变 ai 的值:a i=ai-1;(2) 若 air-i 且 ir,则继续生成下一位 ai+1=ai-1;(3) 若 air-1 则重复:若 air-i,若 i=r,则输出解,并且 ai:=ai-1;若 ink;writeln(t);end.回溯法是通过尝试和纠正错误来寻找答案,是一种通用解题法,在 NOIP 中有许多涉及搜索问题的题目都可以用回溯法来求解。信息学奥赛中的基本算法(递归算法)递归算法的定义:如果一个对象的描述中包含它本身,我们就称这个对象是递归的,这种用递归来描述的算法称为递归算法。我们先来看看大家熟知的一个的故事:从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说上面的故事本身是递归的,用递归算法描述:procedure bonze-tell-story;beginif 讲话被打断 then 故事结束else begin从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事;bonze-tell-story;endend;从上面的递归事例不难看出,递归算法存在的两个必要条件:(1) 必须有递归的终止条件;

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。