例3：输入一串以‘!’结束的字符，按逆序输出。

例3：输入一串以‘!’结束的字符，按逆序输出。
program p4(input，output)； procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end； begin {主程序} rever； end．运行：输入 hey! 输出 !yeh。程序中，c 是过程rever的局部变量。每一次递归调用，都要为局部变量重新分配单元，因此各层的变量c实际上是不同的量，它们分别用于保存执行本层调用时的输入值。

hey! c=‘!’ c=‘y’ c=‘e’ c=‘h’ procedure rever； var c：char； begin
read(c)； if c<>'!' then rever; write(c)； end； c=‘y’ procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end； c=‘e’ procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end； c=‘h’ procedure rever； var c：char； begin read(c)； if c<>'!' then rever; write(c)； end；

程序中的递归过程图解如下： procedure num(x: integer） begin if x=5 then a:=10 else begin num(x+1); a:=a+2 end end; 整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。

回溯

计算机求解的过程在状态空间寻找机内解, 可以看成是从初始状态出发,搜索目标状态(解所在的状态)的过程。状态空间初始状态搜索目标状态搜索的过程可描述为：S0S1…Sn，其中S0为初态，Sn为终态。或者说ψ(S0)且φ(Sn)，这里ψ称为初始条件，φ称为终止条件。

求解是状态空间的搜索求解的过程可以描述为对状态空间的搜索 … … … … … … … …… ……
S0 S0 其中S0为初始状态，不妨设Sni为终止状态 … S11 S12 S1k … … … … … … …… …… Sn1 Sni Sni Snm 问题求解就是通过搜索，寻找出一条从初始状态S0到终止状态Sni的路径。

几种搜索方法状态空间的搜索实际上是一种树/DAG（Directed Acyclic Graph ）的搜索，常用的方法有：广度优先搜索
深度优先搜索启发式搜索从初始状态开始，逐层地进行搜索。从初始状态开始，逐个分枝地进行搜索。从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。

三种搜索的优劣之处一般来说，三种搜索方法各有优劣之处：广度优先搜索和深度优先搜索优点：一定能找到解；缺点：时间复杂性大。
启发式搜索优点：一般来说能较快地找到解，即其时间复杂性小；缺点：需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。

回溯法当需要找出问题的解集，或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。在问题的解空间树中，回溯法按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的算法框架问题的解空间应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解。通常将解空间组织成树或图的形式。问题的解向量：回溯法希望一个问题的解，能够表示成一个n元式(x1,x2,…,xn)的形式。显约束：对分量xi的取值限定隐约束：为满足问题的解，而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。例如，对于有n种可选物品的0-1背包问题，其解空间由长度为n的0-1向量组成。 n=3时的0-1背包问题用完全二叉树表示的解空间

回溯法的基本思想扩展结点:一个正在产生儿子的结点活结点:一个自身已生成但其儿子还没有全部生成的节点死结点:一个所有儿子已经产生的结点
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。

基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前扩展结点，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

可重复的全排列假设是由1-3组成的3位数 program expl; var i,j,k:integer; begin
for i:=1 to 3 do for j:=1 to 3 do for k:=1 to 3 do writeln(i,' ',j,' ',k); end.

如果是5位呢？更多位呢？不定位呢？

试一试，如果n位，n<6,如何改动？如果要求输出不重复的全排列呢？ program expl_dg;
var a:array[1..10] of integer; procedure print; var i:integer; begin for i:=1 to 3 do write(a[i],' '); writeln; end; procedure work(x:integer); if x>3 then begin print ;exit;end; a[x]:=i; work(x+1); work(1); end. 试一试，如果n位，n<6,如何改动？如果要求输出不重复的全排列呢？

剪枝 program expl_dg; var a:array[1..10] of integer; n:integer;
procedure print; var i:integer; begin for i:=1 to n do write(a[i],' '); writeln; end; function try(x,i:integer):boolean; var j:integer; try:=true; for j:=1 to x-1 do if a[j]=i then begin try:=false;break;end; procedure work(x:integer); if x>n then begin print;exit;end; for i:=1 to n do if try(x,i)=true then a[x]:=i; work(x+1); readln(n); work(1); end. 剪枝

关于回溯法搜索的递归程序框架全排列算法的递归解法为例做个介绍：
const n=5; var a:array [1..n] of integer; {记录搜索的解} e:array [1..n] of boolean; {标记数组用于记录i是否已经用过} {初始状态都是false} procedure print; var i:integer; begin for i:=1 to n do write(a[i],' '); end; procedure search(deep:integer); {deep是搜索深度} var i:integer; begin if deep>n then begin print; {输出结果} exit; {退出本层，回溯} end; for i:=1 to n do if e[i]=false then begin {如果i没有用过,限定条件} e[i]:=true; {标记为用过i} a[deep]:=i; {记录该位置的元素为i} search(deep+1); {搜索deep+1个位置上的元素} e[i]:=false; {回溯之后取消i元素的已用标记} end; end; 在很多题目中，"限定条件"需要用邻接矩阵等数据表示，这个"限定条件"就是输出结果中需要满足的条件，具体的可以根据题目来修改。

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

四色问题有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出一种符合条件的填色方案。地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的。返回到题目列表

四色问题输入输出 1 2 3 4 5 6 7 返回到题目列表

四色问题要得到一种可行的填色方案，比较直接的做法就是一个省一个省的填色，在填色的过程中去检查是否和周围省份的颜色存在冲突。
从第一个省份开始，对每个省份依次尝试四种颜色，判断当然选择的颜色是否和相邻的省份相同。若都不相同，则将此省份填上当前的颜色。若存在相同，则取下一种颜色继续尝试。若四种颜色都不能填上，则退回上一个省份并选择下一种颜色继续尝试。当最后一个省份也被填色后就找到一组可行解。返回到题目列表

四色问题 procedure search(m: integer); // 递归搜索第m个省份 begin
n块，m代表当前在填第几块 procedure search(m: integer); // 递归搜索第m个省份 begin if m > n then // 是否所有省份都已经填色 write(s[1]); // 已全部填色，输出结果，终止程序 for j := 2 to n do write(' ', s[j]); writeln; halt end else // 还未全部填色 for j := 1 to 4 do // 依次用四种颜色对当前省份填色 begin if 可以 then {同相邻的块没有色彩冲突} begin // 没有冲突 s[m] := j; // 记录当前省份颜色 search(m + 1); // 递归检查下一个省份 end;

迷宫问题以一个 m*n的长方阵表示迷宫，0和1 分别表示迷宫中的通路和障碍（如下图所示）。设计一个程序，对任意设定的迷宫，如果只能按上下左右四个方向移动，求出一条从入口到出口的通路。或得出没有通路的结论。在方阵中，允许运动的方向为上下左右，因此，对于每个状态，都有四个方向可以扩展搜索，为了简化程序，我们可以设计增量数组描述不同的运动方向。另外，为了回避边沿位置移动方向的限制（如上边沿的位置不能再向上移动等），可以对方阵进行扩充，增加一圈且有障碍。如图所示。

const maxm=10; maxn=10; const dx:array[1..4] of integer=(-1,1,0,0); { 上下左右方向 } dy:array[1..4] of integer=(0,0,-1,1); type address=record x,y:integer; end; var a:array[0..maxm+1,0..maxn+1] of integer; step:array[1..maxm*maxn] of address; m,n,x0,y0,x1,y1:integer; procedure init; var i,j:integer; begin readln(m,n); for i:=0 to m+1 do for j:=0 to n+1 do a[i,j]:=1; for i:=1 to m do for j:=1 to n do read(a[i,j]); readln(x0,y0); readln(x1,y1); step[1].x:=x0; step[1].y:=y0; procedure print(steps:integer); var i:integer; for i:=1 to steps-1 do write('(',step[i].x,',',step[i].y,')-->'); writeln('(',step[steps].x,',',step[steps].y,')'); halt; procedure try(i:integer); var j,x,y:integer; begin for j:=1 to 4 do x:=step[i-1].x+dx[j]; y:=step[i-1].y+dy[j]; if a[x,y]=0 then step[i].x:=x; step[i].y:=y; a[x,y]:=-1; if (x=x1) and (y=y1) then print(i) else try(i+1); a[x,y]:=0; end; init; a[x0,y0]:=1;try(2); end.

N皇后问题 [问题描述] 在n×n的国际象棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个,要使任何一个皇后都不能吃掉另一个，需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后。求放置方法. 如:n=4时,有以下2种放置方法. * * 输出：

n皇后问题返回到题目列表

n皇后问题的解空间就应该是1～n全排列的一部分。解空间的长度是n。
控制策略则是当前皇后与前面所有的皇后都不同列和不同对角线。返回到题目列表

x:array[1..n] of integer; a:array[1..n] of boolean;
var x:array[1..n] of integer; a:array[1..n] of boolean; {列控制标志：true：可以放，false：不能放} b:array[2..2*n] of boolean; {左上右下方斜线控制标志，true：可以放，false：不能放} c:array[1-n..n-1]of boolean; {左下右上方斜线控制标志，true：可以放，false：不能放} 初始时： fillchar(x,sizeof(x),0); fillchar(a,sizeof(a),true); fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); 1 1 *1 2 1 3 1 4 2 1 2 2 2 3 *2 4 *3 1 3 2 3 3 3 4 4 1 4 2 *4 3 4 4

