tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 文学 >>

穷举法


穷举法

2007夏令营

穷举法

一、引入
实例一:编一个程序找出所有的三位数到七位数中 的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数, 它的定义如下:若一个n位自然数的各位数字的n 次方之和等于它本身,则称这个自然数为阿姆斯 特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一 个三位数的阿姆斯特朗数,8208则是一个四位数 的阿姆斯特朗数。
算法分析:由于阿姆斯特朗数是没有规律的,所以程 序只能采用穷举法,一一验证范围内的数是否阿姆斯 特朗数,若是则打印之。

穷举法

一、引入
算法描述: for I:=100 to 9999999 do begin 拆分I各位上的数字; 计算I的位数; 验证是否是阿姆斯特朗数,若是则输出; end;

穷举法

二、穷举法的基本概念

穷举方法是基于计算机特点而进行解题的思维方法。 一般是根据问题中的部分条件(约束条件)将所有 可能解的情况列举出来,然后通过一 一验证是否符 合整个问题的求解要求,而得到问题的解。这样解 决问题的方法我们称之为穷举算法。穷举算法特点 是算法简单,但运行时所花费的时间量大。因此, 我们在用穷举方法解决问题时,应尽可能将明显的 不符合条件的情况排除在外,以尽快取得问题的解。

穷举法

三、穷举算法模式
1、问题解的可能搜索的范围: 用循环或循环嵌套结构实现 2、写出符合问题解的条件。 3、能使程序优化的语句,以便缩小搜索范 围,减少程序运行时间。

穷举法

四、穷举法应用
穷举法应用很多,比如一些密码破译软件通 常就是用的穷举算法。如在QQ上, OicqPassOver这个工具穷举你的口令,它根 据机器性能最高可以每秒测试20000个口令, 如果口令简单,一分钟内,密码就会遭到破 译。下面我们来以三个例子说明穷举法的基 本应用。

穷举法

四、穷举法应用
实例二:4皇后问题。
问题描述:在4×4的棋盘上安置4个皇后,要求 任意两个皇后不在同一行、不在同一列、不在同 一对角线上,输出所有的方案。 分析:

1) 本题是一个搜索问题,搜索范围 44,找出符 合条件的方案;
2)方案必须满足的条件:任意两个不在同一行、 同一列和同一对角线。

穷举法

四、穷举法应用
程序: const n=4; type stack=array[1..n] of integer; var i1,i2,i3,i4:integer; s:stack; function check:boolean; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do
if (s[i]=s[j]) or (s[i]-i=s[j]-j) or (s[i]+i=s[j]+j)

end;

then begin check:=false; exit end; check:=true

穷举法

四、穷举法应用
procedure print; var i:integer; begin for i:=1 to n do write(s[i]:2); writeln end; begin for i1:=1 to n do for i2:=1 to n do for i3:=1 to n do for i4:=1 to n do begin s[1]:=i1;s[2]:=i2;s[3]:=i3;s[4]:=i4; if check then print; end; end.

穷举法

四、穷举法应用
实例三:阿姆斯特朗数。
问题描述:编一个程序找出所有的三位数到七位 数中的阿姆斯特朗数。 阿姆斯特朗数也叫水仙 花数,它的定义如下:若一个n位自然数的各位数 字的n次方之和等于它本身,则称这个自然数为阿 姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5) 是一个三位数的阿姆斯特朗数,8208则是一个四 位数的阿姆斯特朗数。

穷举法

四、穷举法应用
算法分析:
为了使得程序尽快运行出正确结果,程序中使用 了一个数组power存放所有数字的各次幂之值, power[i,j]等于i的j次方。变量currentnumber 存放当前要被验证的数,数组digit存放当前数的 各位数字,开始时digit[3]=1,其它元素均为0,此 时表示当前数为100。 highest为当前数的位数。

穷举法

四、穷举法应用
程序: program ex3(input,outoutp); const maxlen=7; var i,j,currentnumber,highest,sum,total:longint; digit:array [0..maxlen+1] of integer; power:array [0..9,0..maxlen] of longint; begin for i:=0 to 9 do begin power[i,0]:=1; for j:=1 to maxlen do power[i,j]:=power[i,j-1]*i end;

