深入理解编程与算法

孤独一兵 2016-11-28

展开全文

－1－

算法Algorithm是为了解决一个特定的问题而精心设计的一套数学模型以及在这套数学模型上的一系列操作步骤，这些操作步骤是将描述的输入数据逐步处理、转换，并最后得到一个确定的结果。

算法是一个定义明确的计算过程，可以一些值或一组值作为输入并产生一些值或一组值作为输出。因此算法就是将输入转为输出的一系列计算步骤。

算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

简而言之，算法就是可完成特定任务的一系列步骤，它应该具备三大特征：有限、指令明确、有效。

在数学和计算机科学之中，算法（Algorithm）为一个计算的具体步骤，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

算法都遵循特定的方法和模式，就算法的模式而言，处理各种求最优解问题时，人们常用贪婪法、动态规划法等算法模式，处理迷宫类问题时，穷举式的枚举和回溯是常用的模式。

就算法的实现方式而言，如果算法需要频繁地查表操作，那么数据结构的设计通常会选择有序表来实现；反过来，当设计的算法用到了树和图这样的数据结构时，含有递归结构的方法就常常伴随它们左右。

－2－算法要素

2.1 数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：

算术运算：加减乘除等运算
逻辑运算：或、且、非等运算
关系运算：大于、小于、等于、不等于等运算
数据传输：输入、输出、赋值等运算

2.2 算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。

算法也是程序，千姿百态的算法也是由顺序、循环和分支跳转这三大基础结构的。

循环被认定义为在算法中只出现一次但是却有可能被执行多次的一段逻辑体。一般由三部分组成；循环初始化、循环体和循环条件（退出条件），循环条件可以是简单的计数器，也可以是复杂的逻辑判断，它定义循环的执行条件和退出条件。有少数编程语言提供一些特殊的指令，可以控制循环结构的流程和退出，比如C语言的Continue和Break语句。

从数据结构方面来看，涉及线性表的遍历和查找操作，一般会用到循环结构，如果算法操作的数据结构是二维数组，通常都会用到两重循环。

顺序结构可以解决计算、输入和输出等问题，但是不能做判断和选择。正是因为有了分支和选择，程序才能够产生多种多样的结果，一般一个分支对应一个处理流程。

分支结构可以分为单分支结构，双分支结构和嵌套分支结构及多分支结构。根据分支条件判断的结构，分支流程可能被执行一次，也可能不被执行。双分支结构适合那种非真即假的互斥流程，执行一个分支就不会执行另一个分支。多分支结构的每个分支流程也是互斥执行的。switch-case结构的优点是对分支条件只进行一次判断就可以决定代码的分支流程，避免多次判断分支条件，但是缺点就是不能进行复杂的条件判断，比如C语言的switch-case结构，其分支判断条件就只支持整数类型的常量表达式。

－3－了解算法的8个要点

3.1 算法是程序设计的“熟语”（常见短语）,有大算法与有小算法；

3.2 算法中解决问题的步骤是明确且有限的；

3.3 计算机不靠直觉而是机械地解决问题；（就是简单傻瓜式地一步一步做）；

3.4 了解并应用典型算法；

3.5 利用计算机的处理速度；无论是多么冗长繁琐的步骤，只要明确并且机械就能优秀的算法；

3.6 使用编程技巧提升程序执行速度；也就是说解决问题的方法是可以优化的，就像做事有方法，效率就会高一样，算法也是可以优化的；

3.7 找出数字间的规律；因为在计算机中所有的信息都可以用数字表示，因此构造算法，就可以利用到存在于数字间的规律。规律+逻辑；

3.8 先在纸上考虑算法；也就是先在纸上把步骤用文字或图形表示出来，用简单的数字先做验证；

－4－基本算法

4.1.递推法

递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。

递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

递推算法适合有着明显公式规律的场合，如斐波那契数列；

递归算法可以简化代码编写，提高程序的可读性，但是，有的适合不合适的递归往往导致程序的执行效率低。

理解递归最常用的一个例子是编写程序求阶乘问题。

4.2 递归法

程序调用自身的编程技巧称为递归（ recursion）。　一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：

(1) 递归就是在过程或函数里调用自身;

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

4.3 穷举法

穷举法，或称为暴力破解法、枚举法，是“不是办法的办法”，“最后的办法”。其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

I 确定问题的解（或状态）的定义，解空间的范围以及解的判定条件；

II 根据解空间的特点选择搜索策略，一一检验解空间的候选解是否正确，必要时可辅助一些剪枝算法，排除一些明显不可能是正确解的检验过程，提高穷举的效率。

穷举算法Exhaustive Attack method是最简单的一种算法，其依赖于计算机的强大计算能力，来穷尽每一种可能的情况，从面达到求解问题的目的。