procedure try(i:integer);
var j:integer; begin if i=n+1 then print else for j:=1 to n do if a[j] and b[i+j] and c[i-j] then begin x[i]:=j; a[j]:=false; {列控制标志} b[i+j]:=false; {左上右下方斜线控制标志} c[i-j]:=false; {左下右上方斜线控制标志} try(i+1); {如果不能递归进行，既a[j] and b[i+j] and c[i-j]=false：无法放置i+1个皇后，说明当前皇后i放置不正确，要回溯，消除标志} a[j]:=true; b[i+j]:=true; c[i-j]:=true end; try(1) end.

四皇后问题的递归实现皇后序号 procedure try(k:integer); var i:integer; begin if( ) then begin print; ( ) end; for i:=( )do begin ( ); if place(k) then( ); end; end ; begin try(1);{摆放第一个皇后} end. const n=４; var 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; k=n+1 因为从第i个皇后到第i+1个皇后的摆放方法是相同的,所以可以用递归的方法. exit 1 to n x[k]:=i try(k+1) 摆放下一个皇后

跳马问题在n×m棋盘上有一中国象棋中的马：请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。马走日字；
马只能往右走。请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。返回到题目列表

跳马问题输入：9 5 输出： (1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5) 返回到题目列表

跳马问题马走日字，当马一开始在黄点时，它下一步可以到达的点有以下的八个，但由于题目规定了只能往右走的限制，所以它只能走到四个绿色点之一。