穷举法

四、穷举法应用
for i:=1 to maxlen do digit[i]:=0; digit[3]:=1; highest:=3; currentnumber:=100; total:=0; while digit[maxlen+1]=0 do begin sum:=0; for i:=1 to highest do sum:=sum+power[digit[i],highest]; if sum=currentnumber then begin total:=total+1; write(currentnumber:maxlen+5); if total mod 6=0 then writeln end;

穷举法

四、穷举法应用
digit[1]:=digit[1]+1; i:=1; while digit[i]=10 do begin digit[i+1]:=digit[i+1]+1; digit[i]:=0; i:=i+1 end; if i>highest then highest:=i; currentnumber:=currentnumber+1 end; writeln end.

穷举法

四、穷举法应用
算法中的时间和空间往往是矛盾的,时间复杂性 和空间复杂性在一定条件下也是可以相互转化的, 有时候为了提高程序运行的速度,在算法的空间要 求不苛刻的前提下,设计算法时可考虑充分利用有 限的剩余空间来存储程序中反复要计算的数据,这 就是“用空间换时间”策略,是优化程序的一种常 用方法。相应的,在空间要求十分苛刻时,程序所 能支配的自由空间不够用时,也可以以牺牲时间为 代价来换取空间,由于当今计算机硬件技术发展很 快,程序所能支配的自由空间一般比较充分,这一 方法在程序设计中不常用到。

穷举法

四、穷举法应用
实例四:学校名次。
问题描述:有A,B,C,D,E5所学校。在一次检 查评比中,已知E校肯定不是第2名或第3名,他 们互相进行推测。A校有人说,E校一定是第1名; B校有人说,我校可能是第2名;C校有人说,A校 最差;D校有人说,C校不是最好的;E校有人说, D校会获第1名。结果只有第1名和第2名学校的人 猜对了。编程指出这5所学校的名次。

穷举法

四、穷举法应用
分析:本题是一个逻辑判断题,一般的逻辑判断题都采 用穷举法进行解决。我们对5所学校所得名次的各种可 能情况进行穷举。在每种情况中,为了防止不同学校取 相同的名次,设立了逻辑数组x,x[I]为false表示已有 某校取第I名。 此题的难点在于确定判断条件。我们设立逻辑变量b0来 描述这一条件,主要有两个条件:“E校不是第2名或第 3名”与“只有第1名和第2名的学校的人猜对”,后一 条件要判断:1)是否只有两人说法正确?2)说得正确 的人是否是取得第1名和第2名的学校的人?要判断是否 仅有两人说正确,须统计正确命题的个数。为此,设立 了函数bton,将逻辑量数值化。

穷举法

四、穷举法应用
程序: program l3(output); var i,a,b,c,d,e,m:integer; x:array[1..5] of boolean; b0,b1:boolean; function bton(b:boolean):integer; begin if b then bton:=-1 else bton:=0 end;

穷举法

四、穷举法应用
begin for i:=1 to 5 do x[i]:=true; for a:=1 to 5 do begin x[a]:=false; for b:=1 to 5 do if x[b] then begin x[b]:=false; for c:=1 to 5 do if x[c] then begin x[c]:=false; for d:=1 to 5 do if x[d] then

穷举法

四、穷举法应用
begin e:=15-a-b-c-d;b0:=(e<>2) and (e<>3);
m:=bton(e=1)+bton(b=2)+bton(a=5)+bton(c<>1)+bton(d=1);

b0:=b0 and (m=-2); b1:=(e=1) and (a<>2); b1:=b1 or (a=5) and(c<>1) and(c<>2); b1:=b1 or (c<>1) and (d<>1) and (d<>2); b1:=b1 or (d=1) and (e<>2); b0:=b0 and not b1; if b0 then x[d]:=true; end;

writeln('a=',a:2,' b=',b:2,' c=',c:2,' d=',d:2,' e=',e:2);

穷举法

四、穷举法应用
x[c]:=true;

end. 运行结果: a=5 b=2 c=1 d=3 e=4

end; x[b]:=true; end; x[a]:=true; end;

穷举法

