当前位置:首页 >> 其它 >>

noip讲义6-回溯法


回溯搜索
回溯是一种模拟人类思维过程的算法思想。它的基本方 法是:按照深度优先的顺序向下一层扩展结点;扩展到某一 层时,若已无法继续扩展且仍未找到解,则退回到父结点, 从父结点的下一个分支开始,按同样的策略继续扩展……, 直到找到问题的解或证明无解。

四皇后问题的递归实现
const n=4; var

皇后序号 procedure try(k:integer); var i:integer; 因为从第i begin if( k=n+1 ) then 个皇后到第 begin print; ( exit )

i,j,k:integer; x:array[1..n] of integer;
{保存第i个皇后的列号} function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if(x[i]=x[k])or(abs(x[i]-x[k])=abs(i-k)) then place:=false; end; procedure print; var i:integer; begin for i:=1 to n do write(x[i]:4); writeln; end;

end; for i:=( 1 to n )do begin ( x[k]:=i ); if place(k) then( try(k+1) ); end; end ; 摆放下一个皇后 begin try(1);{摆放第一个皇后} end.

i+1个皇后 的摆放方法 是相同的, 所以可以用 递归的方法.

数字排列问题的递归实现
procedure try(k:integer); var var i :integer; i,k,n:integer; begin x:array[1..9] of integer; if( k>n )then begin function place(k:integer):boolean; print; var i:integer; exit; begin end; place:=true; for i:=1 to n do for i:=1 to k-1 do begin if(x[i]=x[k] )then ( x[k]:=i); begin if( place(k) )then try(k+1) place:=false; end break end; end ; begin end; readln(n); procedure print; try(1); var i:integer; end. begin for i:=1 to n do write(x[i],' '); writeln; end;

骑士游历问题的递归实现
const x:array[1..4,1..2] of integer =((1,2),(2,1),(2,-1),(1,-2)); var n,m:integer; a:array[1..30,1..2] of integer; procedure print(ii:integer); var i:integer; begin for i:=1 to ii-1 do write(a[i,1],',',a[i,2],'->'); writeln(n,',',m); ( halt ) end;

procedure try(i:integer); var j:integer; begin for j:=1 to 4 do if (a[i-1,1]+x[j,1]<=n) and (a[i-1,2]+x[j,2]>=0) and (a[i-1,2]+x[j,2]<=m) then begin a[i,1]:=a[i-1,1]+x[j,1]; a[i,2]:=a[i-1,2]+x[j,2]; if (a[i,1]=n)and(a[i,2]=m) then( print(i)) else( try(i+1) ); ( a[i,1]:=0; a[i,2]:=0 ) end; end; begin read(n,m); try(2); writeln(‘NO’); end.

回溯法的递归算法框架:
procedure run(当前状态); var i:integer; begin if 当前状态为目标状态 then begin if 当前状态为最佳目标状态 then 记下最优结果; exit; end; for i←算符最小值 to 算符最大值 do begin 算符i作用于当前状态,扩展出一个子状态; if(子状态满足约束条件)and(子状态满足最优性要求) then run(子状态); end; end;

二种方式的区别:
1、递归方式实现简单,非递归方式比较复杂。 2、递归方式需要利用栈空间,如果搜索量过大,可能造 成栈溢出,所以在栈空间无法满足的情况下,选用非递归 方式实现较好。

回溯法的剪枝
当叶子结点D已找到了一个值为30的最短路径, 回溯搜索的进程可以看作是从树根出发,遍历一棵搜索树 这时在搜索到G(50)、H(35)、J(30)时,其路径长度 的过程.所谓剪枝,就是通过某种判断条件,避免一些不必要 已大于或等于了当时最优值,因此再搜索下去毫无 的遍历过程,形象地说,就是剪去了搜索树中的某些“枝 意义,其下的结点都可以剪除. 条”. 下图是一个求最短路径扩展的搜索树,描述了剪枝的过 程.
A(0) B(10) C(20)

