信息学奥赛算法基础篇

信息学奥赛算法基础篇

ID:45795948

大小:50.59 KB

页数:32页

时间:2019-11-17

信息学奥赛算法基础篇_第1页
信息学奥赛算法基础篇_第2页
信息学奥赛算法基础篇_第3页
信息学奥赛算法基础篇_第4页
信息学奥赛算法基础篇_第5页
资源描述:

《信息学奥赛算法基础篇》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

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

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

3、某种特定关系的量。如上述在5个数中找出最小的数,它的出输出为最小的数。如果一个程序没有输ili,这个程序就毫无意义了;5、可行,性:算法中每一步运算应该是可行的。算法原则上能够精确地运行,而且人能用笔和纸做有限次运算后即可完成。如何來评价一个算法的好坏呢?主要是从两个方而:一是看算法运行所占用的时间;我们用时间复杂度来衡量,例如:在以下3个程序中,(1)x:=x+l(2)fori:=ltondox:=x+l(3)fori:=Itondoforj:=ltondox:=x+l含基木操作“X增1”的语句x:=x+l的出现的次数

4、分别为1,n和『则这三个程序段的时间复杂度分别为O(1),O(n),O(n2),分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中,还有可能出现的有:对数阶O(k)gn),指数阶0(2。等。在n很大吋,不同数量级的时间复杂度有:O(l)

5、许多问题人们主要是研究其算法的时间复杂度,而很少讨论它的空间耗费。吋间复杂性和空I'可复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中,对程序的运行时间作出了严格的限制,如果运行时间超出了限定就会判错,因此在设计算法时首先要考虑的是时间因素,必要时町以以牺牲空间来换取时间,动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素,视题目的耍求而定,一般可以不作太多的考虑。我们通过一个简旳的数值计算问题,來比较两个不同算法的效率(在这里只比较时间复杂度)。例:求N!所产牛的数后血有多少个0(中间的0不计)。算法

6、一:从1乘到n,每乘一个数判断一次,若后甸有0则去掉后面的0,并记下0的个数。为了不超岀数的表示范围,去掉与生成0无关的数,只保留有效位数,当乘完n次后就得到0的个数。(pascal程序如F)vari5t,n,sum:longint;begint:=0;sum:=l;readln(n);fori:=ltondobeginsum:=sum*i;whilesummod10=0dobeginsum:=sumdiv1();inc(t);{i

7、-数器增加1}end;sum:=summod1000;{舍去与主成0无关的数}end;w

8、ritcln(t:6);end.算法二:此题中生成O的个数只与含5的个数有关,n!的分解数中含5的个数就等于末尾0的个数,因此问题转化为直接求n!的分解数中含5的个数。vart,n:integer;beginrcadln(n);t:=0;repeatn:=ndiv5;inc(t,n);{计数器增加n}untiln<5;writeln(t:6);end.分析对比两种算法就不难看出,它们的时间复杂度分别为o(N)、O(logN),算法二的执行时间远远小于算法一的执行时间。在信息学奥赛屮,其主要任务就是设计一个有效的算法,去求

9、解所给出的问题。如果仅仅学会一种程序设计语言,而没学过算法的选手在比赛中是不会取得好的成绩的,选手水平的高低在于能否设计出好的算法。下而,我们根据全国分区联赛大纲的要求,--起来探讨信息学奥赛中的基本算法。第二章基本算法模块对于NOIP,基础是相当重要的,在3个小时之内做完4道题,那么就要求我们有相当快的速度。特别是

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。