算法基础5.doc资源-CSDN文库

需积分: 3 11 浏览量 2016-07-05 15:24:27 上传评论收藏 272KB DOC 举报

资源推荐

资源详情

资源评论

算法在信息学奥赛中的应用 (基础篇)

学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决

一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计

语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的

过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题

的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有

有效算法的程序就像一个没有灵魂的躯体。

算法具有五个特征：

1、有穷性：一个算法应包括有限的运算步骤，执行了有穷的操作后将终止

运算，不能是个死循环；

2、确切性：算法的每一步骤必须有确切的定义，读者理解时不会产生二义

性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能

得出相同的输出。如在算法中不允许有“计算 8/0”或“将 7 或 8 与 x 相加”之类的运

算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种

也不知道。

3、输入：一个算法有 0 个或多个输入，以描述运算对象的初始情况，所谓

0 个输入是指算法本身定义了初始条件。如在 5 个数中找出最小的数，则有 5 个

输入。

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，

这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在 5 个数中

找出最小的数，它的出输出为最小的数。如果一个程序没有输出，这个程序就毫

无意义了；

5、可行性：算法中每一步运算应该是可行的。算法原则上能够精确地运行，

而且人能用笔和纸做有限次运算后即可完成。

如何来评价一个算法的好坏呢？主要是从两个方面：

一是看算法运行所占用的时间；我们用时间复杂度来衡量，例如：在以下 3

个程序中，

（1）x:=x+1

（2）for i:=1 to n do

x:=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 和 n

则这三

个程序段的时间复杂度分别为 O（1）， O（n）， O（n

），分别称为常量阶、

线性阶和平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶

O(log n)，指数阶 O(2

)等。在 n 很大时，不同数量级的时间复杂度有：O(1)<

O(log n)<O(n)< O(nlog n)<O(n

) <O(n

) <O(2

)，很显然，指数阶的算法

不是一个好的算法。

二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术

end.

分析对比两种算法就不难看出，它们的时间复杂度分别为

O（N）、 O（logN）,算法二的执行时间远远小于算法一的执行时间。

在信息学奥赛中，其主要任务就是设计一个有效的算法，去求解所给出的问

题。如果仅仅学会一种程序设计语言，而没学过算法的选手在比赛中是不会取得

好的成绩的，选手水平的高低在于能否设计出好的算法。

下面，我们根据全国分区联赛大纲的要求，一起来探讨信息学奥赛中的基本

算法。

信息学奥赛中的基本算法(枚举法)

枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题

目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问

题的解。

采用枚举算法解题的基本思路：

（1）确定枚举对象、枚举范围和判定条件；

（2）一一枚举可能的解，验证是否是问题的解

下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这

三个方面来探讨如何用枚举法解题。

例 1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一

看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你

编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？

算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别

设为 x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)

为判定条件，穷举各种鸡的个数。

下面是解这个百鸡问题的程序

var x,y,z:integer;

begin

for x:=0 to 100 do

for y:=0 to 100 do

for z:=0 to 100 do{枚举所有可能的解}

if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod

3=0)then writeln('x=',x,'y=',y,'z=',z); {验证可能的解，并输出符合题目要

求的解}

end.

上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡

（x,y），第三种鸡就可以根据约束条件求得（ z=100-x-y），这样就缩小了

枚举范围，请看下面的程序：

str(x*3,s); st:=st+s;

for c:='1' to '9' do{枚举 9 个字符，判断是否都在 st 中}

if pos(c,st)<>0 then inc(t) else break;{如果不在 st 中，则退出循环}

if t=9 then writeln(x,' ',x*2,' ',x*3);

end;

end.

在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不

全面，就穷举不出正确的结果，我们再看看下面的例子。

例３一元三次方程求解(noip2001tg)

问题描述有形如：ax

+bx

+cx+d=0 这样的一个一元三次方程。给出该方程

中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围

在-100 至 100 之间)，且根与根之差的绝对值>=1。

要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到

小数点后 2 位。

提示：记方程 f(x)=0，若存在 2 个数 x1 和 x2，且 x1<x2，f(x1)*(x2)<0，则在

(x1，x2)之间一定有一个根。

样例

输入：1 -5 -4 20

输出：-2.00 2.00 5.00

算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分法。

用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢？再

分析一下题目，根的范围在-100 到 100 之间，结果只要保留两位小数，我们不

妨将根的值域扩大 100 倍（-10000<=x<=10000），再以根为枚举对象，枚

举范围是-10000 到 10000，用原方程式进行一一验证，找出方程的解。

有的同学在比赛中是这样做

var

k:integer;

a,b,c,d,x :real;

begin

read(a,b,c,d);

for k:=-10000 to 10000 do

begin

x:=k/100;

if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' ');

end;

end.

用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，

等成绩下来才发现这题没有全对，只得了一半的分。

这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题

不能用枚举法做吗？看到这里大家可能有点迷惑了。

在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，

剩余33页未读，继续阅读

评论收藏

内容反馈

唐之风采

粉丝: 0
资源: 3

算法基础5.doc

GIS算法基础重点.doc

地理信息系统算法基础复习.doc

数据结构及算法基础报告.doc

数据结构与算法笔试题基础.doc

C语言算法基础.doc

FDK算法基础介绍.doc

一 基础算法.doc

机器人学算法基础.doc

ALL-算法基础.doc

python算法基础.doc

基础算法教案.doc

RSA算法的数论基础.doc

信息安全技术 SM9密码算法使用规范.doc

实验项目一：基础算法设计.doc

2013算法.doc

程序设计基础（算法）.doc

数据结构基础与算法.doc

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

仿真电路以及操作方法

【纯干货啊】华为IPD流程管理(完整版).pptx

可编程语言标准IEC61131-3中文版.pdf

OFDM完整仿真过程与教程.zip

信号与系统——保研复习资料.pdf

Landsat_WRS2.zip

最全的Visio形状/图形库

AxureRP9项目原型50套、案例20个、元件库1套.zip

北理工+成电+东南——通信/信号保研面试真题.pdf

数字信号处理——保研复习资料.pdf

风电和储能并网Simulink模型

最新资源

一基础算法.doc

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar