常用算法指南(一)基本算法思想

常用算法指南(一)基本算法思想近期看了《Java常用算法手册》,来总结一下。想看原书的,在这里提供原书链接:《Java常用算法手册.pdf》
前言编码不仅仅是把代码写出来,还要求能够清晰的表达出编码者的逻辑。准确的传递到计算机中执行,被其他编码者轻松阅读。要实现这些,就要有清晰、正确的思想,即编程思想。
编程思想是软件诞生的源泉,当它喷涌而发时,也是优秀软件诞生之时。算法思想亦是如此。对于程序来说,算法是一个程序的设计核心,不论什么项目、什么编程语言。要实现一个程序,都离不开算法。而选择合理的算法,可以大大提高我们程序的运行效率。所以,掌握常用的算法,便是作为一个程序员的重要基本技能。由于本人主要用的是Java语言,所以,本文中说到的各种算法代码示例,均采用Java语言来实现,JDK版本为1.8
1.什么是算法从字面上来说,算法也就是用于计算的方法。是用来解决某些问题的方法。通过这个方法,可以达到想要的计算结果。它就像我们小时候学些的一些数学公式和解题步骤。算法,一般有5个特征:
有穷性:算法的执行步骤、时间、都是有限的。不会无休止的一直执行下去。确切性:算法的每一步都必须有明确的定义和描述。输入:一个算法应该有相应的输入条件,就像我们小时候做的应用题,已知什么什么。来求某个结果,已知部分便是输入条件。输出:算法必须有明确的结果输出。没有结果,那这个算法是没有任何意义的。可行性:算法的步骤必须是可行的,无法执行的则没有意义,也解决不了任何问题2.算法的分类按照算法的应用来分:算法可以分为基本算法、几何算法、加密/解密算法、查找算法、图标数据分析算法等。按照算法的思路来分:算法可以分为递推算法、递归算法、穷举算法、分治算法等。
下面,我们就来讲我们的重点之一:也就是算法思想:
3.常用算法思想穷举算法思想;递推算法思想;递归算法思想;分治算法思想;概率算法思想;3.1 穷举算法思想穷举,言下之意便是根据题目的部分条件确定范围,并在次范围内对所有情况逐一穷尽验证,直到找到那个最符合的解。我们常用的循环遍历,就是用的穷举思想。在此我们用一个经典的鸡兔同笼问题来作为示例。
鸡兔同笼问题
这个问题源于1500年前的《孙子算经》原文如下:今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?
/**\\n * 穷举算法思想\\n * 今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?\\n * 解法:通过题目可以知道,鸡和兔的总数量为0-35只(每个动物都是一个脑袋,这就不用说了吧),\\n * 我们可以假设鸡为0,兔子为35,用鸡的个数*2+兔子的个数*4就可以得到总的脚的数量,如果等于94,那么便是答案,\\n * 如果不等,则鸡的数量+1,兔子数量-1,依次类推,穷举所有情况直到得到答案\\n */\\n public static void enumeratingAlgorithm() {\\n int head = 35, foot = 94;\\n int j;\\n for (int i = 0; i <= 35; i++) {//i代表鸡的数量\\n j = head – i;//j代表兔子的数量\\n if (i * 2 + j * 4 == foot) {\\n System.out.printf("鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。", i, j);\\n return;\\n }\\n }\\n System.out.printf("此题无解!你家鸡和兔子有三只脚的吧?");\\n }在main方法中调用:
enumeratingAlgorithm();输出:
鸡的个数为[ 23 ]只,兔子的个数为[ 12 ]只。3.2 递推算法思想递推算法是一种理性思维模式的代表,根据已有的数据和关系,逐步推导而得到结果,通常是根据前面的一些项得到后面的一些项在此我们用一个经典的兔子产仔问题来作为示例。
兔子产仔问题
这个问题癞子13世纪意大利数学家斐波那契的《算盘书》,问题的大意如下:如果一对两个月大的兔子以后每一个月都可以生一对小兔子,而一对新生的兔子初剩两个月后才可以生小兔子。也就是说,1月份出生,3月份才可以产仔。那么假定一年没有产生兔子死亡事件,问一年后共有多少对兔子?
/**\\n * 递推算法\\n * 如果一对两个月大的兔子以后每一个月都可以生一对小兔子,而一对新生的兔子初剩两个月后才可以生小兔子。\\n * 那么假定一年没有产生兔子死亡事件,问一年后共有多少对兔子?\\n * 解法:\\n * 头两个月,兔子都是只有一对,第三个月是2对,第四个月是3对,第五个月是5对。。。\\n * 由此可以看出。从第三个月开始,每个月的兔子对数,等于前两个月之和。\\n * 所以第n个月的兔子对数为 fₙ = fₙ₋₂ + fₙ₋₁\\n *\\n * @param month 月份\\n */\\n public static int recursiveDeduceAlgorithm(int month) {\\n int f1, f2;\\n if (month == 1

month == 2) {\\n return 1;\\n }\\n f1 = recursiveDeduceAlgorithm(month – 1);//递归调用\\n f2 = recursiveDeduceAlgorithm(month – 2);//递归调用\\n return f1 + f2;//根据fₙ₋₁和fₙ₋₂,推导出fₙ\\n}调用:
int month = 12;\\n int num = recursiveDeduceAlgorithm(month);\\n System.out.println("经过 " + month + " 个月,共有 " + num + " 对兔子。");\\n输出:
经过 12 个月,共有 144 对兔子。3.3 递归算法思想程序调用自身的编程技巧称为递归( recursion)。它通常把一个复杂的问题转换为与原问题相似的规模较小的问题来求解。递归分为直接递归和间接递归。
直接递归 ,在方法中调用自身。间接递归,间接的调用一个方法。比如方法a调用方法b,方法b又调用方法a。递归方法在编写时,要注意使用if语句来在某些情况下强制退出递归返回结果。否则,会形成死循环。无法结束,当然也无法得到实际问题的解使用递归,可以是代码更简洁清晰,可读性更好。如:八皇后问题、汉诺塔问题,阶乘计算,都是很递归适宜的应用场景。在此,我们以求阶乘为例
求阶乘问题
所谓阶乘,就是从1到指定数之间的所有自然数相乘的结果。n的阶乘为:n! = n * (n-1) * (n-2) * ······ * 2 * 1
/**\\n * 递归算法思想\\n * 求阶乘(factorial)问题\\n * n的阶乘为:n! = n * (n-1) * (n-2) * ······ * 2 * 1\\n * 解法,每一项都等于前一项-1,结果也等于之前的结果*前一项-1\\n * 我们这里用int,要注意int的取值范围,不要超过int的上限。\\n * @param n 求n的阶乘\\n * @return n的阶乘\\n */\\n public static int recursiveAlgorithm(int n) {\\n if (n <= 1) {\\n return 1;\\n }\\n return n * recursiveAlgorithm(n – 1);//递归调用\\n}调用:
int n = 8;\\n int result = recursiveAlgorithm(n);\\n System.out.println(n + " 的阶乘为: " + result)输出:
8 的阶乘为: 403203.4 分治算法思想分治算法的基本思想是将一个计算复杂的问题分为规模较小,计算简单的小问题求解,然后综合各个小问题,从而得到最终答案。例如我们常说的合并排序、二分法查找、堆排序、快速排序等,就是典型的分治思想的应用。在此,我们以合并排序为例
合并排序
将待排序数据序列看做有n个长度为1的有序字表组成,他们两两合并,得到长度为2的坐杆有序字表。然后再将这些字表两两合并,得到长度为4的有序子表,直重复到最后字表长度为n,完成排序。
/**\\n * 合并排序\\n * 将待排序数据序列看做有n个长度为1的有序字表组成,\\n * 将他们两两合并,得到长度为2的坐杆有序字表\\n * 然后再将这些字表两两合并,得到长度为4的有序子表,\\n * 一直重复到最后字表长度为n,完成排序。\\n * 此合并方法以二路合并为例,这种排序算法往往需要申请较大的辅助空间,这个辅助空间和待排序原始序列空间一样多。\\n */\\n public static void mergeSort(int a[], int n) {\\n int count = 0;//排序步骤\\n int len = 1;//有序序列的长度\\n int f = 0;//变量f做标志\\n int[] p = new int[n];\\n while (len < n) {\\n if (f == 1) {\\n mergeOne(p, a, n, len);//p合并到a\\n } else {\\n mergeOne(a, p, n, len);//a合并到p\\n }\\n len *= 2;//增加有序序列长度\\n f = 1 – f;\\n count++;\\n System.out.print("第" + count + "步排序结果:");\\n for (int anA : a) {\\n System.out.print(" " + anA);\\n }\\n System.out.print("\\\\n");\\n }\\n if (f == 1) {\\n// for (int h = 0; h < n; h++) {//将p中的数据复制回数组a\\n// a[h] = p[h];\\n// }\\n System.arraycopy(p, 0, a, 0, n);//将p中的数据复制回数组a\\n }\\n\\n }\\n\\n\\n /**\\n * 合并一次,合并一次后的结果主要看b,因为是从a合并到b\\n *\\n * @param a 待合并的序列a,从a合并到b\\n * @param b 待合并的序列b,从a合并到b\\n * @param n 原数组的长度\\n * @param len 有序序列的长度\\n */\\n static void mergeOne(int a[], int b[], int n, int len) {\\n int s = 0;\\n while (s + len < n) {\\n int e = s + 2 * len – 1;\\n if (e >= n) {//最后一段可能少于len个节点\\n e = n – 1;\\n }\\n //相邻有序段合并\\n int k = s, i = s, j = s + len;\\n while (i < s + len && j <= e) {//如果两个有序表都未结束时,循环比较\\n if (a[i] <= a[j]) {//将较小的元素复制的b中\\n b[k++] = a[i++];\\n } else {\\n b[k++] = a[j++];\\n }\\n }\\n while (i < s + len) {//未合并的部分复制到数据b中\\n b[k++] = a[i++];\\n }\\n while (j <= e) {\\n b[k++] = a[j++];\\n }\\n s = e + 1;\\n }\\n if (s < n) {\\n for (; s < n; s++) {\\n b[s] = a[s];\\n }\\n }\\n }\\nmain方法中调用:
int a[] = {118, 101, 105, 127, 112};\\n mergeSort(a, a.length);输出:
第1步排序结果: 118 101 105 127 112\\n第2步排序结果: 101 105 118 127 112\\n第3步排序结果: 101 105 118 127 1123.5 概率算法思想概率算法依照概率统计的思路来求解问题,其往往不能得到问题的精确解,但是在数值计算领域得到了广泛的应用。因为很多数学问题,往往需要通过数值计算来求解近似值。比如,求圆周率π。概率算法大致分为如下4种形式:
数值概率算法;蒙特卡罗(Monte Carlo)算法;拉斯维加斯(Las Vegas)算法;舍伍德(Sherwood)算法;这里,我们以蒙特卡罗算法求圆周率为例
蒙特卡罗算法

/**\\n * 蒙特卡罗算法\\n * 蒙特卡罗算法计算圆周率\\n * 一个半径为1的圆,(如图6-23)阴影部分面积,也就是四分之一的圆的面积\\n * 计算公式,s₁=s/4=(π*r²)/4=π/4\\n * 而图中的正方形面积为S₂=r²=1;\\n * 按照图中建议一个坐标系,均匀的向正方形内撒点,那么落入阴影部分的点数比上全部的点数应该就是s₁/S₂=π/4\\n * 根据概率统计的规律,只要撒点足够多,那么将得到近似的结果。这就是蒙特卡罗算法\\n *\\n * @param n 撒点数\\n */\\n public static void monteCarloPI(int n){\\n double PI;//圆周率π\\n int valid = 0;//有效点数,也就是落入阴影部分的点数\\n Random random=new Random();\\n for(int i = 0; i < n; i++){\\n double x = random.nextDouble();//产生0~1之间的一个随机数\\n double y = random.nextDouble();\\n if((x * x + y * y) <= 1){//点在有效区域内,根据图,有效点距离原点的距离小于等于1,也就是x²+y²<=1\\n valid++;\\n }\\n }\\n PI = 4.0 * valid/n;\\n System.out.printf("撒点数:%d,有效点数%d,圆周率π ≈ %12.10f\\\\n", n, valid, PI);\\n }\\n\\n调用:
for(int i = 500000; i < 800000; i+=50000){\\n monteCarloPI(i);\\n }输出:
撒点数:500000,有效点数392927,圆周率π ≈ 3.1434160000\\n撒点数:550000,有效点数432508,圆周率π ≈ 3.1455127273\\n撒点数:600000,有效点数471560,圆周率π ≈ 3.1437333333\\n撒点数:650000,有效点数510239,圆周率π ≈ 3.1399323077\\n撒点数:700000,有效点数549782,圆周率π ≈ 3.1416114286\\n撒点数:750000,有效点数589209,圆周率π ≈ 3.1424480000可以多次执行程序,会发现撒点数越多,圆周率π的精确度也就越高,同时,这种计算方法有很大的随机性,每次运行,即使撒点数相同,结算的结果也不尽相同。
基本算法思想就些,下一章,我们将会总结排序算法。