五、穷举算法的深入应用
实例五:尺子的刻度。 问题描述:一根29厘米长的尺子, 只允许在上面刻 七个刻度, 要能用它量出 1~29 厘米的各种长度。 试问这根尺的刻度应该怎样选择? 分析: (1) 从 1~29 厘米中选择七个刻度的所有可能 情况数是: C7 29 = 29· 26· 24· = 28· 25· 23 1· 3· 5· 7 2· 4· 6· 29· 26· 2· 9· 5· 23= 29· 23· 26· 90= 1560780

穷举法

五、穷举算法的深入应用
(2) 对于每一组刻度的选择都需要判断是否能将 1~29 厘米的各种刻度量出来, 例如选择的刻度为: a1,a2,a3,a4,a5a,6,a7 那么能量出的刻度为:
a1, 29-a1; a2, a2-a1, 29-a2; a3, a3-a1 ,a3-a2, 29-a3 ; a4, a4-a1, a4-a2, a4-a3, 29-a4; a5, a5-a1, a5-a2, a5-a3, a5-a4, 29-a5; a6, a6-a1, a6-a2, a6-a3, a6-a4, a6-a5, 29-a6; a7-a1, a7-a2, a7-a2, a7-a3, a7-a4, a7-a5, a7-a6, 29-a7; 2 3 4 5 6 7 8

穷举法

五、穷举算法的深入应用
共可量出 2+3+4+5+6+7+8 种刻度, 即 35 种刻度, 事实上其中有许多刻度是重复的, 不可能复盖 1~29。 例如: 取 a1, a2, a3, a4, a5, a6, a7为1, 3, 6, 10, 15, 21, 28 能量出的刻度为:
1 , 28 3, 2, 26 6, 5, 3, 23 10, 9, 7, 4, 19 15, 14, 12, 9, 5, 14 21, 20, 18, 15, 11, 6, 8 28, 27, 25, 22, 18, 13, 7, 1

缺 16,17,24 ( 29 即尺子长度 )

穷举法

五、穷举算法的深入应用
如果找出了刻度a1, a2, a3, a4, a5, a6, a7 那么我们可以利用其 对称性 29-a1,29-a2,29-a3,29-a4,29-a5,29-a6,29-a7, 也是一 组解, 所以求解过程中可仅考虑 a1<a2<a3<a4<a5<a6<a7 的 情况。 很显然要使1,28 两种刻度能量出来, 则在七个刻度就必须有 1 或 28; 这样就可设a1=1 ( 或 a1=28 )。本题就变成了只要在 2~ 27 中选取六个刻度问题了。其刻度选择的数目为 C 26 6 = 26· 24· 22· = 26· 23· 7 = 230230 25· 23· 21 5· 11· 1· 3· 5· 2· 4· 6

这样解的范围就从百万变成了十万的数量级, 大大减少运 行次数。因此,我们在用穷举法求问题解时,应注意程序 的优化,尽可能减少搜索时间。 { 程序优化 }

穷举法

五、穷举算法的深入应用
(3) 为了判定七个刻度是否能够度量1~29的所有 长度, 可以用集合的方法, 也可以用数组的0,1数 据判断。下面的程序使用了数组的0,1方法。 Program p12_2 ; Const n=29 ; m=1; Var a:array [1..7] of integer; b:array [1..n] of 0..1 ; { 记录能量的刻度 } f:Boolean ; I , j : integer ;

穷举法

五、穷举算法的深入应用
BEGIN a[1]:=m; for a[2]:=2 to n-7 do for a[3]:=a[2]+1 to n-6 do for a[4]:=a[3]+1 to n-5 do for a[5]:=a[4]+1 to n-4 do for a[6]:=a[5]+1 to n-3 do for a[7]:=a[6]+1 to n-2 do begin for i:=1 to 29 do b[i]:=0;

穷举法

五、穷举算法的深入应用
for i:=1 TO 7 do begin b[a[i]]:=1; b[n-a[i]]:=1; b[n]:=1 ; { 初始化 } for j:=i+1 TO 7 do b[abs(a[j]-a[i])]:=1 end; j: =0; for i:=1 to n do j:=j + b[i]; if j=n then begin for i:=1 to 7 do write (a[i]:4); writeln ; end ; end; end.

穷举法