跳马问题当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。 A A2 A1

跳马问题当到达A1点后，又有三条线路可以选择，于是再任意选择一条，到达B1。从B1再出发，又有两条线路可以选择，先选一条，到达C1。

跳马问题从C1出发，可以有三条路径，选择D1。但到了D1以后，我们无路可走且D1也不是最终目标点，因此，选择D1是错误的，我们退回C1重新选择D2。同样D2也是错误的。再回到C1选择D3。D3只可以到E1，但E1也是错误的。返回D3后，没有其他选择，说明D3也是错误的，再回到C1。此时C1不再有其他选择，故C1也是错误的，退回B1，选择C2进行尝试。 B3 D3 B2 C2 D2 A2 C1 E1 A1 B1 A D1

跳马问题从C2出发，有四条路径可以选择，选择D4，从D4出发又有两条路径，选择E1错误，返回D4选择E2，从E2出发有两条路径，先选择F1错误，返回E2选择B，而B恰好是我们要到达的目标点，至此，一条路径查找成功。 B B3 B2 C2 E2 A2 A1 E1 B1 A D4 F1

跳马问题从上面的分析我们可以得知：在无法确定走哪条线路的时候，任选一条线路进行尝试；
当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试。

为了描述路径，我们最直接的方法就是记录路径上所有点的坐标。但比较繁琐。
如果我对马可以走到的四个点都编上号（方向），那么我们很容易得到每一个方向上两个坐标和原位置的关系。同时，四个方向都有了编号，那么在选择路径的时候也就可以不采用任选的方式了，只需按照编号依次尝试就可以了。

在使用增量数组后，只要知道方向t，下一步的位置就是(x+dx[t], y+dy[t])。
1 2 3 4 若马所处的位置为(x,y)，则其下一步可以到达的四个位置分别是(x+1, y-2)，(x+2, y-1)，(x+2, y+1)，(x+1, y+2)。在使用增量数组后，只要知道方向t，下一步的位置就是(x+dx[t], y+dy[t])。增量数组： dx = (1, 2, 2, 1) dy = (-2, -1, 1, 2)

