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)
问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1 样例 输入：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. 用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。 这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？ 看到这里大家可能有点迷惑了。 在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax3+bx2+cx+d中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作为判断条件是不准确的。 我们换一个角度来思考问题，设f(x)=ax3+bx2+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*(x+0.005)<0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果f(x-0.005)=0，哪么就说明x-0.005是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作为判定条件。为了程序设计的方便，我们设计一个函数f(x)计算ax3+bx2+cx+d的值，程序如下： {$N+} var k:integer; a,b,c,d,x:extended; function f(x:extended):extended; {计算ax3+bx2+cx+d的值} begin f:=((a*x+b)*x+c)*x+d; end; begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if (f(x-0.005)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,' '); {若x两端的函数值异号或x-0.005刚好是方程的根，则确定x为方程的根} end; end. 用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。 信息学奥赛中的基本算法(回溯法) 如果上期的“百钱买百鸡”中鸡的种类数是变化的，用枚举法就无能为力了， 这里介绍另一种算法——回溯法。 回溯基本思想 回溯法是一种既带有系统性又带有跳跃性的搜索法，它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。 例1、从N个自然数(1,2,…,n)中选出r个数的所有组合。 算法分析：设这r个数为a1,a2,?ar,把它们从大到小排列，则满足： （1） a1>a2>?>ar; （2） 其中第i位数(1<=i<=r)满足ai>r-i; 我们按以上原则先确定第一个数，再逐位生成所有的r个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值??按此规则不断循环搜索，直到找出r个数的组合，这种求解方法就是回溯法。 如果按以上方法生成了第i位数ai，下一步的的处理为： （1） 若ai>r-i且i=r，则输出这r个数并改变ai的值:ai=ai-1; （2） 若ai>r-i且i≠r，则继续生成下一位ai+1=ai-1; （3） 若ai<=r-i，则回溯到上一位，改变上一位数的值:ai-1=ai-1-1; 算法实现步骤： 第一步：输入n,r的值，并初始化； i:=1;a[1]:=n; 第二步：若a[1]>r-1则重复： 若a[i]>r-i，①若i=r，则输出解，并且a[i]:=a[i]-1; ②若i<>r，则继续生成下一位：a[i+1]:=a[i]-1; i:=i+1; 若 a[i]<=r-i，则回溯：i:=i-1; a[i]:=a[i]-1; 第三步：结束； 程序实现 var n,r,i,j:integer; a:array[1..10] of integer; begin readln(n,r);i:=1;a[1]:=n; repeat if a[i]>r-i then {符合条件 } if i=r then {输出} begin for j:=1 to r do write(a[j]:3); writeln; a[i]:=a[i]-1; end else {继续搜索} begin a[i+1]:=a[i]-1; i:=i+1;end else{回溯} begin i:=i-1; a[i]:=a[i]-1;end; until a[1]=r-1; end. 下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。 例2 数的划分（noip2001tg） 问题描述 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。 例如：n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 输入：n，k (6 输入： 7 3 输出：4 {四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;} 算法分析：此题可以用回溯法求解，设自然数n拆分为a1,a2,…,ak,必须满足以下两个条件： （1） n=a1+a2+…+ak ； （2） a1<=a2<=…<=ak (避免重复计算)； 现假设己求得的拆分数为a1,a2,…ai,且都满足以上两个条件,设sum=n-a1-a2-…-ai,我们根据不同的情形进行处理： （1） 如果i=k,则得到一个解，则计数器t加1，并回溯到上一步，改变ai-1的值； （2） 如果i （3） 如果i 第一步：输入自然数n,k并初始化；t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k; 第二步：如果a[1]<=nk 重复： 若i=k，搜索到一个解，计数器t=t+1;并回溯； 否则：①若sum>=a[i]则继续搜索； ②若sum 搜索时，inc(i);a[i]:=a[i-1];sum:=sum-a[i]; 回溯时，dec(i); inc(a[i]); sum:=sum+a[i+1]-1; 第三步：输出。 程序如下： var n,nk,sum,i,k:integer; t:longint; a:array[1..6]of integer; begin readln(n,k); nk:=n div k; t:=0; i:=1;a[i]:=1; sum:=n-1;{初始化} repeat if i=k then{判断是否搜索到底} begin inc(t); dec(i);inc(a[i]); sum:=sum+a[i+1]-1; end {回溯} else begin if sum>=a[i] then {判断是否回溯} begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜} else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯} end; until a[1]>nk; writeln(t); end. 回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在NOIP中有许多涉及搜索问题的题目都可以用回溯法来求解。 信息学奥赛中的基本算法(递归算法) 递归算法的定义： 如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。 我们先来看看大家熟知的一个的故事： 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说?? 上面的故事本身是递归的，用递归算法描述： procedure bonze-tell-story； begin if 讲话被打断 then 故事结束 else begin 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事； bonze-tell-story； end end; 从上面的递归事例不难看出，递归算法存在的两个必要条件： （1） 必须有递归的终止条件；
信息学奥赛 - 算法入门教程