五、穷举算法的深入应用
运行程序的结果: 当 m=1 时得出两组刻度 1 2 14 18 21 24 27 1 4 10 17 22 24 27 m=28 时也可获得两组刻度 28 2 5 7 13 19 25 28 2 5 8 11 15 27 这两组刻度实际上是 m=1 的对称情况, 所以问题 的解实质上为两组结果。如果调整n=30 可以发现 在这样的情况下程序无解, 这说明取 30cm 长的尺 子, 若仍取七个刻度, 要能量出 1~30cm 的各种 长度, 是不可能的。

穷举法

五、穷举算法的深入应用

优化思路一:减少穷举的变量,在使用穷举算法之 前,先考虑一下解元素之间的关联,将一些非穷举 不可的解元素列为穷举变量,其他元素通过计算和 分析得出解元素的可能值。

穷举法

五、穷举算法的深入应用
实例六:邮票面值。 问题描述:邮局发行一套票面有四种不同值的邮票, 如果每封信所贴邮票张数不超过三枚,存在整数R, 使得用不超过三枚的邮票,可以贴出连续的整数1、 2、3,…,R来,找出这四种面值数,使得R值 最大。

穷举法

五、穷举算法的深入应用
分析: 本题知道每封信邮票数的范围(<=3 ),邮票有四 种类型,编程找出能使面值最大邮票。其算法是: (1) 面值不同的四种邮票,每封信所贴邮票不超过 3 张。 (2) 用这四种邮票贴出连序的整数,并且使R值最大。 (3) 用穷举法,找出所有符合条件的解。 (4) 本题用集合的方法统计邮票面值,提高判重的速度。 设四种邮票的面值分别为: A , B , C , D ,根据题意 设: A < B < C < D,因此 A=1 ,用循环语句完成搜索。

穷举法

五、穷举算法的深入应用

Program p12_3 ; var a, b , c , d : integer ; x, x0, x1 , x2 , x3, x4 : integer ; st1 : set of 1 ..100 ; Function number( a, b, c, d : integer ) : integer ; var n1, n2, n3 ,n4 , sum :integer ; begin st1:=[ ] ; for n1:= 0 to 3 do { 每种邮票所取的张数 } for n2:= 0 to 3-n1 do for n3:= 0 to 3-n1- n2 do for n4:= 0 to 3-n1-n2-n3 do begin

穷举法

五、穷举算法的深入应用
if n1+n2+n3+n4 <= 3 then begin sum:= n1*a+n2*b+n3*c+n4*d ; { 计算信封的邮票面值 } st1:=st1+[sum] end; end; sum:=1 ; while sum in st1 do sum:=sum+1; number:= sum-1; end ; { 函数结束 }

穷举法

五、穷举算法的深入应用
BEGIN { main } a:=1 ; x0:=0 ; for b:= a+1 to 3*a+1 do for c:= b+1 to 3*b+1 do { 每种邮票的可取值的范围 } for d:= c+1 to 3*c+1 do begin x:= number (a, b, c, d ); 调用函数求每封信的邮票总面值 } if x > x0 then begin x0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d { 保存最大面值邮票 } write( x1:5, x2:5, x3:5, x4:5 ); writeln( ‘ ‘:10, 'x0=', x0 );end;end; end.

穷举法

五、穷举算法的深入应用
程序运行后,其输出结果是:{ 解答结果有11 组} 1 2 3 4 x0=12 1 2 3 5 x0=13 ……. 1 3 6 10 x0=23 1 4 7 8 x0=24 优化思路二: 减少穷举变量的值域,通过和穷举变量间的数 学关系定义解元素的值域。

穷举法

五、穷举算法的深入应用
实例七:方格填数。 问题描述:如图所示的8个格子中放入1~8八个数 字,使得相邻的和对角线的数字之差不为1。编 程找出所有放法。

穷举法

五、穷举算法的深入应用
分析:我们先不考虑后一条件, 只考虑第一个条件,即把1~8八 个数字放入8个格子中。这是容易 做到的,就是8个数字的全排列, 共 有 8!=40320 种 放 法 。 然 后 对 这8!个可行解用后一个条件加以 检验,输出符合条件的解。对于 后一个条件中“相邻”的判断, 可以建立一个邻接表来解决:

