经典算法普及——基础篇

kon3155

已知字母A,B和一组字母变换规则(至多100个规则): A1->B1 A2->B2 规则的含义为:如果A=Ak，可以通过一次变换为Bk（1≤k ≤ 规则数） 求从A到B最少需要几次变换。 【输入文件】letter.in 第一行为两个字母，分别是初始字母和变换目标字母。 以下k行为变换规则（1 ≤ k ≤ 100），都是大写字母，两个字母间以空格间隔，直到文件结束。 【输出文件】letter.out 最小的变换次数。如果无法变换，则输入”No Answer!” 【样例数据】 【输入】letter.in A Z A E E F F T T Z A C C Z 【输出】letter.out 2 【参考程序查看】

kon3155

在一个地图上有n(n≤20)个地窖,每个地窖中埋有一定数量的地雷,给出地窖之间的联系路径。当地窖极其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖雷的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。请编程设计一个挖地雷的方案，使某人能挖到的最多的地雷。 【输入文件】miner.in n(地窖个数) v1 v2 v3 ... vn (每个地窖的地雷数) a(1,2) ... a(1,n) a(2,3) ... a(2,n) . . . a(n-1,n) (表示地窖之间连接路径，其中a(i,j)表示地窖i,j之间是否有通路，若有通路，则a(i,j)=1，若无通路，则a(i,j)=0） 【输出文件】miner.out R1-R2-...-Rk(挖地雷的顺序) Max(挖的地雷总数) 【样例数据】 【输入】miner.in 6 2 10 20 8 5 7 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 【输出】miner.out 2-3 30 【参考程序查看】

kon3155

乌托邦有n个城市，某些城市之间有公路连接。任意两个城市都可以通过公路直接或间接到达，并且任意两个城市之间有且仅有一条路径。 每条公路都有自己的长度，这些长度都是已经测量好的。小修想从一个城市出发开车到另一个城市，并且她希望经过的公路总长度最长。请问她应该选择哪两个城市？这个最长的长度是多少？ 【输入文件】wutuo.in 第一行一个整数n(表示n个城市，n≤100)，以下n-1行每行三个整数a,b,c。表示城市之间有公路连接，并且公路的长度是c(c≤10000)。 【输出文件】wutuo.out 仅一个数，即最长长度 【样例数据】 【输入】wutuo.in 5 1 2 2 2 3 1 2 4 3 1 5 4 【输出】wutuo.out 9 【参考程序查看】

kon3155

住在乌托邦首都（编号为1）的天凯，开始对首都的交通情况感到不满，因为，他发现首都到某些城市，即使他选择最短的路径，距离也非常远。因此他想让你求一下交通中心城市是哪座城市（也有可能就是首都）。 为了说明交通中心城市的概念，先定义G[j]为距离城市i最远的城市（到城市i的最短路径长度最长的城市）到城市i的距离。那么交通中心城市都是G[j]最小的城市，如果有几个城市的G[j]一样小，则是编号最小的那个。 【输入文件】capital.in 第一行两个整数n,m(n≤100)。下面m行，每行三个整数，第i+1行的整数表示第i条高速公路连接的两个城市编号和长度（0参考程序查看】 [ 本帖最后由 kon3155 于 2009-2-25 12:53 编辑 ]

kon3155

【最短路径问题】 下图给出了一张地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度，求从A地到E地的最短路径。 【分析】本题可以利用深度搜索法求解，伪代码如下： var s:未访问的城市集合; dist[i,j]:存储任意两个城市间的距离数组; {0表示不连通}

2. function search(city):integer; {求城市city到城市E的最短距离}
3. begin
4. if city=E then search←0;
5. else begin
6. min:=maxint;
7. for i取遍所有城市 do
8. if dist[city,i]>0 and (i∈s)
9. then begin
10. s←s-[i];
11. j←dist[city,i]+search(i); {递归调用搜索过程}
12. s←s+[i];
13. if j<min then min←j;
14. end;
15. search←min;
16. end;
17. begin
18. s←除E外所有城市；
19. dist[A,E]←search(A);
20. end.

复制代码

【效率评价】采用深度搜索的时间复杂度是W(n!)，效率很低。主要的原因就在于重复计算了很多路径值。如果把每次计算得到的最短距离保存下来就可以节省很多时间，于是产生了动态规划的思路。 【动态规划】从城市A出发，按照与城市A的路径长度划分阶段。 阶段0包含的出发城市有{A} 阶段1包含的城市有{B1，B2} 阶段2包含的城市有{C1，C2，C3，D，C4} 阶段3包含的城市有{D1，D2，D3} 阶段4包含的城市有{E} 这种划分的性质如下： （1）阶段 i 的取值只与阶段 i+1 有关，阶段 i+1 的取值对阶段 i 的取值产生影响； （2）每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。 从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市A，得到如下算法：

2. map[i,j]←两个城市之间的距离数组
3. dist[E]←0；
4. for k←3 downto 0 do
5. for x 取遍k阶段的所有城市 do
6. begin
7. dist[x]←∞；
8. for y取遍k+1阶段的所有城市 do
9. if dist[y]+map[x,y]<dist[x]
10. then dist[x]←dist[y]+map[x,y];
11. end;
12. 输出dist[A];

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 12:56 编辑 ]