I(25)

G(50)

H(35)

J(30)

D(30) E(35) F(40)

测试1、售货员的难题
某乡有n个村庄(1<n<40),有一个售货员,他要到各个村庄去售货,各村 庄之间的路程s(0<s<1000)是已知的,且A村到B村与B村到A村的路大多不同。 为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假 设商店所在的村庄为1,他不知道选择什么样的路线才能使所走的路程最短。 请你帮他选择一条最短的路。
输入:村庄数n和各村之间的路程(均是整数)。 输出:最短的路程。 样例输入: 3 02l {村庄数} {村庄1到各村的路程}

1 0 2 {村庄2到各村的路程} 2 1 0 {村庄3到各村的路程} 样例输出:

3

算法分析: 题目给定的村庄数不多(0<40),所以可以用回溯的方 法,从起点出发找出所有经过其他各村庄的回路,计算其中 的最短路程。用一个过程road(step,line:byte)来描述走 的状况,其中step是当前已到过的村庄数、line是当前所在 的 村 庄 。 如 果 step=n, 接 下 去 只 能 回 起 点 了 , 此 时 看 第 line个村庄到起点的路程加上已走的总路程,如果它比最小 值还小则替换最小值。如果step还小于n,那么将还没有到 过的村庄一个一个地试过去,再调用下一步road(step+1, 新到的村庄号)。

procedure road(step,line:byte); var i,j,k:byte; begin if( step=n )then begin if m+a[line,1]<min 满足最优 then min:=m+a[line,1]; 性要求 exit; end; for i:=2 to n do if(i<>line)and(bj[i])then begin begin m:=m+a[line,i]; readln(n); for i:=1 to n do bj[line]:=false; for j:=1 to do read(a[i,j]); 剪枝 if m<min fillchar(bj,sizeof(bj),true); then(road(step+1,i) ); min:=99999999; m:=m-a[line,i]; 恢复其递归前的值 m:=0; ( bj[line]:=true ); road(1,1); end; writeln(min); end; end.

var a:array[1..40,1..40] of integer; n,i,j:integer; min,m:longint; bj:array[1..40] of boolean;

测试2、计算折分方案
给定一个正整数N,假设 0<A1<=A2<=A3...<=As 满足 A1+A2+A3+...+As=N,那么我们称序列A1 A2……As为N的 一个拆分。现在要求N的拆分数目。(n<65) 例如:当N= 6 时 6=1+1+1+1+1+1 =1+1+1+1+2 =1+1+1+3 =1+1+2+2 =1+1+4 =1+2+3 =1+5 =2+2+2 =2+4 =3+3 所以 6 的整数拆分个数为 10 。

var a:array[1..100] of integer; total,n:integer; procedure output(s:integer); {s为一个拆分的长度} var i:integer; begin write(n,'=',a[1]:3); for i:=2 to s do write('+',a[i]:3); writeln; end;

procedure dfs(d,low,rest:integer); var i:integer; begin low为当前a[d]的下界,rest为还 if( rest=0 ) then 剩下多少要拆分. begin ( inc(total) ); output(d-1); exit; end; if low>rest then( exit );{剪枝} for i:=low to rest do {枚举a[d]的所有可能值} begin a[d]:=i; if a[d]<>n then dfs(d+1,i,rest-i ); end; end; begin read(n); dfs( 1,1,n ); writeln('Total=',total); end.