为了判断棋子是否落在棋盘上，我们还必须知道当前棋子（扩展节点）的位置信息。而用一系列的方向来表示就比较麻烦，因此，我们另外使用两个变量来保存当前棋子的坐标。但这时千万要注意的是一定要在回溯的时候，修改当前棋子的坐标。跳马问题的解空间是从左下角到右上角的所有路径。解空间的长度是所有路径中最长的路径的长度。解空间的组织形式是一棵四叉树，一个可行的解就是从根节点到叶子节点的一条路径。控制策略则是马必须在棋盘内。

分析： x:array[1..4,1..2]of integer= ((1,-2),(2,-1),(2,1),(1,2));
1、马跳的方向： x:array[1..4,1..2]of integer= ((1,-2),(2,-1),(2,1),(1,2)); 4个方向横向和纵向的增量。 2、记录马经过的位置坐标 a:array[1..16,1..2]of integer; 第i步所在的位置，1：横坐标 2：纵坐标 3、马的当前位置：（a[I,1],a[I,2]）下一个位置可能是： (a[I,1]+x[j,1],a[I,2]+x[j,2]) 1<=j<=4 4、目标：a[I,1]=n;a[I,2]=m;

const maxx=15; maxy=15; x:array[1..4,1..2]of integer=((1,-2),(2,-1),(2,1),(1,2)); {4个方向} var n,m,t:integer; a:array[1..maxx+1,1..2]of integer;{记录走的路径坐标} procedure print(i:integer); var j:integer; begin inc(t); write(t,':'); for j:=1 to i do write('(',a[j,1],' ',a[j,2],')'); writeln; end;

procedure try(i:integer); {搜索到当前第i个点}
var j:integer; begin if (a[i,1]=n) and (a[i,2]=m) then print(i); for j:=1 to 4 do if (a[i,1]+x[j,1]>=0)and(a[i,1]+x[j,1]<=n) and(a[i,2]+x[j,2]>=0)and(a[i,2]+x[j,2]<=m){判界} then begin a[i+1,1]:=a[i,1]+x[j,1]; a[i+1,2]:=a[i,2]+x[j,2]; try(i+1); end; assign(output,'house1.out'); rewrite(output); readln(n,m); t:=0; a[1,1]:=0;{起始位置作为第1个点,x,y为0} a[1,2]:=0; try(1); close(output); end.

Best:最短路线，a：临时得到的一个路线。Min：最少步。 procedure try(i:integer); {搜索到当前第i个点}
var j:integer; begin if ((a[i,1]=n) and (a[i,2]=m))and(i<min) then begin min:=i;best:=a;exit;end; {记下当前最短路径和最少步数} if ((a[i,1]<>n) or (a[i,2]<>m))and(i>=min) then exit; {剪枝优化} for j:=1 to 4 do if (a[i,1]+x[j,1]>=0)and(a[i,1]+x[j,1]<=n) and(a[i,2]+x[j,2]>=0)and(a[i,2]+x[j,2]<=m) then begin a[i+1,1]:=a[i,1]+x[j,1]; a[i+1,2]:=a[i,2]+x[j,2]; try(i+1); end; 19 19

跳马问题（思考）在本例中，我们只要求输出一条可行路径，如果我们需要输出所有的可行路径，怎样改动此程序呢？
如果我们把问题改成“在n×m的棋盘上有一骑士，开始时，骑士在点(x,y)，现在请你找出一条可行的路径，使得骑士可以不重复的走遍棋盘上的每一个点。”的话，又要如何编写此程序呢？

0,1背包问题已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大输入：第一行一个整数，为背包的容量M；第二行一个整数，为物品的种数Ｎ；第三行Ｎ个整数为各物品的重量；第四行Ｎ个整数分别为Ｎ个物品的价值输出：第一行为最大总价值；第二行为装入的各物品的重量（未装的物品用０）；第三行为装入的各物品的价值（未装的物品用０）返回到题目列表

算法分析本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为I（1~I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。另外，为了优化程序，我们定义一个函数如下： F[I]表示选第I~N个物品能得到的总效益。不难推出： F[N]=Pn F[I]=F[I+1]+Pi （I=1…N-1）假设当前已选到第I号物品，如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小，则没有必要继续搜索下去。返回到题目列表

算法框架 procedure search(i:integer; j:byte); {递归求解} var k:byte; begin
if now+f[j]<=ans then exit; {如果没有必要搜索下去} if now>ans then begin {修改最优解} ans:=now; out:=ou; end; for k:=j to n do {选取物品} if w[k]<=i then begin now:=now+p[k]; ou[k]:=true; search(i-w[k],k+1); now:=now-p[k]; ou[k]:=false;

