经典算法普及——基础篇

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<L<10000）。
【输出文件】capital.out
仅一个数，表示交通中心城市的编号

【样例数据】  
【输入】capital.in
5 5
1 2 1
1 5 6
2 3 2
2 4 1
4 5 2
【输出】capital.out
2


【参考程序查看】

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

kon3155

【最短路径问题】
    下图给出了一张地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度，求从A地到E地的最短路径。


【分析】本题可以利用深度搜索法求解，伪代码如下：
var
  s:未访问的城市集合;
  dist[i,j]:存储任意两个城市间的距离数组; {0表示不连通}

1. 
   
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.
    
21. 
    

复制代码

【效率评价】采用深度搜索的时间复杂度是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，得到如下算法：

1. 
   
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<i且Aj<Ai。如果这样的元素存在，那么对所有Aj,都有一个以Aj为末元素的最长递增子序列的长度S(j)，把其中最大的S(j)选出来，那么S(i)就等于最大的S(j)加上1，即以Ai为末元素的最长递增子序列，等于以使S(j)最大的那个Aj为末元素的递增子序列最末再加上Ai；如果这样的元素不存在，那么Ai自身构成一个长度为1的以Ai为末元素的递增子序列。
    阶段i:以第i个数为末元素
    状态S(i):以第i个数为末元素的可能递增序列长度
    转移方程：S(i+1)←max{S(i)}+1
【算法】

1. 
   
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，Ti>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;

【参考程序】