1 1 1 2 2 2 3 …… 13 6 14 7

1 2 3 4 5 6 7

2 3 4 3 5 6 4
7 8

穷举法

五、穷举算法的深入应用
表中表示哪两个格子是相邻的,link[i,1]和link[i,2]是相 邻的格子的编号。全排列的产生,可以用八重循环,也可 以用专门的算法,程序留给同学们自己去完成。利用穷举 策略编制的程序,其运算量一般是很大的,因此如何提高 算法效率是穷举算法一个很重要的问题。一般应尽量减少 可行解的个数,使得第二步的检验运算量尽可能地少。

如何来优化算法呢?

穷举法

五、穷举算法的深入应用

如果注意到b3和b6两个格子,与它们“相邻”的格子有 6个,也就是说,放入这两个格子中的数,必须和6个数 不连续,仅可以和一个数是连续的,这样的数只有2个, 即1和8。这样,b1,b3,b6,b8;4个格子中数的放法 仅有两种可能:2、8、1、7和7、1、8、2。而b2、b4、 b5、b7四个格子中的数仅需在3~6四个数中选择。经过 上述优化,可行解仅有:2×4!=48个,大大减少了计 算量。并且检验是否符合要求,也只需检查(1,2),(1, 4),(2,5),(4,7),(5,8),(7,8)这6对数之差就 可以了。

穷举法

五、穷举算法的深入应用
program exampleb; const link:array[1..6,1..2] of integer= ((1,2),(1,4),(2,5),(4,7),(5,8),(7,8)); var b:array[1..8] of integer; procedure print; begin writeln(' ',b[1]:2); writeln(b[2]:2,b[3]:2,b[4]:2); writeln(b[5]:2,b[6]:2,b[7]:2); writeln(' ',b[8]:2) end;

穷举法

五、穷举算法的深入应用
function choose:boolean; var i: integer; begin choose:= false; for i:=1 to 6 do if abs(b[link[i, 1]] - b[link[i ,2]]) = 1 then exit; choose := true end;

穷举法

五、穷举算法的深入应用
procedure try; begin for b[2]:=3 to 6 do for b[4]:= 3 to 6 do if b[2]<>b[4] then for b[5]:= 3 to 6 do if (b[5]<>b[2]) and (b[5]<>b[4]) then begin b[7]:= 18 - b[2] - b[4] - b[5]; if choose then print; end; end;

穷举法

五、穷举算法的深入应用
begin b[1]:=2;b[3]:=8;b[6]:= 1;b[8]:=7; try; b[1]:=7;b[3]:=1 ;b[6]:=8;b[8]:=2; try; readln end.

穷举法

五、穷举算法的深入应用
优化思路三:分解约束条件,将拆分的约束条件嵌 套在相应的循环体间,尽可能减少可行解的数目, 也称为“剪枝”,即把明显不符合条件的可行解尽 可能地剪去,减少穷举的计算量。

穷举法

六、实例分析:
实例八:巧妙填数。 问题描述:将1~9这九个数字填入九个空格中。 每一横行的三个数字组成一个三位数。如果要使第 二行的三位数是第一行的两倍,第三行的三位数是 第一行的三倍,应怎样填数。如图所示。 1 3 5 9 8 7 2 4 6

穷举法

六、实例分析:
分析:本题目有9个格子,要求填数,如果不考虑 问题给出的条件,共有9!=362880种方案,在 这些方案中符合问题条件的即为解。因此可以采用 穷举法。 但仔细分析问题,显然第一行的数不会超过400, 实际上只要确定第一行的数就可以根据条件算出 其他两行的数了。这样仅需穷举400次。

穷举法

六、实例分析:
program ex_8(input,output); var i,j,k,s:integer; function sum(s:integer):integer; begin sum:=s div 100+s div 10 mod 10+s mod 10 end;{sum} function mul(s:integer):longint; begin mul:=(s div 100)*(s div 10 mod 10)*(s mod 10) end;{mul}

穷举法