售货员的难题某乡有n个村庄(1<n<40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。输入:村庄数n和各村之间的路程(均是整数)。输出:最短的路程。样例输入: {村庄数} 0 2 l {村庄1到各村的路程} {村庄2到各村的路程} {村庄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（）then if m+a[line,1]<min then min:=m+a[line,1]; exit; end; for i:=2 to n do if(i<>line)and（）then m:=m+a[line,i]; bj[line]:=false; if m<min then（ ); m:=m-a[line,i]; （）; var a:array[1..40,1..40] of integer; n,i,j:integer; min,m:longint; bj:array[1..40] of boolean; begin readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); fillchar(bj,sizeof(bj),true); min:= ; m:=0; road(1,1); writeln(min); end. step=n 满足最优性要求 bj[i] 剪枝 road(step+1,i) 恢复其递归前的值 bj[line]:=true

计算拆分方案给定一个正整数Ｎ，假设 0<A1<=A2<=A3...<=As 满足 A1+A2+A3+...+As=Ｎ，那么我们称序列A1 A2……As为Ｎ的一个拆分。现在要求Ｎ的拆分数目。（n<65）例如：当Ｎ= 6 时 6 = = = = = = = 1 + 5 = = 2 + 4 = 　　所以 6 的整数拆分个数为 10 。

var a:array[1..100] of integer; total,n:integer; procedure output(s:integer); {s为一个拆分的长度} 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 if( ) then
（）; output(d-1); exit; end; if low>rest then（）;{剪枝} for i:=low to rest do {枚举a[d]的所有可能值} a[d]:=i; if a[d]<>n then dfs( ); read(n); dfs( ); writeln('Total=',total); end. low为当前a[d]的下界,rest为还剩下多少要拆分. rest=0 inc(total) exit d+1,i,rest-i 1,1,n

测试3、数的划分（ 01年复赛）问题描述: 将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
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 div 3 7=1+1+5 =1+2+4 =1+3+3
分析：按份数递增的顺序拆分，且被拆分的整数按递增顺序排列（避免重复）。 7=1+6 =2+5 =3+4 第一个数要小于等于 7 div 3 7=1+1+5 =1+2+4 =1+3+3 第二个数要小于等于 6 div 2 7=2+2+3 第二个数要小于等于 5 div 2

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

测试4、选数( 01年复赛）已知n（1<=n<=20）个整数x1,x2,…,xn（1<=xi<= ），以及一个整数k（k<n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k=3，4个整数分别为3,7,12,19时，可得到的全部组合及它们的和为3+7+12=22，3+7+19=29， =38， =34。现在，要求你计算出和为素数的组合共有多少种。如上例中，只有一种的和为素数：3+7+19=29。输入： n , k x1,x2,…,xn 输出：一个整数(满足条件的组合个数) 输入输出样例 4 3 输出： 1

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

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

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

测试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 3 2 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; if (w>0)and(b>0) then begin {放‘B’的情况} b:=b-1; w:=w-1; w:=w+1; b:=b+1; 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 i=2时，ba<>bc s=‘abcbc ‘ i=1时，c<>b i=2时，bc=bc

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

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

x,y为当前马所在的位置计算马的控制点 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); 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); 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. x,y为当前马所在的位置目标回溯向右走向下走计算马的控制点

测试8、01字符串问题问题描述：输出仅由0和1组成的长度为n的字符串，并且其中不可含有三个连续的相同字串。
输入：字符串长度n（n<=40）输出：所有满足条件的字符串的个数。样例输入: 2 样例输出: 4

0 1 0 0 1 0 0 1 0 Z Y X Z Y X Z Y X R Q P R Q P R Q P R Q P 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 x:=lev; y:=lev-1; z:=lev-2; while z>0 do p:=x;q:=y;r:=z; while (r<y) and (list[p]=list[q]) and (list[q]=list[r]) do inc(p) ; inc(q) ; inc(r); end; if r=y then begin right:=false ; exit; x:=x-1;y:=y-2;z:=z-3 right:=true; Z Y X Z Y X Z Y X R Q P R Q P R Q P R Q 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｝ 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时：原来位置为：放回去时只能为：或这两种问题：求当n = 5时满足以上条件的放法共有多少种？

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

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

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