测试3、数的划分( 01年复赛) 问题描述: 将整数n分成k份,且每份不能为空,任意两种分法不能相同 (不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的: 1,1,5 ; 1,5,1 ; 5,1,1 ; 问有多少种不同的分法。 输入:n,k ( 6<n<=200, 2<=k<=6 )

输出:一个整数,即不同的分法。
样例 输入:7 3

输出:4
{四种分法为:1,1,5 ;1,2,4 ;1,3,3 ;2,2,3;}

分析:按份数递增的顺序拆分,且被拆分的整数按递 增顺序排列(避免重复)。 7=1+6 =2+5 =3+4 7=1+1+5 =1+2+4 第一个数要小于等于 7 div 3

=1+3+3
7=2+2+3

第二个数要小于等于 6 div 2
第二个数要小于等于 5 div 2

var begin n,k,i:integer; read(n,k); tot:longint; a:array[1..6] of integer; tot:=0; procedure sum( kx:integer); for i:=1 to n div k do var kx为整数序号 m , L:integer; 按递增要求 begin begin 枚举n拆成 if kx=k then begin a[1]:=i; 两份的所有 可能方案 tot:=tot+1; exit; 已将n拆成k份 a[2]:=n-i; end; L:=a[kx]; sum(2); for m:=a[kx-1] to L div (k-kx+1) do 从第二个 end; 数出发递 begin 按递增要求穷 归拆分 a[kx]:=m; writeln(tot); 举a[kx] 拆成 a[kx+1]:=L-m; 两份的所有可 sum(kx+1); end. 能方案 end; end;

测试4、选数( 01年复赛)
已 知 n(1<=n<=20) 个 整 数 x1,x2,…,xn(1<=xi<=5000000), 以 及一个整数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 x1,x2,…,xn 输出:一个整数(满足条件的组合个数) 输入输出样例 输入: 43 3 7 12 19 输出: 1

判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一 个素数a(a<=sqrt(P))是P的约数,如果不存在,该数就为素数。 由于在此题中1<=xi<=5000000,n<=20,所以要判断的数P不会 超过100000000,sqrt(p)<=10000,因此,为了加快速度,我们可 以先将2…10000之间的素数保存到一个数组里(共1229个),这样 速度估计将提高5~6倍。

var
n,k: integer; ans,i: longint;

x: array[1 .. 20] of longint;
p: array[1 .. 1229] of integer; function ss( i:longint ):boolean;

var
begin

判断i是否是素数

j:longint;

j:=2;
while i mod j<>0 do j:=j+1; if j>sqrt(i) then ss:=true else ss:=false; end;

procedure create; 建立10000以 var s:integer; 内的素数集合 i:longint; begin s:=0; for i:=2 to 10000 do if ss ( i ) then begin s:=s+1; p[s]:=i; 判断k个整数之和是 end; 否为素数 end; function fit( sum:longint ):boolean; var max,m:integer; begin max:=trunc( sqrt(sum) )+1; m:=1; while ( sum mod p[m]<>0 ) and ( p[m]<max ) do m:=m+1; if p[m]>=max then fit:=true else fit:=false; end;

目前组合和为all,还 procedure solve(left,now,all:longint); 需从第x ..x 中选出 now n 如余下的数已不足 begin left个数。 left个,则回溯 if ( left > n-now+1 ) then exit;{剪枝} if ( left=0 ) then begin if fit(all) then ans:=ans+1; exit; end; 当前组合不选xnow solve( left , now+1 , all ); solve( left-1,now+1,all+x[now] ); 当前组合选取xnow end; begin create;{建立10000以内的素数表} readln(n,k); for i:=1 to n do read(x[i]); ans:=0; solve( k,1,0 ); writeln(ans); end.

测试5、合理排列(04年江苏)
问题描述: 由m个A,n个B组成若干个排列,从某个排列的位置1开始数,数到 任意位置时都能保证A的个数不少于B的个数,则称该排列为合理排列。 如当m=2,n=2时,排列有:AABB(合理) ABAB(合理) ABBA (不合理)BBAA(不合理),合理排列有2种。 又如当m=3,n=2时合理排列有5种:AAABB、AABAB、AABBA、 ABAAB、ABABA 输入输出: 输入只有一行两个整数m,n(1<=n<=m<=12)(用空格分隔) 输出一个整数表示所有的合理排列数。 样例: 10.in 32 10.out 5

var a,b,n,w:integer;{w表示前k个字符中'A'的个数与'B'的个数的差} s:longint;{合理排列数} procedure try(k:integer);{k表示目前确定第K个字符} begin if k=n+1 then begin s:=s+1; exit; end; if a>0 then begin {放‘A’的情况} a:=a-1; w:=w+1; try(k+1); w:=w-1; a:=a+1; end; if (w>0)and(b>0) then begin {放‘B’的情况} b:=b-1; w:=w-1; try(k+1); w:=w+1; b:=b+1; end; end; begin readln(a,b); n:=a+b; {排列的长度} a:=a-1; w:=1; {第1个字符必定为'A'} s:=0; try(2); writeln(s); end.

测试6、构造字串 生成长度为n的字串,其字符从26个英文字母的前 p(p≤26)个字母中选取,使得没有相邻的子序列相等。例 如p=3,n=5时 ‘a b c b a’满足条件 ‘a b c b c’不满足条件 输入:n,p

输出:所有满足条件的字串

copy(s,length(s)-i+1,i)<>copy(s,length(s)-2*i+1,i)

1<= i<=at div 2
s=‘abcba ‘
i=1时,a<>b

s=‘abcbc ‘
i=1时,c<>b

i=2时,ba<>bc

i=2时,bc=bc

var n,p,L:integer; begin{主程序} t:longint; ed:char;{可选字母集中的最大字母} readln(n,p); ed:=chr( ord('a') + p - 1); s:string;{满足条件的字串} s:=''; tl:=0; procedure solve(at:integer); solve(1); var ch:char; i:integer; 待扩展的字母序号at writeln('Total=',tl); begin end. if at=n+1 then begin writeln(s); inc(t); exit end; 搜索范围:'a'.. chr(ord('a')+p-1) for ch:='a' to ed do begin 约束条件:当前字串没有相邻子串相等的情况 s:=s+ch; L:=length(s); i:=1;{i是子串长度} while(i<=at div 2)and(copy(s,L-i+1,i)<>copy(s,L-2*i+1,i)) do inc(i); if i>at div 2 then solve(at+1); delete(s,length(s),1); 递归扩展下一个字母 end; end;

测试7、马拦过河卒(02年复赛)
【问题描述】
棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以 向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所 有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为不超过20的整数),同 样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点 的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。 【输入】 一行四个数据,分别表示B点坐标和马的坐标。 【输出】

