NOIP基础算法--枚举、递推和递归教程课件.ppt

到第一半零一个；以后每天如此到第n天，猴子一看天，猴子一看只剩下一个了问最初有多少个桃子？只剩下一个了问最初有多少个桃子？ 【【扩展练习扩展练习】】猴子分桃猴子分桃 【【问题描述问题描述】】有一堆桃子和N只猴子，第一只猴子将桃子平均分成了M堆后，还剩了1个，它吃了剩下的一个，并拿走一堆后面的猴子也和第1只进行了同样的做法，请问N只猴子进行了同样做法后这一堆桃子至少还剩了多少个桃子(假设剩下的每堆中至少有一个桃子)？而最初时的那堆桃子至少有多少个？ 【【文件输入文件输入】】输入包含二个数据，数据间用空格隔开第一个数据为猴子的只数N(1≤N≤10)，第二个数据为桃子分成的堆数M(2≤M≤7) 【【文件输出文件输出】】输出包含两行数据，第一行数据为剩下的桃子数，第二行数据为原来的桃子数 【【样例输入样例输入】】3 2 【【样例输出样例输出】】 1 15（一）递推的应用（一般递推问题）（一）递推的应用（一般递推问题）•【【例题例题6】】传球游戏（传球游戏（NOIP2008普及）普及）•【【问题描述问题描述】】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。

这次，老师带着同学们一起做传球游戏 　　游戏规则是这样的：n（3<=n<=30）个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目 　　聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m（3<=m<=30）次后，又回到小蛮手里两种传球被视作不同的方法，当且仅当这两种方法中，接到球的同学按照顺序组成的序列是不同的比如3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共两种 分析n设f[i,k]表示经过k次传到编号为i的人手中的方案数，传到i号同学的球只能来自于i的左边一个同学和右边一个同学，这两个同学的编号分别是i-1和i+1，所以可以得到以下的递推公式：          f[i,k]=f[i-1,k-1]+f[i+1,k-1]          f[1,k]=f[n,k-1]+f[2,k-1],   当i=1时          f[n,k]=f[n-1,k-1]+f[1,k-1],   当i=n时          边界条件：f[1,0]=1；’没传边界条件          answer=f[1,m]         ‘传送m次后回到自己。