输出：（数字为长方形编号） 1 2 2 4 1 3 3 4 5 6 6 8 5 7 7 8 测试11 、棋盘覆盖
有边长为N（偶数）的正方形，用N*N/2个长为2、宽为1的长方形将它全部覆盖，请找出所有覆盖方法。如N=4时的一种覆盖方法及输出格式如下所示。输出：（数字为长方形编号） 1 2 4 3 5 6 8 7

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

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

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

例1、翻硬币(03年初赛题) 题目描述：　　一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们一起翻面后再放回原处。再取3枚，取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中的每一枚又都是正面朝上为止。　　输入：　　仅有的一个数字是这摞硬币的枚数m，0<m<50。　　输出：　　为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。　　输入样例：　　　　30 　　输出样例：　　　　899

procedure turn(k:integer);
var i:integer; begin if k>m then（　　　　）; b:=a; for i:=1 to k do 　b[i]:=not(　　　　　); a:=b; print; （　　　　　　）； end; readln(m); fillchar(a,sizeof(a),false); n:=0;｛翻面次数｝ turn(1);｛翻一个硬币｝ end. const max=100; var a,b:array[1..max] of boolean; m,n:integer; procedure print; var i:integer; 　 p:boolean; begin （　　　　　）； p:=true; for i:=1 to m do if a[i] then p:=false; if p then 　writeln('total=',n); 　（　　　　）; end; k:=1 a[k+1-i] inc(n) turn(k+1) halt

例2、求全排列(06年初赛题) 下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）： 312

procedure perm(k:integer); var j,p,t:integer; begin if( )then ( );
i,n,k:integer; a:array[1..10] of integer; count:longint; procedure perm(k:integer); var j,p,t:integer; begin if( )then ( ); for p:=1 to k do write(a[p]:1); write(' '); if( )then writeln; exit; end; for j:=k to n do begin t:=a[k]; a[k]:=a[j]; a[j]:=t; perm(k+1) ; t:=a[k];( ) end end; writeln('Entry n:'); read(n); count:=0; for i:=1 to n do a[i]:=i; ( ) end. a[k]:=a[j]; a[j]:=t ; K=n inc(count) count mod 5=0 perm(1)

123 123 213 321 123 132 213 231 321 312 123 132 213 231 321 312

例3、2的幂次方表示(98年复赛) 任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20
同时约定次方用括号来表示，即ab可表示为a (b)。由此可知，137可表示为：2 (7)+2 (3)+2 (0) 进一步：7= (21用2表示) 3=2+20 所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0) 又如：1315= 所以1315最后可表示为： 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0) 输入：一个正整数(n<=20000) 输出：符合约定的n的0,2表示 (在表示中不能有空格)

if( )then write('2(0)') else begin if t=2 then write('2') write('2('); ( ); write(')'); end; end; {情况二} begin readln(n); try(n); end. t=1 var n:longint; procedure try(n:longint); var a:array[ ]of integer; k,p,i,t:longint; begin fillchar(a,sizeof(a),0); k:=n; p:=0; t:=0; while( )do inc(p); a[p]:=k mod 2; if (a[p]<>0)and(t=0) then t:=p; {t记录二进制数中从最低位开始第一个'1'的位置} k:=k div 2; end; for i:=p downto t+1 do if a[i]=1 then if( )then write('2+') else begin write('2(');( ); write(')+'); end; {情况一} try(t-1) k>0 由于最后一项后面没有加号，其它项之后有加号，因此程序中进行了处别对待． i=2 try(i-1)

例4、集合找数【问题描述】集合A中的元素有以下特征： (1)数1是A中的元素；
(2)如果X是A中的元素，则2X+1，3X+1也是A中的元素； (3)除了条件（1），（2）以外的所有元素均不是A中的元素；给定数N，请求出集合中的第N个元素。例如 N=500， A500=3351 N=10000，A10000=157653

算法分析：从2开始，对其后的每一个数判断是否符合条件，如果符合则记数器加1，若不符合条件则试下一个数，直到产生了N个数为止。但在判断是否符合条件时，我们引入递归的思想去判断：例如，要判断15是否符合条件，先解出2X+1=15 或3X+1=15的X值（X必须取自然数），可见，X=7，然后任务转化为判断7是否符合条件，同理，求出2X+1=7 或3X+1=7的X值，X=2或X=3；然后继续判断2和3是否符合条件，求出2X+1=2 或3X+1=2或2X+1=3或3X+1=2的X值，有2X+1=3得X=1；最终能得到1，符合数列的定义：“数1是A中的元素”，说明15是集合中的元素。如果最终无法得出1，则说明不是集合的元素。