kon3155

一、动态规划程序设计的基本概念 1、阶段k 将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每个阶段的解。设阶段变量为k。 2、状态Sk 各阶段开始的客观条件叫做状态，常用Sk表示各阶段的状态变量，Sk是k阶段的状态集合。 每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移。 将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其他状态没有关系，尤其是未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总结”。就个特性称为“无后效性”。 3、决策 当各阶段的状态取定以后，就可以作出不同的决定，从而确定下一个阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，常用Uk(Sk)表示第k阶段当状态为Sk时的决策变量，某个状态的决策可能有多个，以Dk(Sk)表示决策集合。 决策是问题解的属性。决策的目的就是“确定下一个阶段的状态”。 4、最优策略 在某一阶段的所有策略中，如有一个策略最优对于当前问题最优，则称最优策略。无论先前初始状态及初始策略如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。 5、最优指标函数 用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为Fk(Sk)。最优指标函数其实就是我们真正关心的问题的解。 二、动态规划程序设计的一般步骤 1、确定问题的研究对象，即状态。对于一个动态规划程序设计来说，状态的设计与存储比阶段的划分更重要，因为阶段只是一些可以等同处理的状态的集合，状态的选定对整个问题的处理起了决定性的作用。选定状态必须满足如下两点： ① 状态必须完全描述出事物的性质，两个不同的事物的状态是不同的。 ② 必须存在状态与状态之间的“转移方程”，以便可以由初始状态逐渐转化为目标状态。 2、划分阶段，确定阶段之间的状态转移方程。 3、考察此问题可否用动态规划程序设计方法解决，即问题是否具备最优子结构和无后效性的特征 4、如果发现问题目前不能用动态规划程序设计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。 三、程序设计一般格式： Fn(Sn)←某个初始值； for k←n-1 downto 1 do for S 取遍所有状态 do for U 取遍所有决策 do Fk(Sk)取最优决策 ；

kon3155

【骑士游历问题】 设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目。 输入： m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标) 输出： 路径数目（若不存在，则输出0） 【分析】 本题可以使用深度搜索发求解，但是效率很低，当路径很多时，不可能在短时间内出解。可以采用动态规划的设计思想。 从（x1,y1）位置出发，按照由左到右的顺序定义阶段的方向。位于（x2,y2）的左方且可达（x2,y2）的跳马位置集合都是（x2,y2）的子问题，起点至（x2,y2）的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。 阶段i：中国象棋马当前的列位置（x1≤i≤x2） 状态j：中国象棋马在i列的行位置（1≤i≤m） 状态转移方程map[i,j]：起点（x1,y1）至（i,j）的路径数目 具体算法如下： fillchar(map,sizeof(map),0); map[x1,y1]←1； for i←x1+1 to x2 do for j←1 to m do map[i,j]←map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1]; writeln(map[x2,y2]); 【参考程序】

kon3155

【最长递增子序列】 给定数列A1,A2,...An，求最长递增子序列 输入： 第一行一个整数n，表示有n个数(n<=1000) 第二行n个整数，用空格隔开。 输出： 最长递增子序列长度。 【分析】 在求以Ai为末元素的最长递增子序列时，找到所有序号在Ai前面且小于Ai的元素Aj，即j

2. S[1]:=1; {以第一个元素为末元素的递增序列长度肯定是1}
3. For i←2 to n do
4. For j←1 to i-1 do
5. Begin
6. 搜索A[i]前面比A[i]小的数A[j]，得到对应的S[j];
7. S[i]←max{S[j]}+1;
8. End;
9. Write(max{S[i]});