六、实例分析:
Begin for i:=1 to 3 do for j:=1 to 9 do if j<>i then for k:=1 to 9 do if (k<>j) and (k<>i) then begin s:=i*100+j*10+k; if 3*s<1000 then if (sum(s)+sum(2*s)+sum(3*s)=45) and (mul(s)*mul(2*s)*mul(3*s)=362880) then begin writeln(s);writeln(2*s);writeln(3*s); writeln; end; end; end.

穷举法

六、实例分析:
实例九:(第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题) 将n个整数分成k组(k≤n,要求每组不能为空),显然这k个 部分均可得到一个各自的和s1,s2,……sk,定义整数P 为:P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2s3)2+……+(Sk-1-Sk)2 问题求解: 求出一种分法,使P为最小(若有多种方案仅记一种) 程序说明: 数组:a[1],a[2],...A[N]存放原数 s[1],s[2],...,s[K]存放每个部分的和 b[1],b[2],...,b[N]穷举用临时空间 d[1],d[2],...,d[N]存放最佳方案

穷举法

六、实例分析:
程序: program exp4; Var i,j,n,k : integer; a :array [1..100] of integer; b,d:array [0..100] of integer; s :array[1..30] of integer; begin readln(n,k); for I:=1 to n do read(a[I]); for I:=0 to n do b[I]:=1; cmin:=1000000;

穷举法

六、实例分析:
while (b[0]=1) do begin for I:=1 to k do ① for I:=1 to n do ② sum:=0; for I:=1 to k-1 do for j:= ③ sum:=sum+(s[I]-s[j])*(s[I]-s[j]); if ④ then begin cmin:=sum; for I:=1 to n do d[I]:=b[I]; end;

穷举法

六、实例分析:
j:=n; while ⑤ do j:=j-1; b[j]:=b[j]+1; for I:=j+1 to n do ⑥ end; writeln(cmin); for I:=1 to n do write(d[I]:40); writeln;

end.

穷举法

六、实例分析:
答案: 1、 S[I]:=0; 2、 S[b[I]]:=s[b[i]]+a[I]; 3、 I+1 to k do 4、 (cmin> sum ) 5、 (b[j]=k) 6、 b[I]:=1;

穷举法

穷举法小结:
穷举的思想往往是最容易想到的一种解题策略,穷 举算法从本质上说,它是一种搜索算法。适合穷举 策略求解的问题,首先必须满足其问题规模和可能 解的规模(个数)不是特别大,且解变量的值的变 化具有一定的规律性。 实际应用中,许多复杂问题的求解策略不止使用 一种算法,穷举算法在这类问题的求解过程中起 到相当关键的作用。如圆桌骑士问题。如果问题 规模很大,而又能找到其他的算法解决,则不宜 采用穷举法,如全排列问题,可用构造法解决。

穷举法

圆桌骑士问题:
很多世纪以前,阿瑟王和他的圆桌武士常在每年元旦聚会 庆祝他们的友谊。我们用一个单人玩的棋盘游戏去纪念这 个史实:一个国王和多个武士被随机放在8X8的正方形棋 盘的不同方格上。只要不越出棋盘,国王可以移至与之相 邻的方格内,只要不越出棋盘,武士可以跳日字,在棋局 当中,选手可以在同一方格内摆放多个棋子,选手的目标 是在尽可能少的步数内把所有的棋子集中到同一方格。为 此,他必须按前述方法去移动棋子。此外,当国王和一个 或多个武士位于同一方格内时,选手可以选择此后让国王 跟随其中一个武士一同向聚会终点移动,就象移动单个武 士一样。任务:写出一个程序去计算选手要实现聚会所需 最少的移动次数。

穷举法

圆桌骑士问题:
1 2

3
4 5 6 7

O O O

O * O

O O O

*为国王, 图示国王 所有可能 的移动

8

A

B

C

D

E

F

G

H

穷举法

圆桌骑士问题:

O O *

O O *为武士, 图示武士 所有可能 的移动

O
O O

O

穷举法

圆桌骑士问题:
输入数据:文件camelot.in包括了以字符串表示的棋盘 初始状态。该字符串包含了一串最多有64个不同的棋子 位置:首先是国王的位置,而随后是武士们的位置。每个 位置由一对字母-数字表示:字母表示棋盘水平坐标,而 数字表示棋盘垂直坐标。 输入实例: D4A3A8H1H8 输出数据: 文件camelot.out必须包含单一的一行,以一个正整数表 示选手要实现聚会所需最少的移动次数。 输出实例: 10