((x-1)mod 3=0)and(init((x-1)div 3))
var n,Long,x:longint; function init(x:longint):boolean; begin if x=1 then init:=true else if( (x-1)mod 2=0)and( init((x-1)div 2)) or then init:=true else 　　　　; end; readln(n); x:=0; Long:=0; while Long<n do x:= 　　　; if init(x) then ; writeln(　 ); end. ((x-1)mod 3=0)and(init((x-1)div 3)) init:=false x+1 Long:=Long+1 x

例5、求先序遍历给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8）。 [样例] 输入：BADC
BDCA 输出：ABCD 分析: 通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。同样的，也可以通过对比左子树的中序与后序排列，找出左子树的根节点……可见，该问题能够被递归描述。当找到最后一个根节点时，递归无法再进行下去，这就是递归结束的边界条件。

var z,h:string; procedure find(a,b:string); var s,L : integer; begin L:=length(b); if( )then write(b){是叶子结点} else begin write(b[L]);{后序遍历的最后一个是根} s:=pos(b[L],a);{在中序遍历中找出根的位置} if s-1>0 then {若存在左子树} find(copy( ),copy( )); {递归左子树} if L-s>0 then {若存在右子树} find(copy( ),copy( )); {递归右子树} end; readln(z); readln(h); find(z,h); end. DEABFCHG DEAFHGCB BAEDCFGH L=1 a,1,s-1 b,1,s-1 a,s+1,L-s b,s,L-s

例6、黑白棋子的移动问题描述: 有2n个棋子（n≥4）排成一行，开始位置白子全部在左边，黑子全部在右边，如下图为n=5时的情况：
【样例】 chessman.in chessman.out step 0:ooooooo*******-- step 1:oooooo--******o* step 2:oooooo******--o* step 3:ooooo--*****o*o* step 4:ooooo*****--o*o* step 5:oooo--****o*o*o* step 6:oooo****--o*o*o* step 7:ooo--***o*o*o*o* step 8:ooo*o**--*o*o*o* step 9:o--*o**oo*o*o*o* step10:o*o*o*--o*o*o*o* step11:--o*o*o*o*o*o*o* 问题描述: 有2n个棋子（n≥4）排成一行，开始位置白子全部在左边，黑子全部在右边，如下图为n=5时的情况： ○○○○○●●●●● —— 移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为： —— ○●○●○●○●○● 任务：编程打印出移动过程。

我们先从n=4开始试试看，初始时： ○○○○●●●● —— 第1步：○○○——●●●○● 第2步：○○○●○●●——● 第3步：○——●○●●○○● 第4步：○●○●○●——○● 第5步：——○●○●○●○● 如果n=5呢？我们继续尝试，希望看出一些规律，初始时： ○○○○○●●●●● —— 第1步：○○○○——●●●●○● 第2步：○○○○●●●●——○● 这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把它转化为规模为n-1的相同类型子问题。数据结构如下：数组c[1..max]用来作为棋子移动的场所，初始时，c[1]~c[n]存放白子（用字符o表示），c[n+1]~c[2n]存放黑子（用字符*表示），c[2n+1]，c[2n+2]为空位置（用字符—表示）。最后结果在c[3]~c[2n+2]中。

第1步：○○○○——●●●●○● 第2步：○○○○●●●●——○●
procedure move(k:integer); {移动一步} var j:integer; begin for j:=0 to 1 do {移两个棋} c[sp+j]:=c[k+j] ; c[k+j]:='-'; end; ( ); print procedure mv(n:integer); var i,k:integer; if n=4 then begin move(4); move(8); move(2); move(7);( ) end else begin move(n); move(2*n-1); ( ) readln(n); init(n); mv(n); end. const max=100; var n,st,sp:integer; c:array[1..max] of char; procedure print; {打印} var i:integer; begin write('step',st:2,':'); for i:=1 to 2*n+2 do write(c[i]); writeln; ( ) end; procedure init(n:integer); {初始化} st:=0; {移动步数} sp:=2*n+1; for i:=1 to n do c[i]:='o'; for i:=n+1 to 2*n do c[i]:='*'; c[2*n+1]:='-';c[2*n+2]:='-'; print 第1步：○○○——●●●○● 第2步：○○○●○●●——● 第3步：○——●○●●○○● 第4步：○●○●○●——○● 第5步：——○●○●○●○● sp:=k st:=st+1 move(1) mv(n-1) 第1步：○○○○——●●●●○● 第2步：○○○○●●●●——○●