复制代码【参考程序】 [ 本帖最后由 kon3155 于 2009-2-25 14:26 编辑 ]

kon3155

【合唱队形】 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】 输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 【输出文件】 输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 【数据规模】 对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。 【分析】 假设第i位同学为最高个，则对其左边序列求最长递增序列长度，对其右边序列求最长递减序列长度，然后两者相加再减1（因为第i位同学被重复计算了一次）即可得到整个合唱队形的长度。可以利用两次动态规划求解，时间效率为O(N2) 依次枚举每一位同学为最高个，则N次之枚举后得到N个合唱队形长度，取其中最大值，然后(N-合唱队形最大值)即所求。 这样总的时间效率为O(N3)

kon3155

【石子合并】 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 【输入文件】 包含两行，第1 行是正整数n（1<=n<=100），表示有n堆石子。 第2行有n个数，分别表示每堆石子的个数。 【输出文件】 输出两行。 第1 行中的数是最小得分；第2 行中的数是最大得分。 【输入样例】 4 4 4 5 9 【输出样例】 43 54 【分析】 本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子： 6 3 4 6 5 4 2 如果使用贪心法求最小得分，应该是如下的合并步骤： 第一次合并 3 4 6 5 4 2 2,3合并得分是５ 第二次合并 5 4 6 5 4 5,4合并得分是9 第三次合并 9 6 5 4 5,4合并得分是9 第四次合并 9 6 9 9,6合并得分是15 第五次合并 15 9 15,9合并得分是24 总得分＝5＋9＋9＋15＋24＝62 但是如果采用如下合并方法，却可以得到比上面得分更少的方法： 第一次合并 3 4 6 5 4 2 3,4合并得分是7 第二次合并 7 6 5 4 2 7,6合并得分是13 第三次合并 13 5 4 2 4,2合并得分是6 第四次合并 13 5 6 5,6合并得分是11 第五次合并 13 11 13,11合并得分是24 总得分＝7＋13＋6＋11＋24＝61 由此我们知道本题是不可以使用贪心法求解的，上例中第五次合并石子数分别为13和11的相邻两堆。 这两堆石头分别由最初 的第1，2，3堆（石头数分别为3，4，6）和第4，5，6堆（石头数分别为5，4，2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2次合并的得分总和最优。为了实现这一目标，我们将第１个序列又一分为二：第１、２堆构成子序列１，第３堆为子序列２。第一次合并子序列１中的两堆，得分７；第二次再将之与子序列２的一堆合并，得分13。显然对于第１个子序列来说，这样的合并方案是最优的。同样，我们将第２个子序列也一分为二；第４堆为子序列１，第５，６堆构成子序列２。第三次合 并子序列２中的２堆，得分６；第四次再将之与子序列１中的一堆合并，得分13。显然对于第二个子序列来说，这样的合并方案也是最优的。由此得出一个结论──６堆石子经过这样的５次合并后，得分的总和最小。 动态规划思路： 阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N堆合并 状态s：每一阶段中各个不同合并方法的石子合并总得分。 决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案 具体来说我们应该定义一个数组s[i,j]用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s[i,j]为合并的最优得分。 对于上面的例子来说，初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因为一开始还没有合并，所以这些值应该全部为0。 第二阶段：两两合并过程如下，其中sum(i,j)表示从i开始数j个数的和 s[1,2]=s[1,1]+s[2,1]+sum(1,2) s[2,2]=s[2,1]+s[3,1]+sum(2,2) s[3,2]=s[3,1]+s[4,1]+sum(3,2) s[4,2]=s[4,1]+s[5,1]+sum(4,2) s[5,2]=s[5,1]+s[6,1]+sum(5,2) s[6,2]=s[6,1]+s[1,1]+sum(6,2) 第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个为一组 s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3)，取其最优 s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3)，取其最优 . . . 第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。以后第五阶段、第六阶段依次类推，最后在第六阶段中找出最优答案即可。 由此得到算法框架如下： For j←2 to n do {枚举阶段，从两两合并开始计算} For i←1 to n do {计算当前阶段的n种不同状态的值} For k←1 to j-1 do {枚举不同的分段方法} begin If i+k>n then t←(i+k) mod n else t←i+k {最后一个连第一个的情况处理} s[i,j]←最优{s[i,k]+s[t,j-k]+sum[1,3]} {sum[i,j]表示从i开始数j个数的和} end; 【参考程序】