穷举法

圆桌骑士问题:
由于问题的规模较少(8X8),国王与骑士的 总个数为64,且国王最多只会与一个骑士结合,没 有必要在中途将国王托付给其他的骑士。因此,我 们可以完全穷举出国王与骑士最终的所有汇聚点, 穷举出与国王可能汇合的所有骑士及其所有可能的 汇合点,其最大穷举次数为8X8X8X8X63,程序 完全可以承受。 为了便于计算和处理,我们需要进行一个预 处理,即将任意两点之间走马字步距离计算出来 (可使用Floyd或宽搜完成)。

穷举法

构造法简介
根据处理对象状态的构造特点,以及不同状态之间的 生成关系,利用简单操作,从当前状态转变为下一个 新的状态,实现所有状态的枚举.

穷举法

构造法简介
program L4;{构造法求N个元素全排列}
const maxn=9; var x:array[1..maxn] of byte; n,i,k,l,r,temp:integer; b:boolean;

begin
write('n=');readln(n); for i:=1 to n do x[i]:=i;

for i:=1 to n do write(x[i]);writeln;{第一个排列}

穷举法

构造法简介
b:=true; while b do begin k:=n-1;{找最靠右的数字变大的位置} while (k>0) and (x[k]>x[k+1]) do dec(k); if k=0 then b:=false{终止} else begin i:=n; while x[k]>x[i] do dec(i); temp:=x[k];x[k]:=x[i];x[i]:=temp;

穷举法

构造法简介
l:=k+1;r:=n; while l<r do begin temp:=x[l];x[l]:=x[r];x[r]:=temp; inc(l);dec(r); end; for i:=1 to n do write(x[i]);writeln; end; end; readln end.

穷举法

上机题
题1 交谈(talking.???)

问题描述: 来自不同国家的4位留学生A,B,C,D在一 起交谈,他们每人只会中、英、法、日4种语言 中的2种,情况是:没有人既能讲日语又能讲法 语;A能讲日语,D不会日语,但A和D能互相 交谈,B不8会英语,但A和C交谈时却要B当翻 译;B,C,D3人想互相交谈,但找不到共同 的语言;只有一种语言3人都会。请编程确定这 四人分别会哪两种语言。

穷举法

上机题
题2 最佳游览线路(travel.???) 问题描述: 某旅游区的街道成网格状。其中东西向的街道都是旅 游街,南北向的街道都是林荫街。由于游客众多,旅 游街被规定为单行道,游客在旅游街上只能从西向东 走,在林荫街上则既可以从南向北走,也可以从北向 南走。 阿龙想到这个旅游区游玩。他的好友阿福给了他一些 建议,用分值表示所有旅游街相邻两个路口间的街道 值得游览的程度,分值是从-100到100的整数,所有 林荫街不打分。所有分值不可能全是负分。

穷举法

上机题
如图是被打过分的某旅游区的街道图。 北 -50 -47 36 -30 -23 西 17 -19 -34 -13 -8 -42 -3 -43 34 -45 南 东

阿龙可以从任何一个路口开始游览,在任何一个路口 结束游览。请你写一个程序,帮助阿龙找一条最佳的 游览线路,使得这条线路的所有分值总和最大。

穷举法

上机题
题3 数塔问题 (numbertap.??? ) 问题描述: 有形如下图所示的数塔,从顶 部出发,在每一结点可以选 择向左走或是向右走,一直 走到底层,要求找出一条路 径,使路径上的数值的和最 接近零。

穷举法

上机题
题4 大整数(number.???)

问题描述: 一个k(1≤k≤80)位的十进制正整数n,我们称其 为大整数。现在的问题是,请你设计一个程序,对于 给出的某一个大整数n,找到满足条件p3+p2+3p≤n 的最大值。 输入数据:输入文件是number.dat。该文件只有一行, 是一个k位的大整数n。行首行末无多余空格。 输出数据:输出文件是number.out。在文件的第一行输 出你所找到的p的最大值。行首行末无多余空格。


推荐相关:

穷举法_图文.ppt

