|
算法是一组(有限个)规则，它为某个特定问题提供了解决问题的运算序列；也就是计算机解题的过程，在这个过程中，无论是形成解题思路还是编写程序， 都是在实施某种算法；前者是推理实现的算法，后者是操作实现的算法。下面就常用的一些算法来进行分析。
计算机解题的核心是算法没汁。一个算法应该具有以下五个重要特征：(1)有穷性：一个算法必须保证执行有限步之后结束；(2)确切性：算法的每一步骤必须确切定义；(3)输入：一个算法有0个或多个输入，所谓0个输入是指算法本身定出初始条件；(4)输出： 一个算法有一个或多个输出，以反映对输人数据加工后的结果，没有输出的算法是毫无意义的；(5)能行性：算法原则上能够精确地运行，做有限次即可完成。
常见的基本算法：
1)递推法，递推法实际上是一种递推关系，就是为了得到问题的解，把它推到比原问题简单的问题求解，可分为顺推法和倒推法。
i.顺推法，就是先找到递推关系式，然后从初始条件出发，一步步地按递推关系式递推，直至求出最终结果。
例：求斐波那契数列第10项。
已知斐波那契数列第1项为1，第2项也为2，递推关系是当前项等于前2项之和。F[n]=f[n-1]+f[n-2] (n≥3)。
F[1]:=1;
F[2]:=2
for m:=3 to 10 do
f[m]:=f[m-1]+f[m-2];
writeln(f[10]);
ii.倒推法，就是在不知道初始条件的情况下，经某种递推关系而获知问题的解，再倒过来，推知它的初始条件。
例：一辆重型卡车想穿过800公里的沙漠，已知卡车每公里耗油1升，卡车总载油能力为400升，显然卡车装满一次油是无法穿越沙漠的，因此卡车司机需要在沿途建立几个储油点，使卡车能够顺利穿越沙漠。试问司机需要沿途建立几个储油点？每个储油点存储多少汽油，才能让卡车以消耗最少的汽油穿越沙漠。
用倒推法来解决这个问题，从终点向起点倒推，逐一求出每个贮油点的位置及存油量。为了消耗最少的汽油，最后一个储油点应该离终点400公里，且此处储油400升，即储油点m=1处离终点dis[1]=400公里，储油oil[1]=400升；为了在m=1处储400升汽油，卡车最少从储油点m=2处开两趟载满油的车到储油点m=1处，则储油点m=2处储油oil[2]=400*2=800升，离终点dis[2]=dis[1]+400/3公里（储油点m=2处到储油点m=1处开两趟需要开三次路程）；为了在储油点m=2处储800升汽油，卡车最少从储油点m=3处开两趟载满油的车到储油点m=2处，则储油点m=3处储油oil[3]=400*3=1200升，离终点dis[3]=dis[2]+400/5公里（储油点m=3处到储油点m=2处开三趟需要开五次路程）；依次类推，为了在m=k处储oil[k]=k*400升汽油，卡车最少从m=k+1处开k趟满载车至m=k处，则储油点m=k+1处储油oil[k+1]=(k+1)*400，从m=k+1处至m=k处两地往返2k+1次路程，用总耗油最省方法要求400升，则储油点离终点dis[k+1]=dis[k]+400/(2*k+1)，最后，反推至m=n至起点距离为800-dis[n]，储油为n*400升，为了在m=n处储n*400升汽油，卡车最少从起点开n+1次满载车至m=n处，需要开2*n+1次路程，总耗油量为(800-dis[n])*(2*n+1)，即起点储油为oil[n]+(800-dis[n])*(2*n+1)=n*400+(800-dis[n])*(2*n+1)。
程序段如下：
k:=1;
dis[1]:=400; {从m=1处开始倒推}
oil[1]:=400
repeat
dis[k+1]:=dis[k]+400/(2*k+1);
k:=k+1;
oil[k]:=k*400;
until dis[k]>=800;
dis[k]:=800;
oil[k]:=(k-1)*400+(800-dis[k])*(2*k+1);
for m:=0 to k-1 do
writeln(800-dis[k-m],oil[k-m]);
2)递归法，递归算法本质上将较复杂的处理归结为简单处理，直到最简单的处理，在处理的递归调用过程中，系统用堆栈把每次调用的中间结果保存在栈区，直至求出最简值，然后返回调用函数，返回过程中，中间结果相继出栈恢复，它的执行效率相对比较低。
例：求斐波那契数列第10项。
已知斐波那契数列第1项为1，第2项也为2，关系式是当项等于前2项之和，F[n]=f[n-1]+f[n-2] (n≥3)。
function fib(n:integer):integer;
begin
if n=1 then fib:=1
else if n=2 then fib=2
else
fib:=fib(n-1)+fib(n-2)
end;
使用时调用fib(10)求第10项的值
3)穷举法，从是将所有存在的条件都测试一次，求出正确的结果，它的执行效率是最低的。
例：背包问题，有一个背包，可以放Wm公斤物品，现有n件物品，第I件物品的重量是Wi公斤，价值为Vi元（1≤i≤n），现要求在包内放在若干件物品，使包内物品总价值最大。
使用穷举法，将物品放入包所有可能情况(2n-1)都计算一遍，再考虑背包的最大存放重量Wm，在满足条件的情况下，计算包内物品的总价值，求解出总价值最大的情况。
使用一个N位二进制的计数器，来表示N个物品放入包的情况，第i位上的0表示第i件没有放入包，1表示第i件放入包。根据物品情况计算物品的总重量，若没有超过包的限重，记录下此情况下的总价值，使用提高门槛法判断此时情况是否为已测试条件下总价值最大，若是则记录下此时的总价值，从1测试到2n-1种的情况，此算法的执行效率最低，但一定可以求出最优解。
4)贪心法，从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：i.不能保证求得的最后解是最佳的；ii.不能用来求最大或最小解问题；iii.只能求满足某些约束条件的可行解的范围。
用贪心法来求背包问题，为了使包内物品的总价值最大，先计算出所有物品的单位价值，然后从单位价值从高到低依次选择物品放入包，在不超过限重的情况下尽可能放更多的物品。
例：背包最大限重100公斤，各物品重量、价值如下表：
|
物品
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
重量（公斤）
|
35
|
30
|
60
|
50
|
40
|
10
|
25
|
|
价值(元)
|
10
|
40
|
30
|
50
|
35
|
40
|
30
|
|
单位价值(元/公斤)
|
0.29
|
1.33
|
0.5
|
1
|
0.88
|
4
|
1.2
|
按局部贪心的方法，各物品单位价值从高到低分别6、2、7、4、5、3、1，选取物品6、物品2、物品7、物品1，总重量恰好100公斤，总价值有120元。而事实上这并不是最优解，最优解是物品6、物品2、物品4，总重量虽然为90公斤，但总价值有130元。因此使用局部贪心的方法难以达到全局最优解动态规划设计方法可以解决，一般采用动态规划设计方法解决此问题。
5)分治法，对问题分而治之，将原问题一次或者多次分成N个规模较小的而结构与原问题相似的问题，递归地解这些子问题，然后合并其结果就得到原问题的解。用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作问题来确定的。当N=2又称为二分法。
例：对序列A[1]、A[2]…A[n]进行合并排序。
输入：n，A[1]、A[2] …A[n]
输出：排序后的A[1]、A[2] …A[n]
合并排序的算法就是二分法，先将N个元素分解成两个子序列，再用合并排序法对两个子序列分别排序，如果子序列长度不为1的话，再进行分解成两个子序列，然后再用合并排序法对两个子序列分别排序，当其长度为1时递归结束，然后将两个子序列合并，返回递归调用，再合并…最后就得到结果。
若序列为(5,3,17,9,4,1,8)进行合并排序的过程为：
6)模拟法，模拟法就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化。一般题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法。
例：求圆周率，在一个单位正方形有1/4圆弧，随机产生N个坐标点，统计出现在圆弧内的点的次数M，根据概率，当N足够大时，出现的次数M/N接近π/4，通过计算M/N*4的值来近似求出π。
假计N为10000次
randomize;
n:=0;
m:=0;
while n<10000 do
begin
x:=random;
y:=random;
if x*x+y*y<=1 then m:=m+1;
n:=n+1;
end
writeln(m/n*4);
7)简单搜索，搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但需要庞大的空间需求量。
例：在“走迷宫”的时候，一般回溯法(深度优先搜索)思路是这样的：
a、这个方向有路可走，我没走过
b、往这个方向前进
c、是死胡同，往回走，回到上一个路口
d、重复第一步，直到找着出口
按广度优先搜索思路是：
a、走一步，将下一步所有可走且没有走过的路口放入队列
b、从队列取下一个路口
c、重复第一步，直到找着出口
回溯法很容易实现，但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨。我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？使用剪枝的算法，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。
例：求解九宫数字魔方。在搜索解过程中，我们分析因为每行、列的三个数相加均为15，则可将1～9个数分为三组1～3、4～6，7～9，从每组中取出一个组成一行或一列，再分析，组成和为15的组合只有8种，1+5+9、2+6+7、1+6+8、3+4+8、2+4+9、3+5+7、2+5+8、4+5+6，再分析，可以发现九宫最中间的数必为5，通过这样的分析，就可以从搜索过程中剪去许多没有用的枝条，从而大大提高搜索效率。
8)动态规划，动态规划是建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪心算法或分治法无法解决的问题。和贪心算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心算法中，每采用一次贪心准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。
动态规划的设计过程一般分为三个步骤：
a、 按照最优解的结构设计状态转移方程
b、按照自上而下或者自下而上的方式计算最优解的值
c、 按照求解途径给出最优解的形成过程
例:某人购置了一辆卡车，从事个体运输业务。给定以下各有关数据:
R[t]，t=1,2,...,k，表示已使用过 t 年的卡车，再工作一年所得的运费，它随 t 的增加而减少，k (k≤20) 年后卡车已无使用价值.。 U[t]，t=1,...,k，表示已使用过 t 年的卡车，再工作一年所需的维修费， 它随 t 的增加而增加。C[t]，t=1,2,...,k，表示已使用过 t 年的旧卡车，卖掉旧车，买进新车，所需的净费用，它随 t 的增加而增加。以上各数据均为实型，单位为"万元"。
设某卡车已使用过 t 年,
① 如果继续使用，则第 t+1 年回收额为 R[t]-U[t],
② 如果卖掉旧车,买进新车，则 第 t+1 年回收额为 R[0]-U[0]-C[t] . 该运输户从某年初购车日起,计划工作 N (N<=20) 年，N 年后不论车的状态如何，不再工作。为使这 N 年的总回收额最大，应在哪些年更新旧车? 假定在这 N年内，运输户每年只用一辆车，而且以上各种费用均不改变。输入: 用文件输入已知数据，格式为:
第 1 行: N (运输户工作年限)
第 2 行: k (卡车最大使用年限，k≤20 )
第 3 行: R[0] R[1] ... R[k]
第 4 行: U[0] U[1] ... U[k]
第 5 行: C[0] C[1] ... C[k]
输出: 用文本文件按以下格式输出结果:
第 1 行: W ( N 年总回收额 )
第 2--N+1 行: 每行输出 3 个数据:
年序号
( 从 1 到 N 按升序输出 );
是否更新
( 当年如果更新,输出 1，否则输出 0);
当年回收额 ( N 年回收总额应等于 W ).
例: 设给定以下数据:
N=4， k=5,
i:
0 1 2
3 4 5
R[i]: 8
7 6 5
4 2
U[i]: 0.5
1 2 3 4
5
C[i]: 0
2 3 5 8 10
则正确的输出应该是
24.5
1 0 7.5
2 1 5.5
3 1 5.5
4 0 6.0
【分析】这是动态规划的一个典型的例题.由题意可知,用过t年的卡车,继续使用一年的收益为d[t]=R[t]-U[t],更换新车后一年的收益为e[t]=R[0]-U[0]-C[t]。我们采用倒推分析的方法.F[j,t]表示已经使用了t年的卡车，在第j年不论继续使用还是更新,到第N年为止,可能得到的最大收益。规定当j>N时，F[j,t]≡0。如果在第j年更新,则收益为p=e[t]+F[j+1,1];
如果仍使用旧车,则收益为
q=d[t]+F[j+1,t+1]。这里,e[t]或d[t]为第j年的收益，F[j+1,1]或F[j+1,t+1]为从第j+1年到第N年在不同条件下的最大收益.显然,F[j,t]=Max(p,q).这就是所需要的计算公式.在下面的程序中,数组g[j,t]用于记录使用过t年的车,在第j年的选择方案,g[j,t]=1表示更换新车,g[j,t]=0表示仍使用旧车.
|