数独的规则很简单，3x3的数独题就是一个9x9的方阵，方阵中的每一个格子可以填入1-9的数字，要求是：每行不能有重复的数字，每列也不能有重复的数字，而且9x9的方阵再划分为9个3x3的小方阵，要求每个小方阵中也不能有重复的数字。按照正常的数独规则，每个问题必须只能有一个答案，不过这个规则与我们的搜索算法无关，我们可以不理睬问题是否无解或有多个解，只管搜索就是了

④v[a[i,j],k] and v[b[i,j],k] and v[c[i,j],k]; ⑤g[i,j]:=k;
var g,a,b,c:array[0..8,0..8] of longint; v:array[0..26,0..9]of boolean; i,j,x,y,k,n:longint; procedure print; begin for i:=0 to 8 do for j:=0 to 8 do writeln(g[i,j],' '); writeln; end; close(output); halt; procedure search(i,j,dep:longint); var k:longint; if ① then print; if j>8 then ② else if g[i,j]>0 then ③ else for k:=1 to 9 do if ④ then ⑤ ; v[a[i,j],k]:=false; v[b[i,j],k]:=false; v[c[i,j],k]:=false; search(i,j+1,dep+1); v[a[i,j],k]:=true; v[b[i,j],k]:=true; v[c[i,j],k]:=true; g[i,j]:=0; begin fillchar(v,sizeof(v),true); for i:=0 to 8 do for j:=0 to 8 do read(g[i,j]); if g[i,j]=0 then inc(n); a[i,j]:=i div 3*3+j div 3; b[i,j]:=9+i; {按区的第二排} c[i,j]:=18+j; {按区的第三排} v[a[i,j],g[i,j]]:=false; v[b[i,j],g[i,j]]:=false; v[c[i,j],g[i,j]]:=false; end; search(0,0,1); end. ①dep>n; ②search(i+1,0,dep); ③search(i,j+1,dep); ④v[a[i,j],k] and v[b[i,j],k] and v[c[i,j],k]; ⑤g[i,j]:=k;

const size=100; var n,m,x,y,i :integer; r: array[1.. size] of integer; map : array[1..size, 1..size] of boolean; found : boolean; function successful : boolean; var i : integer; begin for i :=1 to n do if not map[r[i]][r[i mod n + 1]] then begin successful := false; exit; end; successful :=true; end; procedure swap(var a, b : integer); var t : integer; begin t := a; a := b; b := t;end; procedure perm(left, right : integer); var i : integer; if found then exit; if left > right then begin if successful for i := 1 to n do writeln(r[i], ' '); found := true; exit; for i:= left to right do begin swap(r[left], r[i]); perm(left + 1, right); swap(r[left], r[i]); end; begin readln(n, m); fillchar(map, sizeof(map), false); for i := 1 to m do begin readln(x, y); map[x][y] := true; map[y][x] := true; end; for i := 1 to n do r[i] := i; found := false; perm(1, n); if not found then writeln('No soloution'); end. 输入: 9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9 1 6 9 7 2 8 5 3 4

const size=100; var n,m,x,y,i :integer; r: array[1.. size] of integer; map : array[1..size, 1..size] of boolean; found : boolean; function successful : boolean; var i : integer; begin for i :=1 to n do if not map[r[i]][r[i mod n + 1]] then begin successful := false; exit; end; successful :=true; end; procedure swap(var a, b : integer); var t : integer; begin t := a; a := b; b := t;end; procedure perm(left, right : integer); var i : integer; if found then exit; if left > right then begin if successful for i := 1 to n do writeln(r[i], ' '); found := true; exit; for i:= left to right do begin swap(r[left], r[i]); perm(left + 1, right); swap(r[left], r[i]); end; begin readln(n, m); fillchar(map, sizeof(map), false); for i := 1 to m do begin readln(x, y); map[x][y] := true; map[y][x] := true; end; for i := 1 to n do r[i] := i; found := false; perm(1, n); if not found then writeln('No soloution'); end. 输入: left right right left

例3：输入一串以‘!’结束的字符，按逆序输出。

Similar presentations

Presentation on theme: "例3：输入一串以‘!’结束的字符，按逆序输出。"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

例3：输入一串以‘!’结束的字符，按逆序输出。

Similar presentations

Presentation on theme: "例3：输入一串以‘!’结束的字符，按逆序输出。"— Presentation transcript:

Similar presentations

About project

反馈