穷举法虽然效率不高，但是适合于一些没有明显规律可循的场合。如采用穷举法解决“鸡兔同笼”问题；

4.4 贪心算法(Greedy algorithm)

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。　贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。　对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。　一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。

贪婪法和动态规划法以及分治法一样，都需要对问题进行分解，定义最优解的子结构，但是，贪婪法和其他方法最大的不同在于，贪婪法每一步选择完后，局部最优解就确定了，不再进行回溯处理，也就是说，每一个步骤的局部最优解确定以后，就不再进行修改，直到算法结束。因为不需要进行回溯处理，贪婪法只在很少的情况下可以得到真正的最优解，比如最路径问题，图的最小生成树问题，大多数情况下，由于选择策略的“短视”，贪婪法错过真正的最优解，得不到问题的真正答案。但是贪婪法简单高效，省去了为找最优解可以需要的穷举操作，可以得到与最优解比较接近的近似解。通常作为其他算法的辅助算法使用。

如某国发行的倾向是25分、20分、5分和1分四种硬币，这时候找41分的最优策略是2枚20分的硬币加一枚1分的硬币；但是使用贪婪法得到的结果却是1枚25分硬币、三枚5分硬币和一枚1分硬币。

4.5 分治法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征：

(1) 该问题的规模缩小到一定的程度就可以容易地解决

(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

(3) 利用该问题分解出的子问题的解可以合并为该问题的解；

(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

分治算法是一种化繁为简的算法思想，分治算法往往应用于计算比较复杂的问题，通过将问题简化而逐步得到结果。

4.5.1 对于一个规划为N的问题，若该问题可以容易地解决（比如说规模N较小），则直接解决；否则执行下面的步骤；

4.5.2 将该问题分解为M个规律较小的子问题，这些子问题互相独立，并且与原问题形式相同；

4.5.3 递归地解这些子问题；

4.5.4 然后，将各子问题的解合并得到原问题的解。

如在一堆硬币中寻找一枚假硬币；

快速排序，定义一个标靶，将数据分成两组，每组分别排序，然后合并。

4.6 动态规划法（Dynamic Programming）

是解决多阶段决策问题常用的最优理论。动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优决策，最终堆叠出多阶段决策的最优化决策结果。

动态规划法将问题细分为一系列子问题，从而隐含地探查了所有可能解的空间。

分治法要求子问题是互相独立的，以便分别示解并最终合并原始问题的解。但是动态规划法的子问题不是互相独立的，以便分别求解并最终合并出问题的解，一般包含四个步骤：

定义最优子问题；
定义状态；
定义决策和状态转换方程；
确定边界条件；

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

4.7 迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

4.8 分枝界限法

分枝界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。　与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。

4.9 概率算法

依照概率统计的思路来求解问题，其往往不能得到问题的精确解，但是在数值计算领域得到了的应用。因为很多数学问题，往往没有或者很难计算解析，这时候便需要通过数值计算来求解近似值。

I 将问题转化为相应的几何图形S，S的面积是容易计算的，问题的结果往往对应几何图形中某一部分S1的面积；

II 然后，向几何图形中随机撒点；

III 统计几何图形S中和S1中的点数；根据S的和S1面积的关系以及各图形中的点数来计算得到结果；

VI 判断上述结果是否在需要的精度之内，如果未达到精度则进行执行步骤（2）。如果达到精度，则输出近似结果。

如蒙特卡罗pi算法；

import java.util.Scanner;
public class MontePI{
static double MontePI(int n){
double PI;
double x,y;
int i,sum;
sum=0;
for(i=1;i
x=Math.random();
y=Math.random();
if((x*x+y*y)<=1){
sum++;}}
PI=4.0*sum/n;88
return PI; }
public static void main(String[] args){
int n;
double PI;
System.out.println('蒙特卡罗概率算法计算PI：');
Scanner input=new Scanner(System.in);
System.out.print('输入点的数量：');
n=input.nextInt();
PI=MontePI(n);
System.out.println('PI='+PI); }}

在各算法问题中，排序算法是最基本的问题。对于一个排序好的序列来说，在查找最大值、最小值、遍历、计算和求解等各种操作都十分方便；

排序虽然看似是一个很简单的问题，但当面对庞大的数据时，考虑到效率和速度的因素，往往需要选择一种高效的排序方法，因此便演变出了多种排序算法；

交换（冒泡、快速）、选择（选择、堆）、插入（插入、Shell)、合并排序,直接对计算机内存中的数据进行排序。而对于一些大的文件，由于计算机的内存有限，往往不能直接将其读入内存排序。这时可以采用多路归并排序法，将文件为几个能够读入内存的小部分，然后分别读入进行排序，经过多次处理便可以完成大文件的排序。

－5－算法分类

5.1 按照应用分