本文共 3369 字，大约阅读时间需要 11 分钟。

回溯法：

回溯法（英语：backtracking）也称试探法，回溯法有“通用的解题方法”之称。它可以系统的搜索一个问题的所有解或者任意解。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点

出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过

对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，

只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较

大的问题。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

1 .找到一个可能存在的正确的答案。

2. 在尝试了所有可能的分步方法后宣告该问题没有答案。

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

回溯法-八皇后问题：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

可能是最好的八皇后问题博客：

package com.algorithm.queen;import java.util.Date;/** * 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击， * 即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 * 下面使用递归方法解决 * */public class EightQueen {    private static final short N=16;        //使用常量来定义，方便之后解N皇后问题    private static int count=0;            //结果计数器    public static void main(String[] args) {        Date begin =new Date();        //初始化棋盘，全部置0        short chess[][]=new short[N][N];        for(int i=0;i
   
    =0){            if(chess[row-step][col]==1)                //中上                return false;            if(col-step>=0 && chess[row-step][col-step]==1)        //左上                return false;            if(col+step
   

约瑟夫杀人法：

约瑟夫将军抓到一群俘虏，需要剩下一个人回去给敌军报信。让俘虏围成一圈，从1数数，数到某个数时，杀掉一个人，重新开始从1数数。直到剩下一个人。

约瑟夫杀人法Java实现：

package com.algorithm.joseph;public class Joseph {    private static int MAXNUM=20;    private static int NUM=5;    class Node{        private int value;        private Node nextNode;        public Node(int value){            this.value=value;        }    }    public void killNode(){        //建立循环单链表        Node head=new Node(1);        Node x=head;        for(int i=2;i<=MAXNUM;i++){             x.nextNode=new Node(i);             x=x.nextNode;        }//        head=x.nextNode;注意顺序，报错        x.nextNode=head;        while(x!=x.nextNode){            //x在20的位置            for(int i=1;i

大数相乘：

所谓大数相乘（Multiplication algorithm），就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。

大数相乘Java实现：

package com.algorithm.bigcount;/** * 大数相乘：将较大数字相乘转化为字符串和数组处理。 */public class BigCountMultiply {    public static void main(String[] args) {        String str1="753656566859769";        String str2="9518598598486568654";        //字符串反转，希望后面生成的数组位置0对应个位，位置1对应十位,位置2对应百位.....        str1=reserve(str1);        str2=reserve(str2);        int len1=str1.length();        int len2=str2.length();        int len=len1+len2+3;        char[] chars=new char[len];        char[] chars1=str1.toCharArray();        char[] chars2=str2.toCharArray();        int a[]=new int[len1];        int b[]=new int[len2];        int c[]=new int[len];        for(int i=0;i
   
    0){//判断是否需要进位                //更高位置进位                c[i+1]+=c[i]/10;            }            //取该位置对应数字            c[i]=c[i]%10;        }        int m=0;        for(int i=len-1;i>=0;i--){            //数组下标对应较高位置，即结果较高位数可能有多个0，不需要遍历应去除            if(c[i]>0){               m=i;               break;            }        }        //从结果最高不为0位置开始遍历        for(int i=m;i>=0;i--){            System.out.print(c[i]);        }    }    private static String reserve(String str1) {        if(str1==null||str1.length()==1){            return str1;        }else {            return reserve(str1.substring(1))+str1.charAt(0);        }    }}输出：7173754341051596127319080809080926
   

转载地址：http://trpqb.baihongyu.com/