好文档 - 专业文书写作范文服务资料分享网站

信息学奥赛 - 算法入门教程 

天下 分享 时间: 加入收藏 我要投稿 点赞

end;{for} end.

信息学奥赛中的基本算法(贪心法)

在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。

从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。

我们看看下面的例子

贪心法应用

例1 均分纸牌(NOIP2002tg)

[问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的:

从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。 [输 入]:键盘输入文件名。

文件格式:N(N 堆纸牌,1 <= N <= 100)

A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输 出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in:

4

9 8 17 6 屏慕显示:3

算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。

我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0

(1) 若a[i]>v,则将a[i]-v张纸牌从第I堆移动到第I+1堆; (2) 若a[i]

为了设计的方便,我们把这两种情况统一看作是将a[I]-v张牌从第I堆移动到第I+1堆;移动后有:a[I]:=v;a[I+1]:=a[I+1]+a[I]-v;

在从第i+1堆中取出纸牌补充第i堆的过程中,可能会出现第i+1堆的纸牌数小于零(a[i+1]+a[i]-v<0 )的情况。

如n=3,三堆纸牌数为(1,2,27)这时v=10,为了使第一堆数为10,要从第二堆移9张纸牌到第一堆,而第二堆只有2张纸牌可移,这是不是意味着刚才使用的贪心法是错误的呢?

我们继续按规则分析移牌过程,从第二堆移出9张到第一堆后,第一堆有10张纸牌,第二堆剩下-7张纸牌,再从第三堆移动17张到第二堆,刚好三堆纸牌数都是10,最后结果是对的,从第二堆移出的牌都可以从第三堆得到。我们在移动过程中,只是改变了移动的顺序,而移动的次数不变,因此此题使用贪心法是可行的。 源程序: var

i,n,s:integer;v:longint; a:array[1..100]of longint; f:text;fil:string; begin

readln(fil);

assign(f,fil);reset(f); readln(f,n);v:=0;

for i:=1 to n do begin

read(f,a[i]); inc(v,a[i]); end;

v:=v div n; {每堆牌的平均数} for i:=1 to n-1 do

if a[i]<>v then {贪心选择} begin

inc(s);{移牌步数计数}

a[i+1]:=a[i+1]+a[i]-v;{使第i堆牌数为v} end;{then} writeln(s); end.

利用贪心算法解题,需要解决两个问题:

一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统有3种币值,面值分别为一角、五分和一分,求最小找币数时,可以用贪心法求解;如果将这三种币值改为一角一分、五分和一分,就不能使用贪心法求解。用贪心法解题很方便,但它的适用范围很小,判断一个问题是否适合用贪心法求解,目前还没有一个通用的方法,在信息学竞赛中,需要凭个人的经验来判断何时该使用贪心算法。

二是确定了可以用贪心算法之后,如何选择一个贪心标准,才能保证得到问题的最优解。在选择贪心标准时,我们要对所选的贪心标准进行验证才能使用,不要被表面上看似正确的贪心标准所迷惑,如下面的列子。

例2 (NOIP1998tg)设有n个正整数,将他们连接成一排,组成一个最大的多位整数。例如:n=3时,3个整数13,312,343,连成的最大整数为:34331213

又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613 输入:N

N个数

输出:连接成的多位数

算法分析:此题很容易想到使用贪心法,在考试时有很多同学把整数按从大到小的顺序连接起来,测试题目的例子也都符合,但最后测试的结果却不全对。按这种贪心标准,我们很容易找到反例:12,121 应该组成12121而非12112,那么是不是相互包含的时候就从小到大呢?也不一定,如:12,123 就是12312而非12112,这样情况就有很多种了。是不是此题不能用贪心法呢?

其实此题是可以用贪心法来求解,只是刚才的贪心标准不对,正确的贪心标准是:先把整数化成字符串,然后再比较a+b和b+a,如果a+b>b+a,就把a排在b的前面,反之则把a排在b的后面。 源程序: var

s:array[1..20] of string; t:string;i,j,k,n:longint; begin

readln(n);

for i:=1 to n do begin read(k);

str(k,s[i]); end;

for i:=1 to n-1 do for j:=i+1 to n do

if s[i]+s[j]

end;

for i:=1 to n do write(s[i]); end.

贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。

算法在信息学奥赛中的应用(搜索法一)

在这里介绍两种基本的搜索算法:深度优先搜索和广度优先搜索法,以树的搜索为例,深度优先搜索法是优先扩展尚未扩展的且具有最大深度的结点;广度优先搜索法是在扩展完第K层的结点以后才扩展K+1层的结点。

深度优先搜索法与前面讲的回溯法差不多,主要的区别是回溯法在求解过程中不保留完整的树结构,而深度优先搜索则记下完整的搜索树,搜索树起记录解路径和状态判重的作用。为了减少存储空间,在深度优先搜索中,用标志的方法记录访问过的状态,这种处理方法使得深度优先搜索法与回溯法没什么区别了。在回溯法中,我们己分析了非递归的实现过程,在这里就只讨论深度优先的递归实现方法。

深度优先搜索的递归实现过程: procedure dfs(i); for i:=1 to r do

if 子结点mr符合条件then 产生的子结点mr入栈; if 子结点 mr 是目标结点 then 输出

else dfs(i+1);

栈顶元素出栈(即删去mr); endif; endfor;

在讲解递推法时,我们讨论了用递推法解骑土游历问题,在这里我们再看看如何用深度优先搜索法求解此题。

搜索算法应用

例1骑士游历:设有一个n*m的棋盘,在棋盘上任一点有一个中国象棋马,马走的规则为:1.马走日字 2.马只能向右走。当N,M 输入之后,找出一条从左下角到右上角的路径。例如:输入 N=4,M=4,输出:路径的格式:(1,1)->(2,3)->(4,4),若不存在路径,则输出\

算法分析:我们以4×4的棋盘为例进行分析,用树形结构表示马走的所有过程(如下图),求从起点到终点的路径,实际上就是从根结点开始深度优先搜索这棵树。

马从(1,1)开始,按深度优先搜索法,走一步到达(2,3),判断是否到达终点,若没有,则继续往前走,再走一步到达(4,4),然后判断是否到达终点,若到达则退出,搜索过程结束。为了减少搜索次数,在马走的过程中,判断下一步所走的位置是否在棋盘上,如果不在棋盘上,则另选一条路径再走。 程序如下:

const

dx:array[1..4]of integer=(2,2,1,1); dy:array[1..4]of integer=(1,-1,2,-2); type

map=record

x,y:integer; end; var

i,n,m:integer; a:array[0..50]of map; procedure dfs(i:integer); var j:integer; begin

for j:=1 to 4 do

if (a[i-1].x+dx[j]>0)and(a[i-1].x+dx[j]<=n)

and(a[i-1].y+dy[j]>0)and(a[i-1].y+dy[j]<=n) then{判断是否在棋盘上} begin

信息学奥赛 - 算法入门教程 

end;{for}end.信息学奥赛中的基本算法(贪心法)在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而
推荐度:
点击下载文档文档为doc格式
7jdgg3ljxx41z4g1rywu
领取福利

微信扫码领取福利

微信扫码分享