源程序： 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] 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 a[i].x:=a[i-1].x+dx[j]; a[i].y:=a[i-1].y+dy[j];{入栈} if (a[i].x=n)and(a[i].y=m)then begin write('(',1,',',1,')'); for j:=2 to i do write('->(',a[j].x,',',a[j].y,')'); halt;{输出结果并退出程序} end; dfs(i+1);{搜索下一步} a[i].x:=0;a[i].y:=0;{出栈} end; end; begin a[1].x:=1;a[1].y:=1; readln(n,m); dfs(2); writeln('no'); end. 从上面的例子我们可以看出，深度优先搜索算法有两个特点： 1、己产生的结点按深度排序，深度大的结点先得到扩展，即先产生它的子结点。 2、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。 对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和 编程技巧上又都不相同，甚至会有很大的差别。我们再看看另一个例子。 题二 选数（存盘名：NOIP2002pj） [问题描述]:已知 n 个整数 x1,x2,?,xn，以及一个整数 k(k＜n)。从n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29。 [输入]：键盘输入，格式为： n , k (1<=n<=20，k＜n) x1,x2，?,xn （1<=xi<=5000000） [输出]：屏幕输出，格式为： 一个整数（满足条件的种数）。 [输入输出样例]: 输入：4 3 3 7 12 19 输出：1 算法分析：本题是求从n个数中选k个数的组合，并使其和为素数。求解此题时，先用深度优先搜索法生成k个数的组合，再判断k个数的和是否为素数，若为素数则总数加1。 在程序实现过程中，用数组a存放输入的n个数，用s表示k个数的和，ans表示和为素数的个数。为了避免不必要的搜索，程序对搜索过程进行了优化，限制搜索范围，在搜索过程dfs(i,m)中，参数m为第i个数的上限，下限为n-k+i。 源程序： var n,k,i: byte; ans,s:longint; a: array[1 .. 20] of Longint;