2013教科版选修1《穷举法》课件.pptVIP

穷举法 一、引入 实例一：输入绳子的长度n，将该绳子分成三段，每段的长度为正整数，输出由该三段绳子组成的三角形个数。 一、引入 s:=0; for a:=1 to n-2 do for b:=a to n-2 do for c:=b to n-2 do if (a+bc) and (b+ca) and (c+ab) and (a+b+c=n) then s:=s+1; 一、引入 s:=0; for a:=1 to n-2 do for b:=a to n-2 do begin c:=n-a-b; if (a+bc) and (b+ca) and (c+ab) and (c=b) then s:=s+1; end; 二、穷举法的基本概念 三、穷举算法模式 四、穷举法应用 实例二：有形如：ax3+bx2+cx+d=0? 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d? 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。 提示：记方程f(x)=0，若存在2个数x1和x2，且x1x2，f(x1)*(x2)0，则在(x1，x2)之间一定有一个 根。 样例 输入：1?? -5?? -4?? 20 输出：-2.00?? 2.00?? 5.00 本题是2001年全国信息学奥林匹克竞赛高中组复赛第一题，如果考虑解方程的话则比较麻烦。我们可以换个角度思考问题，在-100到100之间找三个满足方程的实数，由于穷举时必须用整型变量，题目又要求保留两位小数，我们只需将循环变量扩大100倍即可顺利穷举，最后只要将所求结果再缩小100倍即可。 程序如下： Var a,b,c,d,x:real; i,x1,x2,x3:Integer; Begin Read(a,b,c,d); x1:=MaxInt; x2:=x1; x3:=x1; For i:=-10000 To 10000 Do Begin x:=i/100; If Abs(a*x*x*x+b*x*x+c*x+d)0.000001 Then If ix1 Then x1:=i Else If ix2 Then x2:=i Else If ix3 Then x3:=i;{确保x1x23} End; Writeln(x1/100:0:2, ,x2/100:0:2, ,x3/100:0:2); End. 四、穷举法应用 四、穷举法应用 四、穷举法应用 四、穷举法应用 四、穷举法应用 四、穷举法应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 五、穷举算法的深入应用 procedure print; var i:integer; begin for i:=1 to n do write(s[i]:2); writeln end; begin while s[0]=1 do begin j:=n; while? (s[j]=4) ?do?j:=j-1; s[j]:=s[j]+1; for?I:=j+1?to?n?do?? s[I]：=1; ? if check then print; end; end. procedure print; var i:integer; begin for i:=1 to n do write(s[i]:2); writeln end; procedure search(k: integer); var i:integer; begin if k n then begin if