一个数据,表示所有的路径条数。
【样例】 输入:6 6 3 3

输出:6

const dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2); dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1); var n,m,x,y,i,j: byte; g:array[0..20,0..20] of 0..1; c:longint; procedure sol(x,y:integer); x,y为当前马所 var i:integer; 在的位置 begin if (x=n) and (y=m) then begin c:=c+1; exit; 目标 回溯 end; if (y<m) and (g[x,y+1]=0) then sol(x,y+1); 向右走 if (x<n ) and (g[x+1,y]=0) then sol(x+1,y); end; 向下走 begin readln(n,m,x,y); g[x,y] := 1; for i:=1 to 8 do if (x+dx[i]>=0) and (x+dx[i]<=n) and (y+dy[i]>=0) and (y+dy[i]<=m) then g[x+dx[i],y+dy[i]]:=1; sol(0,0); writeln(c); 计算马的控制点 end.

测试8、01字符串问题
问题描述:

输出仅由0和1组成的长度为n的字符串,并且其中不可含有三个 连续的相同字串。
输入:字符串长度n(n<=40) 输出:所有满足条件的字符串的个数。 样例输入: 2 样例输出: 4

var n : integer; lev : integer;{位指针} tot : longint; list : array[1..50] of integer;{01序列} function right(lev:integer):boolean;{有没有三个连续的相同子串} var p,q,r,x,y,z : integer; begin Z Y Z Y Z Y X X X x:=lev; y:=lev-1; z:=lev-2; while z>0 do begin R R R Q Q Q Q P P P R p:=x;q:=y;r:=z; while (r<y) and (list[p]=list[q]) and (list[q]=list[r]) do begin inc(p) ; inc(q) ; inc(r); end; if r=y then begin right:=false ; exit; end; x:=x-1;y:=y-2;z:=z-3 end; right:=true; end;