参考代码 readln(n,m); f[1,0]:=1; for k:=1 to m do begin f[1,k]:=f[2,k-1]+f[n,k-1]; for i:=2 to n-1 do f[i,k]:=f[i-1,k-1]+f[i+1,k-1]; f[n,k]:=f[n-1,k-1]+f[1,k-1]; end; writeln(f[1,m]);（二）递推的应用（组合计数）（二）递推的应用（组合计数）nCatalan数数n例题例题7：凸：凸n边形的三角形剖分边形的三角形剖分n在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用f(n)表之，f(n)即为Catalan数例如五边形有如下五种拆分方案，故f(5)=5求对于一个任意的凸n边形相应的f(n)分析:•设f(n)表示凸n边形的拆分方案总数由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，……，Pn-1点中找一个点Pk(1

个结点能构成不同二叉数的数目问题分析】：         设F(n)为n个结点组成二叉树的数目         容易知道：f(1)=1;f(2)=2,f(3)=5       选定1个结点为根，左子树结点的个数为i，二叉树数目f(i)种；右子树结点数目为n-i-1，二叉树数目f(n-i-1)种，i的可取范围[0，n-1]所以有：   为了计算的方便：约定f(0)=1【【扩展扩展2】】：出栈序列：出栈序列【【问题描述问题描述】】：：N个不同元素按一定的顺序入栈，求不同的个不同元素按一定的顺序入栈，求不同的出栈序列数目出栈序列数目问题分析】设f(n)为n个元素的不同出栈序列数目       容易得出：f(1)=1；f(2)=2       第n个元素可以第i(1<=i<=n)个出栈，前面已出栈有i-1个元素，出栈方法：f(i-1)；后面出栈n-i 个元素，出栈方法为：f(n-i)所以有：         初始条件： F(0)=1 （二）递推的应用（组合计数）（二）递推的应用（组合计数）例题例题10：错排问题（经典问题）：错排问题（经典问题）nn个数，分别为1~n，排成一个长度为n的排列。

若每一个数的位置都与数的本身不相等，则称这个排列是一个错排例如，n=3，则错排有2 3 1、3 1 2编写程序，求n的错排个数分析Ø我们设k个元素的错位全排列的个数记做：f(k)Ø四个元素的错位排列f(4)我们用穷举法可以找到如下9个： (4,3,2,1);(3,4,1,2);(2,1,4,3) (4,3,1,2);(2,4,1,3);(2,3,4,1) (4,1,2,3);(3,4,2,1);(3,1,4,2)Ø它们有什么规律呢？n通过反复的试验，我们发现事实上有两种方式产生错位排列：            A、将k与(1，2，…，k-1)的某一个数互换，其他k-2个数进行错排，这样可以得到(k-1)×f(k-2)个错位排列             B、另一部分是将前k-1个元素的每一个错位排列(有f(k-1)个)中的每一个数与k互换，这样可以得到剩下的(k-1)×f(k-1) 个错位排列n根据加法原理，我们得到求错位排列的递推公式f(k):f(k)=(k-1)*(f(k–1)+f(k–2))分析分析（二）递推的应用（组合计数）（二）递推的应用（组合计数）例题例题11：编码问题：编码问题n【【问题描述问题描述】】编码工作常被运用于密文或压缩传编码工作常被运用于密文或压缩传输。

这里我们用一种最简单的编码方式进行编码：输这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字字母表中共有把一些有规律的单词编成数字字母表中共有26个小写字母个小写字母{a,b,c….,z}这些特殊的单词长度不这些特殊的单词长度不超过超过6且字母按照升序排列把所有这样的单词放且字母按照升序排列把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置，例如：应着它在字典中的位置，例如：a-1;b-2;z-26;ab-27;ac-28;你的任务就是对于所给的单词，求出它你的任务就是对于所给的单词，求出它的编码 （二）递推的应用（组合计数）（二）递推的应用（组合计数） 例题例题12：：2^k进制数（进制数（NOIP2006）） 见见word文档文档（三）递推的应用（博弈问题）（三）递推的应用（博弈问题）例例例例题题题题13131313：：：：走走走走直直直直线线线线棋棋棋棋问问问问题题题题有如下所示的一个编号为１到ｎ的方格： 现由计算机和人进行人机对奕，从１到ｎ，每次可以走ｋ个方格，其中ｋ为集ｓ={a1,a2, a3,....am}中的元素(m<=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。

12345 … …N-1 N分析n题设条件：若谁先走到第N格谁将获胜，例如，假设S={1,2}，从第N格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态分析分析        设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格        例如，设N＝10，S＝{1,2}，则可确定其每个棋格的状态如下所示：        而N＝10，S＝{2,3}时，其每格的状态将会如下所示：        有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，这样就能保证计算机尽可能不败1 1-1-1-1-11 1-1-1-1-11 1-1-1-1-11 10 0-1-1-1-10 01 10 0-1-1-1-10 01 1（四）递推的应用（动态规划中的递推）（四）递推的应用（动态规划中的递推）n例题例题14：最小伤害：最小伤害 n把儿站在一个N x N的方阵中最左上角的格子里。

他可以从一个格子走到它右边和下边的格子里每一个格子都有一个伤害值他想在受伤害最小的情况下走到方阵的最右下角分析分析nF[i,j]：设走到(i,j) 这格的最小伤害值,a[i][j]表示(i,j)这格的伤害值nF[i,j]=min(f[i-1,j],f[i,j-1])+a[i,j]n边界条件：f[1,1]=a[1,1] f[i,1]=f[i-1,1]+a[i,1](2<=i<=n) f[1,i]=f[1,i-1]+a[1,i](2<=i<=n)Ø见见wordword文档文档例题例题1515：：乌龟棋（乌龟棋（NOIP2010NOIP2010提高）提高） 动态规划与递推的关系动态规划与递推的关系n上题实质上是采用动态规划来求解上题实质上是采用动态规划来求解,那么递推与动那么递推与动态规划之间到底是什么关系呢？态规划之间到底是什么关系呢？n我们不妨画个图我们不妨画个图(如下图如下图)而通常人们理解的递而通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个体。

推关系是两个各自独立的个体动态规划一般递推关系递推关系动态规划与递推的关系动态规划与递推的关系n1、一般递推边界条件很明显，动态规划边界条件比较隐蔽，容易被忽视；n2、一般递推数学性较强，动态规划数学性相对较弱；n3、一般递推一般不划分阶段，动态规划一般有较为明显的阶段；第三部分第三部分递归策略递归策略一、递归的概念一、递归的概念n一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用二、递归的基本思想二、递归的基本思想 n递归是借助于一个递归工作栈栈来实现；递归递归=递推递推+回归回归；n1.递推：递推：问题向一极推进, 这一过程叫做递推；这一过程相当于压栈压栈n2.回归：回归：问题逐一解决，最后回到原问题，这一过程叫做回归这一过程相当于弹栈弹栈二、递归的基本思想二、递归的基本思想例题例题1：用递归算法求：用递归算法求n!定义：函数定义：函数定义：函数定义：函数 fact(n)=n!fact(n)=n!fact(n-1)=(n-1)!fact(n-1)=(n-1)!递推方程：递推方程：递推方程：递推方程：fact(n)=n*fact(n-1)fact(n)=n*fact(n-1)边界条件：边界条件：边界条件：边界条件：fact(1)=1fact(1)=181下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图三、递归的实现三、递归的实现n递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。

n由此可以想到，减少每个“工作记录”的大小便可节省部分空间例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简例题例题2 2：求：求a[1..n]a[1..n]的最大者的最大者有如下过程：有如下过程：Procedure findmax(i:integer;var max:integer);var j:integer;begin max:=a[i]; if i=n then exit else begin findmax(i+1,j); if j>max then max:=j; end;end; n起始状态就是调用起始状态就是调用findmax(1,max),而像上述过程而像上述过程中的变参中的变参max完全可以省略将上述方法修改可得下完全可以省略将上述方法修改可得下面的算法：面的算法：Procedure findmax(i:integer);begin if i=n then exit else begin findmax(i+1); if a[i]>max then max:=a[i]; end;end;n起始状态就是调用起始状态就是调用findmax(1) ，，max为全局为全局变量，同时还减少了一个局部变量的使用。

尽管变量，同时还减少了一个局部变量的使用尽管这只是一个很简单的例子，在本例中不做精简，这只是一个很简单的例子，在本例中不做精简，程序也还是能通过，但它精简的原则对其它使用程序也还是能通过，但它精简的原则对其它使用递归的程序而言却是同样适用的特别是在递归递归的程序而言却是同样适用的特别是在递归过程出现过程出现堆栈溢出情况时堆栈溢出情况时就应该考虑这一问题就应该考虑这一问题四、递归的优点与缺点四、递归的优点与缺点n优点：采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决n缺点：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境五、递归的应用五、递归的应用n 处理递归定义或解决方法为递归方式的问题n 解决搜索问题和组合计数n 实现分治思想n 用于输出动态规划的中间过程1、递归定义问题、递归定义问题n树结构是由递归定义的因此，在解决与树有关的问题时，常常可以采用递归的方法。

2、解决搜索问题、解决搜索问题n因为搜索产生的节点成树状结构，所以可以用递归方法解决这类例子很多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题例题例题3：全排列：全排列 【【问题描述问题描述】】编程列举出编程列举出1、、2、、…、、n的全排列，要的全排列，要求产生的任一个数字序列中不允许出现重复的数字求产生的任一个数字序列中不允许出现重复的数字文件输入文件输入】】输入输入n(1<=n<=9)【【文件输出文件输出】】有有1到到n组成的所有不重复数字的序列，组成的所有不重复数字的序列，每行一个序列每行一个序列分析分析n我们假设n=3时，如下图：位置1可以放置数字1、2、3；位置2可以放置数字1、2、3；位置3可以放置数字1、2、3，但是当位置1放了数字1后位置2和位置3都不能在放1，因此画树的约束条件是：各位置的数字不能相同 分析分析n我们画“解答树”时，根结点一般是一个空结点，根结点下面的第1、2、3三层分别对应位置1、位置2、位置3，用“╳”标示的分支表示该结点不满足约束条件，不能被扩展出来：procedure f(k:integer) //搜索第搜索第k层结点（向第层结点（向第k个位置放数）个位置放数）begin var i:integer; if k=n+1 then begin for i:=1 to n do write(a[i]);writeln;end // 如果搜索到一条路径，则输出一种解如果搜索到一条路径，则输出一种解 else for i:=1 to n do//每一个结点可以分解出每一个结点可以分解出n个子结点；个子结点； if b[i]=0 then //如果能生成第如果能生成第k层的第层的第i个结点；个结点； begin a[k]:=i; //第第k个位置为数字个位置为数字i；； b[i]:=1; //标记数字标记数字i已用已用 f(k+1); //扩展第扩展第k层的第层的第i个结点个结点(向第向第k+1个位置放数个位置放数) b[i]:=0; //向上回溯，并恢复数据向上回溯，并恢复数据 end;end;n我们用递归过程来描述我们用递归过程来描述我们用递归过程来描述我们用递归过程来描述 “ “解答树解答树解答树解答树” ”的深度优先搜索的深度优先搜索的深度优先搜索的深度优先搜索3、实现分治思想、实现分治思想n不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。

n因此无论是归并排序，还是堆排序、快速排序，都存在有分治的思想只要分开处理，就可以采用递归处理其实进行分治，也是一个建树的过程n如下图中归并排序的过程：例题例题4：表达式求值：表达式求值 u由键盘输入一个算术表达式，该表达式由数字，加(+)、减(-)、乘(*)、求商(/)运算符及小括号组成 u例如：6*(8-1)+(5-(12-7)/5)/2u请编写一个程序，计算输入表达式的值 funtion tree(left,right:integer):integer;funtion tree(left,right:integer):integer;beginbegin var tmp,L1,L2,p:integer; var tmp,L1,L2,p:integer; tmp:=isnum(left,right); tmp:=isnum(left,right); if tmp<>-1 begin tree:=tmp;exit;end;// if tmp<>-1 begin tree:=tmp;exit;end;//返回值返回值返回值返回值 if (st[left]='(')and (poskh(left,right)=right) thenif (st[left]='(')and (poskh(left,right)=right) then tree:=tree(left+1,right-1); tree:=tree(left+1,right-1); // //去掉最外层的括号去掉最外层的括号去掉最外层的括号去掉最外层的括号 p:=findlow(left,right); //p:=findlow(left,right); //找运算级别最低的运算符找运算级别最低的运算符找运算级别最低的运算符找运算级别最低的运算符 L1:=tree(left,p-1); //L1:=tree(left,p-1); //递归左子树递归左子树递归左子树递归左子树 L2:=tree(p+1,right); //L2:=tree(p+1,right); //递归右子树递归右子树递归右子树递归右子树 tree:=cal(L1,st[p],L2);tree:=cal(L1,st[p],L2);end;end;4、用于输出动态规划的中间过程、用于输出动态规划的中间过程例题例题5：复制书稿：复制书稿 【【问题描述问题描述】】假设有m本书（编号为1,2,…m），想将每本复制一份，m本书的页数可能不同（分别是p1,p2,…pm）。

任务是将这m本书分给k个抄写员（k<=m），每本书只能分配给一个抄写员进行复制，而每个抄写员所分配到的书必须是连续顺序的 复制工作是同时开始进行的，并且每个抄写员复制的速度都是一样的所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间n试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小（如存在多个最优方案，输出结果排序最小的一种） 分析分析n该题中m本书是顺序排列的，k个抄写员选择数也是顺序且连续的不管以书的编号，还是以抄写员标号作为参变量划分阶段，都符合策略的最优化原理和无后效性考虑到k<=m，以抄写员编号来划分阶段会方便些 n设f[i,j]为前i个抄写员复制前j本书的最小“页数最大数”S[i]=a[1]+a[2]+…+a[i]，则状态转移方程为：nf[i,j]=min{max(f[i-1,k],S[j]-S[k])}(i-1<=k<=j-1)nd[i,j]=k；记录第i个人的最佳位置n边界条件 f[1,i]=S[i]n输出方案，则递归输出；输出方案，则递归输出；procedure Print(i,j:integer)begin if i=1 then begin writeln(1,’ ‘,j);exit;end; Print(i-1,d[i,j]); writeln(d[i,j]+1,’ ‘,j);end第四部分第四部分归纳策略归纳策略一、归纳法的基本思想一、归纳法的基本思想 n归纳法的基本思想：归纳法的基本思想：是通过列举少量的特殊情况，经过分析，最后找出一般的关系。

n从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径 二、归纳法解题二、归纳法解题的过程的过程1.细心的观察；细心的观察；2.丰富的联想；丰富的联想；3.继续尝试；继续尝试；4.总结归纳出结论总结归纳出结论二、归纳法解题二、归纳法解题的过程的过程n归纳是一种抽象，即从特殊现象中找出一般关系n由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)所以，严格说来对于归纳假设还必须加以严格的证明三、归纳策略解题应注意的问题三、归纳策略解题应注意的问题1.从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系2.从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解四、归纳策略的应用四、归纳策略的应用例题例题1：求前n个自然数的平方之和： S=12+22+32+……+n2 【【分分析析】】这本是一道很简单的题目，但如果能找出S值与n的关系，则此题将更进一步得到简化，由数学证明得知：(12+22+32+…+n2)/(1+2+3+…+n) =(2n+1)/3又由于 1+2+3+…+n=n(n+1)/2，因此得到： 12+22+32+…+n2=n(n+1) (2n+1)/6 但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。

例题例题2：乘积最大【问题描述】若干个正整数之和为n，其中：n<2000，试求它们乘积的最大值以及该最大值的位数k 【【【【分析分析分析分析】】】】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：•当N mod 3＝1 时，N可分解为一个4和若干个3的和； •当N mod 3＝2 时，N 可分解为一个2和若干个3的和；•当N mod 3＝0 时，N 直接分解为若干个3的和 按照这一分解方法，所有因数的乘积必定最大注意注意：因N 的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算例题例题例题例题3 3：极值问题      已知m、n为整数，且满足下列两个条件：         ① m、n∈1，2，…，K，（1≤K≤109）         ② (n 2－mn－m2)2＝1       编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2＋n2的值最大例如，若K＝1995，则m＝987，n＝1597，则m、n满足条件，且可使m2＋n2的值最大【【分析分析】】分析小数据会发现：m,n是Fibonacci数列的相邻两项。

因为：(n2-mn-m2)2 =1 故： (m2+mn-n2 )2=1 又： m2+mn-n2=(m+n)2-mn-2n2 =(m+n)2-(m+n)n-n2 故：(m2+mn-n2)2=[(m+n)2-(m+n)n-n2]2 即：(n2-mn-m2)2=[(m+n)2-(m+n)n-n2]2【【【【分析分析分析分析】】】】由上述数学变换式可以得出，如果m和n为一组满足条件①和条件②的解，设n’=m+n，m’=n那么n’，m’也是一组满足条件①和条件②的一组解将所有满足条件①和条件②的m和n 按递增顺序排成一个Fibonacci数列 ｛1，1，2，3，5，8，……｝ 数列中小于k的最大两个相邻数即为试题所要求的一组m和n算法算法】】利用Fibonacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2＋n2的值最大 例题例题4：士兵排队问题：士兵排队问题 【【问题描述问题描述】】有有N个士兵（个士兵（1<=N<=100),编号依次为编号依次为1,2,...,N。

队队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1 比比2 高，高，7 比比 5高高”这样的比较结果如果不能排成一排，则这样的比较结果如果不能排成一排，则输出输出"No answer"文件输入文件输入】】第一行为一个整数第一行为一个整数N（（N<=100），表示士兵的个数表示士兵的个数接下来若干行每行两个数接下来若干行每行两个数A和和B，表示，表示A高于高于BA,B属于１属于１..ＮＮ)【【文件输出文件输出】】输出文件只有一行为一个合法的排队序列输出文件只有一行为一个合法的排队序列样例输入样例输入】】 4 1 2 2 3 4 2 1 4【【样例输出样例输出】】1 4 2 3【【思思路路点点拨拨】】由题意可知，所有士兵的身高关系对应一张图，每两个士兵的身高关系对应于一条边；A高于B对应于一条有向边，将B的入度加1，AB这条边称之为A的出边如果有环，显然不能得到排队方案；无环时，每次选入度为0的点，且删除与该点相连的边，再重复上述操作，即可得到士兵的排队方案这种方法称为拓扑排序，能构造出最优解1243。