穷举法 - pascal 信息技术奥赛 穷举法... ? ? ? 理解穷举法的思想方法 学会分析建立正确的穷举步骤,归纳穷 举法的穷举技巧 学会优化穷举算法 学会使用穷举法解决...

《用穷举法解决问题》教学设计.doc

《用穷举法解决问题》教学设计 - 《用穷举法解决问题》教学设计 用穷举法解决问题

用穷举法解决问题课件.ppt

穷举法解决问题课件_其它课程_高中教育_教育专区。算法与程序设计 3.2 用穷举法解决问题 算法与程序设计 座位邻近的前后8位同学为一组,并为自己的组取个名字...

用穷举法设计程序教学设计.doc

《用穷举法设计程序》教学设计 《用穷举法设计程序》教学设计执教教师:佛山市第三中

用穷举法设计算法_图文.ppt

算法分析:没有公式直接求出三角形的个数,所以程 序只能采用穷举法,一一验证范围内的数是否能构成 三角形,若是则累计。 穷举法 s=0; for (a=1;a<=n-2;...

解析法,穷举法_图文.ppt

解析法,穷举法 - 一、解析法 问题 ? 现有一根长度为L的铁丝,若想用这根铁丝

穷举法_图文.ppt

穷举法 穷举法 一、引入 实例一:输入绳子的长度 n,将该绳子分成三段,每段的长

C语言穷举法经典例题_图文.ppt

C语言穷举法经典例题_工学_高等教育_教育专区。C语言穷举法经典例题 第3章 程序控制结构 枚举法(穷举法)“笨人之法”: 把所有可能的情况一一测试,筛选出符合 ...

C语言穷举法经典例题_图文.ppt

C语言穷举法经典例题 - 第3章 程序控制结构 枚举法(穷举法) “笨人之法”:

穷举法-VB_图文.ppt

穷举法-VB - 复习解析法 问题:小球从10米处自由落下,每 次弹起的高度是下

用穷举法解决问题_图文.ppt

穷举法解决问题_其它课程_高中教育_教育专区。解析法解决问题步骤 1、问题分析 未知---已知数学表达式 S = (a+b)*h/2 2、编程实现 3.2 用穷举法解决问题...

C语言穷举法经典例题_图文.ppt

C语言穷举法经典例题 - 第3章 程序控制结构 枚举法(穷举法) “笨人之法”:

1穷举法.doc

常用算法穷举法重点:1、穷举法的基本思想 2、利用穷举法设计程序的基本步骤和方

4.2用穷举法设计程序_图文.ppt

4.2用穷举法设计程序 - § 4.2 用穷举法设计程序 课前思考 某个暑假你携

《用穷举法解决问题》教学设计_图文.pdf

《用穷举法解决问题》教学设计 - 《用穷举法解决问题》教学设计 教学分析 1.教学目标 知识与技能:了解什么是穷举法及其特点,以及用穷举法设计算法 的基本过程;...

用穷举法设计算法_图文.ppt

穷举法设计算法 - 用穷举法设计算法 ? 问题1: 有一把锁和一串钥匙(共有10把钥匙), 怎样找出所有开这把锁的钥匙? 用穷举法设计算法 ? 穷举算法的概念: ...

用穷举法解决问题_图文.ppt

穷举法解决问题 - 解析法解决问题步骤 1、问题分析 未知---已知 数学表达式 S = (a+b)*h/2 2、编程实现 3.2 用穷举法解决问题 3.2 用穷举法解决...

穷举法 VB_图文.ppt

穷举法 VB - 登录ftp://192.168.1.211, , 登录 课堂资料”中名字为“ 将“课堂资料”中名字为“穷 举法” 举法”的文件夹下载到自己的 电脑上。 电脑...

基础算法(一)穷举法.doc

基础算法(一)穷举法 - 基础算法( 基础算法(一)穷举法 穷举法的基本思想: 穷举法的基本思想:从可能的解集合中一一穷举各元素,用题目给定的检验 条件判定哪些是...

穷举法_论文.pdf

穷举法 - 穷举法,顾名思义,就是把各种可能性都列举出来,找到答案。... 穷举法_专业资料。穷举法,顾名思义,就是把各种可能性都列举出来,找到答案。 ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com