0 1 0 0 1 0 0 1 0

P

procedure search(lev:integer); begin if lev>n then begin tot:=tot+2; exit; end; list[lev]:=0;{先填0} if right(lev) then search(lev+1); list[lev]:=1;{后填1} if right(lev) then search(lev+1); end; begin readln(n); list[1]:=0;{第一位为0} lev:=1; tot:=0; search(2); writeln(tot); end.

序列的对称性: 011001 100110

测试9.错排问题(02年初赛)
在书架上放有编号为1 ,2 ,…,n的n本书。现将 n本书全部取下然后再放回去,当放回去时要求每本书 都不能放在原来的位置上。 例如:n = 3时: 原来位置为:1 2 3 放回去时只能为:3 1 2 或 2 3 1 这两种 问题:求当n = 5时满足以上条件的放法共有多少 种?

var a:array[1..50] of integer; s:set of 1..50; n,num:integer; procedure print; var i:integer; begin inc(num); write('No.',num,' '); for i:=1 to n do write(a[i]:4); writeln; end; procedure cuopai(k:integer); var i:integer; begin if (k=n+1)then begin print; exit; end;

for i:=1 to n do if not(i in s)and ( i<>k ) then begin a[k]:=i; s:=s+[i]; ( cuopai(k+1) ) ; a[k]:=0; ( s:=s-[i] ); end; end; begin readln(n); ( s:=[] ); num:=0; cuopai(1); writeln('Total=',num); end.

测试10.排队购票
公园门票每张5角,如果有2n个人排队购票,每 人一张,并且其中一半人恰有5角钱,另一半人恰有 1元钱,而票房无零钱可找,那么有多少种方法将这 2n个人排成一列,顺次购票,使得不至于因票房无零 钱可找而耽误时间?
2n个0与1组成的数,从最左边算起,任何位置0的 个数不得小于1的个数,这样的排列有多少种?

const maxn=10; if( n0>n1 )and(n0<n)then var begin a:array[1..maxn*2] of integer; for i:=0 to 1 do n,num:integer; begin a[k]:=i; procedure try(k,n0,n1:integer); if i=0 then try(k+1,n0+1,n1) var i,j:integer; else try(k+1,n0,n1+1); begin end; if( k=2*n+1 )then end; begin n0=n )then if ( inc(num); begin write('No.',num,' '); a[k]:=1; for i:=1 to 2*n do try(k+1,n0,n1+1); write(a[i]:2); end; writeln; end; ( exit ); begin end; fillchar(a,sizeof(a),0); if(n0=n1)and(n0<n)then readln(n); begin num:=0; a[k]:=0; try(1,0,0); try( k+1,n0+1,n1 ); end. end; n0是有5角钱的人数,n1是有1元钱的人数

测试11

、棋盘覆盖

有边长为N(偶数)的正方形,用N*N/2个长为2、宽 为1的长方形将它全部覆盖,请找出所有覆盖方法。如N=4 时的一种覆盖方法及输出格式如下所示。

1 1

2 3

2 3

4 4

输出:(数字为长方形编号)

1224
1334

5
5

6
7

6
7

8
8

5668
5778

var n:integer; t:longint; a:array[1..10,1..10] of integer; procedure print; var i,j:integer; begin ( inc(t) ); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:5); writeln; end; end; procedure try(i:integer); var j,k:integer; begin j:=0; repeat{找到第一个未覆盖的空格(j,k)} j:=j+1; k:=1; while(k<=n)and( a[j,k]>0 ) do inc(k); until k<=n; a[j,k]:=i;

if (j<n)and(a[j+1,k]=0)then begin a[j+1,k]:=i; if i*2<n*n then try(i+1) else print; ( a[j+1,k]:=0 ); end; if (k<n)and(a[j,k+1]=0)then begin a[j,k+1]:=i; if i*2<n*n then try(i+1) else print; ( a[j,k+1]:=0 ); end; ( a[j,k]:=0 ); end; begin readln(n); try(1); write(t); end.

测试12、组合的输出
【问题描述】 排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元 素(不分顺序且r<=n),我们可以简单地将n个元素理解为自然数1,2,…, n,从中任取r个数。 现要求你输出所有的组合。 例如n=5,r=3,所有组合为: 123 124 125 134 135 145 234 235 245 345 【输入】 一行两个自然数n、r(1<n<21,1<=r<=n)。 【输出】 所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列, 每个元素占三个字符的位置,所有的组合也按字典顺序。

const max=20; var a:array[0..max]of integer; n,r:1..max; 当前所选元素最小为前一个元素加1,最 procedure compages (k:integer); 大为n-(r-k),因为后面还有(r-k)个元素 var i,j:integer; 要选取,至少为每次选取留一个. begin for i:=( a[k-1]+1 to n-(r-k) )do begin a[k]:=i; if( k=r )then begin for j:=1 to r do write(a[j]:3); writeln; end else( compages(k+1) ); end; end; begin readln(n,r); compages(1); {从第一个元素开始选取组合数} end.


相关文章:
noip考前狂背
noip讲义6-回溯法 38页 免费 信息学奥赛试题精选33题(附... 53页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...
noip训练题
noip讲义6-回溯法 38页 免费 noip2008初赛集训一 18页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP名校讲义
NOIP名校讲义_学科竞赛_高中教育_教育专区。NOIP学习...数组存储二进制数的各个数位是一种比较好的方 法...[i,6]/5;{求平均分} end; {输出成绩表} ...
NOIP2009复习资料
By 摇杆大牛 6 宜昌一中 NOIP2008 复习资料第六部分 搜索 回溯法 算法框架 procedure run(当前状态) ; var i:integer; begin if 当前状态为边界 then begin ...
回溯算法的一些例题
回溯算法 搜索与回溯是计算机解题中常用的算法, 很多问题无法根据某种确定的计算...noip讲义6-回溯法 38页 5下载券 第4章-贪心算法-习题 38页 1下载券 ©...
NOIP算法入门——回溯免费学习_高中其他_教学视频大全
理解回溯算法的基本概念,并通过几个案例的讲解,学习回溯的基本应用。视频教程,NOIer全套教学,在线学习高中其他课程,NOIP算法入门——回溯视频下载
名校noip讲义-背包问题思路
名校noip讲义-背包问题思路_学科竞赛_高中教育_教育专区。名校noip讲义-背包问题思路背包问题思路 [问题描述] 在 M 件物品取出若干件放在空间为 W 的背包里,每件...
NOIP2000_2010普及组初赛-完善程序-题目
题目利用回溯法求解。棋盘行标号为 0~n-1,列标号为 0~m-1。 var n, m,...(n:integer); var 第 6 页 2011-09-24 noip2000-2010 普及组初赛-完善...
NOIP2011普及组初赛试题及答案C++版
: A.回溯法 B.枚举法 C.动态规划 D.贪心 18.1956 年( )手语肖克利、巴丁...NOIP2011 初赛 普及组 C++ 4 return 0; } 输入: 11 4 5 6 6 4 3 3 ...
NOIP C
6页 5财富值 2008年NOIP(C语言)提高组初... 11页 5财富值 noip 2003 c ...题目利用回溯法求解。棋盘行标号为 0~n-1,列标号为 0~m-1。 #include <...
更多相关标签: