贪心算法

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解,如之前的Dijkstra算法,Prim算法,Kruskal算法。如果不要求绝对最佳答案,那么有时候我们使用简单的贪婪算法生成近似的答案.

• 贪心与动态规划

贪心算法和动态规划都需求最优子结构,但是贪心算法是自顶向下方式进行,就是每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。最后得到结果.每一步的最优解都依赖上一部的最优解.你只考虑之前已做出的选择
而动态规划通常自底向上解各种子问题,每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解.全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解.你考虑的都是以后的子问题
经典的还是背包问题,之前的01背包问题我们采用动态规划解决而不能用贪心.但是如果改成部分背包问题呢:
假如有三件物品，背包可装50磅的物品，物品1重10磅，价值60元；物品2重20磅，价值100元；物品3重30磅，价值120元。你可以选择带走每个物品的全部或一部分，求如何选择可以使背包所装的价值最大？
注意到不同点是我们可以选择带走一部分,所以使用贪心算法十分自然地想到,先算含金量啊,先把含金量最高的都带完,再带含金量其次的...很容易得到解,带走一件1,一件2,2/3件3...比较简单代码不写.

• 活动安排问题

设有n个活动的集合E = {1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si < fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si >= fj或sj >= fi时，活动i与活动j相容.怎么尽可能地安排多的相容活动呢?
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:

6

  package com.fredal.structure;
import java.util.Arrays;
public class Arrange {
   public static int[] greedyArrangement(int[] start,int[] end){
       int total=start.length;
       int endtime=end[0];//选择的所有活动的最末结束时间
       int[] arrangement=new int[total];
       arrangement[0]=1;//无脑选第一个 最早结束的那个
       int count=1;
       for(int i=0;i<total;i++){
           if(start[i]>endtime){//下一个活动开始时间晚于当前活动结束时间
               arrangement[count++]=i+1;//活动选中
               endtime=end[i];//更新结束时间
           }
       }
       return arrangement;
   }    
   public static void main(String[] args) {
       int[] start={1,3,0,5,3,5,6,8,8,2,12};
       int[] end={4,5,6,7,8,9,10,11,12,13,14};
       int[] arrangement=greedyArrangement(start, end);
       for(int i=0;i<arrangement.length;i++){
           if(arrangement[i]!=0)
               System.out.println("开始时间:"+start[arrangement[i]-1]+",结束时间:"+end[arrangement[i]-1]);
       }
   }
}

• 哈夫曼编码

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示

7

8

9

  package com.fredal.structure;
public class Huffman {
   static MyHeap<Node> heap=new MyHeap<Node>();//堆类
   static class Node implements Comparable<Node>{
       private int weight;//权值 频率
       private String value;//字符
       private Node left;
       private Node right;
       private Node parent;
       private String path;//记录路径
       private boolean isvisited;//是否遍历过
       public Node(int weight, String value) {
           super();
           this.weight = weight;
           this.value = value;
       }
       public int compareTo(Node o) {
           return weight-o.weight;
       }        
   }    
   public static Node bulidHuffman(Node[] nodes){
       for(int i=0;i<nodes.length;i++){
           heap.insert(nodes[i]);
       }
       while(heap.getCurrentSize()>1){
           Node minA = heap.deleteMin();//弹出最小的两个
           Node minB = heap.deleteMin();
           Node sumNode=new Node(minA.weight+minB.weight,minA.value+minB.value);//权值和称为其父节点
           //维护关系
           sumNode.left=minA;
           minA.path="0";//为了方便 直接把路径信息记这儿了
           sumNode.right=minB;
           minB.path="1";
           minA.parent=sumNode;
           minB.parent=sumNode;
           
           heap.insert(sumNode);//插入堆
           
       }
       
       return heap.findMin();//返回最后一个  相当于是完整的树了
   }
   
   public static void printHuffman(Node node){    
       if(node.left!=null && !node.left.isvisited){//遍历左边
           Node left = node.left;
           left.isvisited=true;
           printHuffman(left);
       }
       
       if(node.right!=null && !node.right.isvisited){//遍历右边
           Node right=node.right;
           right.isvisited=true;
           printHuffman(right);
       }
       
       if(node.left==null && node.right==null){//是叶子节点
           StringBuffer sb=new StringBuffer();
           sb.append(node.path);
           System.out.print(node.value+":");
           while(node.parent!=null){
               node=node.parent;
               if(node.path!=null)
                 sb.append(node.path);//访问父节点 获得路径信息
           }
           System.out.println(sb.reverse().toString());//输出
           printHuffman(node);//递归 输出下一个叶子节点的编码
       }
   }
   
   public static void main(String[] args) {
       Node[] nodes={
               new Node(45, "a"),
               new Node(13, "b"),
               new Node(12, "c"),
               new Node(16, "d"),
               new Node(9, "e"),
               new Node(5, "f")
       };
       Node root = bulidHuffman(nodes);
       printHuffman(root);
   }
}

• 近似装箱问题

给定N 项物品，大小为 s1, s2, ..., sN，所有的大小都满足 0 < si < = 1 ；问题是要把这些物品装到最小数目的箱子中去， 已知每个箱子的容量是1个单位；下图显示的是对N项物品的最优装箱方法

10

11

  package com.fredal.structure;
import java.util.LinkedList;
public class BinPacking {
   static LinkedList<Box> boxes=new LinkedList<Box>();//存储所有箱子
   static int index=1;
   
   static class Box{//箱子类
       private double remain;//剩余容量
       private LinkedList<Double> values;
       public Box(){
           remain=1;//设容量初始为1
           values=new LinkedList<Double>();//存储箱子中的物品
       }
   }
   //下项适合算法
   public static void nextfit(double[] a){
       for(int i=0;i<a.length;i++){
           if(boxes.peek()==null)
               boxes.push(new Box());
           Box last = boxes.peek();
           if(last.remain>=a[i]){//装的下就装
               last.values.add(a[i]);
               last.remain-=a[i];
           }else{//装不下就开辟新箱子
               Box nbox=new Box();
               nbox.values.add(a[i]);
               nbox.remain-=a[i];
               boxes.push(nbox);
           }
       }
       
       show(boxes);
   }
   
   //输出显示
   public static void show(LinkedList<Box> boxes){
       while(!boxes.isEmpty()){
           Box box = boxes.removeLast();
           System.out.print("box"+index+++":");
           while(!box.values.isEmpty()){
               Double value = box.values.removeFirst();
               System.out.print(value+" ");
           }
           System.out.println();
       }
   }
   
   public static void main(String[] args) {
       double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
       nextfit(a);
   }
}

下项算法的性能是线性的,但是在实践中显然是不靠谱的.不需要开辟新箱子的时候开辟了新箱子.接下来讲首次适合算法:依序扫描这些箱子把新的一项物品放入足够盛下它的第一个箱子中.

12

  package com.fredal.structure;
import java.util.Iterator;
import java.util.LinkedList;
public class BinPacking {    
   static LinkedList<Box> boxes=new LinkedList<Box>();//存储所有箱子
   static int index=1;
   
   static class Box{//箱子类
       private double remain;//剩余容量
       private LinkedList<Double> values;
       public Box(){
           remain=1;//设容量初始为1
           values=new LinkedList<Double>();//存储箱子中的物品
       }
   }
   //首次适合算法
   public static void firstfit(double[] a){
       for(int i=0;i<a.length;i++){
           boolean flag=false;
           if(boxes.peek()==null)
               boxes.add(new Box());
           Iterator<Box> it = boxes.iterator();
           while(it.hasNext()){//从头到尾遍历 能装就装
               Box box = it.next();
               if(box.remain>=a[i]){
                   box.values.add(a[i]);
                   box.remain-=a[i];
                   flag=true;
                   break;
               }
           }
           if(!flag){//全部不能装就开辟新的
               Box nbox=new Box();
               nbox.values.add(a[i]);
               nbox.remain-=a[i];
               boxes.add(nbox);
           }
       }
       
       show(boxes);
   }
   
   //输出显示
   public static void show(LinkedList<Box> boxes){
       while(!boxes.isEmpty()){
           Box box = boxes.removeFirst();
           System.out.print("box"+index+++":");
           while(!box.values.isEmpty()){
               Double value = box.values.removeFirst();
               System.out.print(value+" ");
           }
           System.out.println();
       }
   }
   
   public static void main(String[] args) {
       double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
       firstfit(a);
   }
}

第三个是最佳适合算法,该方法不是吧一项新物品放入所发现的第一个能够容纳它的箱子，而是放到所有箱子中能够容纳它的最满的箱子中.该算法对随记的输入表现的更好

13

  package com.fredal.structure;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
public class BinPacking {
   static ArrayList<Box> boxes=new ArrayList<Box>();//存储所有箱子
   static int index=1;    
   static class Box{//箱子类
       private double remain;//剩余容量
       private LinkedList<Double> values;
       public Box(){
           remain=1;//设容量初始为1
           values=new LinkedList<Double>();//存储箱子中的物品
       }
   }
   //最佳适合算法
   public static void bestfit(double[] a){
       for(int i=0;i<a.length;i++){
           double remainMin=1+1;//最小的剩余容量 用于寻找最满的箱子 初始化表示比容量大1
           int index=0;//记录箱子编号
           if(boxes.size()==0)
               boxes.add(new Box());
           for(int j=0;j<boxes.size();j++){
               Box box=boxes.get(j);
               if(box.remain>=a[i] && box.remain<remainMin){//从头遍历 如果找到更满的并且能装下的就记录
                   remainMin=box.remain;
                   index=j;
               }
           }
           if(remainMin<=1){//说明找到了可以装的
               Box box = boxes.get(index);//装进记录好的最满的箱子
               box.values.add(a[i]);
               box.remain-=a[i];
           }else{//找不到可以装的就开辟新的箱子
               Box nbox=new Box();
               nbox.values.add(a[i]);
               nbox.remain-=a[i];
               boxes.add(nbox);
           }
       }
       
       show(boxes);
   }
   
   //输出显示
   public static void show(ArrayList<Box> boxes){
       for(int i=0;i<boxes.size();i++){
           Box box=boxes.get(i);
           System.out.print("box"+index+++":");
           while(!box.values.isEmpty()){
               Double value = box.values.removeFirst();
               System.out.print(value+" ");
           }
           System.out.println();
       }
   }
   
   public static void main(String[] args) {
       double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
       bestfit(a);
   }
}

接下来是脱机算法,显然脱机算法可以表现得更好.联机算法的问题在于在于将大项物品装箱困难,特别是当他们在输入的晚期出现的时候.于是脱机算法我们可以将各项物品排序，把最大的物品放在最先，此时我们可以应用首次适合算法或最佳适合算法，分别得到“首次适合递减算法”　和　”最佳适合递减算法”.
这两种算法是差不多的,我们以首次适合递减算法为例.

14

  package com.fredal.structure;
import java.util.Iterator;
import java.util.LinkedList;
public class BinPacking {    
static LinkedList<Box> boxes=new LinkedList<Box>();//存储所有箱子
static int index=1;
static class Box{//箱子类
    private double remain;//剩余容量
    private LinkedList<Double> values;
    public Box(){
        remain=1;//设容量初始为1
        values=new LinkedList<Double>();//存储箱子中的物品
    }
}
//首次适合递减算法
public static void firstfit(double[] a){
    quickSort(a, 0, a.length-1);
    for(int i=0;i<a.length;i++){
        boolean flag=false;
        if(boxes.peek()==null)
            boxes.add(new Box());
        Iterator<Box> it = boxes.iterator();
        while(it.hasNext()){//从头到尾遍历 能装就装
            Box box = it.next();
            if(box.remain>a[i]||Math.abs(box.remain-a[i])<Math.pow(10, -10)){//解决一下精度
                box.values.add(a[i]);
                box.remain-=a[i];
                flag=true;
                break;
            }
        }
        if(!flag){//全部不能装就开辟新的
            Box nbox=new Box();
            nbox.values.add(a[i]);
            nbox.remain-=a[i];
            boxes.add(nbox);
        }
    }
    show(boxes);
}
//快速排序
public static void quickSort(double[] a,int left,int right){
   if(left<right){//递归出口条件
       int i=left;//左指针
       int j=right;//右指针
       double x=a[left];//选择第一个元素作为标尺
       while(i<j){
           while(i<j && a[j]<=x) j--;//从右向左找第一个大于x的数
           if(i<j) a[i++]=a[j];
           while(i<j && a[i]>x) i++;//从左向右找第一个小于等于x的数
           if(i<j) a[j--]=a[i];
       }
       a[i]=x;//插入标尺
       quickSort(a,left,i-1);//递归左边
       quickSort(a, i+1, right);//递归右边
   }
}

//输出显示
public static void show(LinkedList<Box> boxes){
    while(!boxes.isEmpty()){
        Box box = boxes.removeFirst();
        System.out.print("box"+index+++":");
        while(!box.values.isEmpty()){
            Double value = box.values.removeFirst();
            System.out.print(value+" ");
        }
        System.out.println();
    }
}
public static void main(String[] args) {
    double[] a={0.2,0.5,0.4,0.7,0.1,0.3,0.8};
    firstfit(a);
}
}

分治算法

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础.
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法.
传统上,含有两个或以上的递归调用的叫做分治法.经典的例子就是快速排序,归并排序
接下来我们选一些其他的经典例子来分析

• 大整数乘法

设有两个大整数相乘,X=61438521,Y=94736407.那么XY=5820464730934047.易知我么的算法需要O(N²)即O(8²)次操作.
如果我们把X和Y都拆成两半,由最高几位和最低几位组成.那么XL=6143,XR=8521,YL=9473,YR=6470.于是X=XL*10^4+XR,Y=YL*10^4+YR.可以得到
XY=XL*YL*10^8+(XL*YR+XR*YL)*10^4+XRYR
显然这个式子就是由4个乘法组成的,每一个都是原问题的一半,而10^8,104的乘法只是添一些0,于是可以得到递归:T(N)=4T(N/2)+O(N)..
我们按照主定理(相关资料查阅维基百科),可以求得算法复杂度仍然是O(N²).并没有改进这个问题.
观察XL*YR+XR*YL,可以分解为(XL-XR)(YR-YL)+XL*YL+XR*YR,我们仅需要算前面一项,后面的两项已经计算过了.于是得到了T(N)=3T(N/2)+O(N).,按照主定理,可得T(N)=O(N^1.59).当然对于每一个乘积我们还可以继续递归下去,一般到四位数就不用递归了.
我们还是采取代码来模拟过程:

  package com.fredal.structure;
public class BigMultiply {
   //大整数相乘
   public static String multiply(String x,String y){
       int flag1=0;//x的符号位
       int flag2=0;//y的符号位
       if(x.charAt(0)=='-'){//处理符号
           x=x.substring(1);//先把符号位截掉
           flag1=1;
       }
       if(y.charAt(0)=='-'){
           y=y.substring(1);
           flag2=1;
       }
       
       String flag=(flag1^flag2)==1?"-":"";//相乘即异或之后符号位
       
       if(x.length()<y.length())//保证x的位数更大
           return flag+multiply(y, x);
   
       if(x.length()<=4)
           return flag+Integer.parseInt(x)*Integer.parseInt(y);//少于等于四位数直接计算了
       
       if(x.length()%2==0){//x位数是偶数 就把y补成和x一样长
           while(x.length()>y.length())
               y="0"+y;
       }else{//x位数不是偶数 就先把x补成偶数 再把y补成和x一样长
           x="0"+x;
           while(x.length()>y.length())
               y="0"+y;
       }
       
       String xl=x.substring(0,x.length()/2);
       String xr=x.substring(x.length()/2);
       String yl=y.substring(0,y.length()/2);
       String yr=y.substring(y.length()/2);
       
       String D1=minus(xl, xr);//xl-xr
       String D2=minus(yr, yl);//yr-yl
       
       String xlyl=multiply(xl, yl);//xl*yl
       String xryr=multiply(xr, yr);//xr*yr
       
       String D3=add(multiply(D1, D2)+"", add(xlyl, xryr));//D1*D2+Xl*Yl+Xr*Yr
       return flag+add(shift(xlyl, x.length()),add(shift(D3, x.length()/2),xryr));//Xl*Yl*10^n+D3*10^(n/2)+Xr*Yr
   }
   
   //大数相减 带符号处理
   public static String minus(String x,String y){
       int large=compare(x, y);
       String flag=large>=0?"":"-";//加上符号
       if (large==0)
           return "0";
       else if(large>0)//转化成大的减小的
           return minusBigNum(x,y);
       else 
           return flag+minusBigNum(y,x);
   }
   
   //大数相减
   private static String minusBigNum(String x,String y){//大数减小数
       int len=x.length();
       while(len>y.length())
           y="0"+y;
       StringBuilder result=new StringBuilder();
       int flag=0;//表示是否进位
       for(int i=len-1;i>=0;i--){
           int xs=Integer.parseInt(String.valueOf(x.charAt(i)));
           int ys=Integer.parseInt(String.valueOf(y.charAt(i)));
           if(xs+flag>=ys){//别忘了把flag加上
               result.append(xs-ys+flag);
               flag=0;
           }else{
               result.append(10+xs-ys+flag);
               flag=-1;
           }
       }
       return clearZero(result.reverse().toString());
   }
   
   //大数相加
   public static String add(String x,String y){
       if(x.charAt(0)=='-'){//先处理符号
           x=x.substring(1);
           if(y.charAt(0)=='-'){
               y=y.substring(1);
               return "-"+add(x,y);
           }else
               return minus(y, x);             
       }
       
       if(y.charAt(0)=='-'){
           y=y.substring(1);
           return minus(x, y);
       }
       if(x.length()<y.length())
           return add(y, x);//保证x的位数更大
       
       int len=x.length();
       
       while(len>y.length())//补位使位数相等
           y="0"+y;
       
       StringBuilder result=new StringBuilder();
       int flag=0;//表示是否进位
       for(int i=len-1;i>=0;i--){
           int xs=Integer.parseInt(String.valueOf(x.charAt(i)));
           int ys=Integer.parseInt(String.valueOf(y.charAt(i)));
           if(xs+ys+flag>9){//别忘了把flag加上
               result.append(xs+ys-10+flag);
               flag=1;
           }else{
               result.append(xs+ys+flag);
               flag=0;
           }
       }
       if(flag!=0)
           result.append(1);
       return clearZero(result.reverse().toString());
   }
   
   //计算10n次方的 就是后面加0
   public static String shift(String x,int n){
       for(int i=0;i<n;i++){
           x+="0";
       }
       return x;
   }
   
   //消除0
   private static String clearZero(String str){
       int i=0;
       while(i<str.length()&&str.charAt(i)=='0'){
           i++;
       }
       return str.substring(i);
   }
   
   //比较两个数的大小
   private static int compare(String x,String y){
       if(x.length()>y.length())
           return 1;
       else if(x.length()<y.length())
           return -1;
       else{
           int index = 0;
           while (index < x.length() && x.charAt(index) == y.charAt(index))
               index++;
           if (index == x.length())
               return 0;
           else {
               return x.charAt(index) > y.charAt(index)? 1 : -1;
           }
       }
   }
   
   public static void main(String[] args) {
       System.out.println(multiply("-61438521", "94736407"));
       System.out.println(multiply("-3124234254543411432432422238221342421",
               "-2423442342342342342342342323423445345699"));
               
   }
}

算法并不复杂,但是处理符号什么的还是比较麻烦的,而且加法减法啥的都要自己去实现.

• Strassen矩阵乘法

两个矩阵的乘法学过线性代数的都知道怎么求,一般来说复杂度为O(N^3).直接给出标准的算法

  package com.fredal.structure;
public class MartixMultiply {
   public static int[][] multiply(int[][] a, int[][] b) {
       int n = a.length;
       int[][] c = new int[n][n];

       for (int i = 0; i < n; i++)
           // 初始化
           for (int j = 0; j < n; j++)
               c[i][j] = 0;

       for (int i = 0; i < n; i++)
           for (int j = 0; j < n; j++)
               for (int k = 0; k < n; k++)
                   c[i][j] += a[i][k] * b[k][j];

       return c;
   }

   public static void main(String[] args) {
       int[][] a = { { 1, 2 }, { 3, 4 } };
       int[][] b = { { 3, 4 }, { 7, 2 } };
       int[][] c = multiply(a, b);

       System.out.println(c[0][0] + " " + c[0][1] + " " + c[1][0] + " "
               + c[1][1]);
   }
}

Strassen提出了算法打破了O(N^3)的屏障.用到分治算法,把矩阵分为4块.

15

16

17

  package com.fredal.structure;
public class MartixMultiply {
   public static int[][] StrassenMultiply(int[][] a, int[][] b) {
       int[][] result = new int[a.length][b.length];
       if (a.length == 2)
           return multiply(a, b);// 如果是2阶的 就结束递归 用传统方法
       // a的四个子矩阵
       int[][] A00 = divide(a, 1);
       int[][] A01 = divide(a, 2);
       int[][] A10 = divide(a, 3);
       int[][] A11 = divide(a, 4);
       // b的四个子矩阵
       int[][] B00 = divide(b, 1);
       int[][] B01 = divide(b, 2);
       int[][] B10 = divide(b, 3);
       int[][] B11 = divide(b, 4);

       int[][] m1 = StrassenMultiply(addArrays(A00, A11), addArrays(B00, B11));
       int[][] m2 = StrassenMultiply(addArrays(A10, A11), B00);
       int[][] m3 = StrassenMultiply(A00, subArrays(B01, B11));
       int[][] m4 = StrassenMultiply(A11, subArrays(B10, B00));
       int[][] m5 = StrassenMultiply(addArrays(A00, A01), B11);
       int[][] m6 = StrassenMultiply(subArrays(A10, A00), addArrays(B00, B01));
       int[][] m7 = StrassenMultiply(subArrays(A01, A11), addArrays(B10, B11));

       int[][] C00 = addArrays(m7, subArrays(addArrays(m1, m4), m5));// m1+m4-m5+m7
       int[][] C01 = addArrays(m3, m5); // m3+m5
       int[][] C10 = addArrays(m2, m4); // m2+m4
       int[][] C11 = addArrays(m6, subArrays(addArrays(m1, m3), m2));// m1+m3-m2+m6

       // 将四个矩阵合并起来
       Merge(result, C00, 1);
       Merge(result, C01, 2);
       Merge(result, C10, 3);
       Merge(result, C11, 4);

       return result;
   }

   // /分割得到子矩阵
   private static int[][] divide(int[][] a, int flag) {
       int[][] result = new int[a.length / 2][a.length / 2];
       switch (flag) {
       case 1:
           for (int i = 0; i < a.length / 2; i++)
               for (int j = 0; j < a.length / 2; j++)
                   result[i][j] = a[i][j];
           break;
       case 2:
           for (int i = 0; i < a.length / 2; i++)
               for (int j = a.length / 2; j < a.length; j++)
                   result[i][j - a.length / 2] = a[i][j];
           break;
       case 3:
           for (int i = a.length / 2; i < a.length; i++)
               for (int j = 0; j < a.length / 2; j++)
                   result[i - a.length / 2][j] = a[i][j];
           break;
       case 4:
           for (int i = a.length / 2; i < a.length; i++)
               for (int j = a.length / 2; j < a.length; j++)
                   result[i - a.length / 2][j - a.length / 2] = a[i][j];
           break;
       }
       return result;
   }

   // 矩阵加法
   private static int[][] addArrays(int[][] a, int[][] b) {
       int[][] result = new int[a.length][a.length];
       for (int i = 0; i < result.length; i++) {
           for (int j = 0; j < result.length; j++) {
               result[i][j] = a[i][j] + b[i][j];
           }
       }
       return result;
   }

   // 矩阵减法
   private static int[][] subArrays(int[][] a, int[][] b) {
       int[][] result = new int[a.length][a.length];
       for (int i = 0; i < result.length; i++) {
           for (int j = 0; j < result.length; j++) {
               result[i][j] = a[i][j] - b[i][j];
           }
       }
       return result;
   }

   // 将b复制到a的指定位置
   private static void Merge(int[][] a, int[][] b, int flag) {
       switch (flag) {
       case 1:
           for (int i = 0; i < a.length / 2; i++)
               for (int j = 0; j < a.length / 2; j++)
                   a[i][j] = b[i][j];
           break;
       case 2:
           for (int i = 0; i < a.length / 2; i++)
               for (int j = a.length / 2; j < a.length; j++)
                   a[i][j] = b[i][j - a.length / 2];
           break;
       case 3:
           for (int i = a.length / 2; i < a.length; i++)
               for (int j = 0; j < a.length / 2; j++)
                   a[i][j] = b[i - a.length / 2][j];
           break;
       case 4:
           for (int i = a.length / 2; i < a.length; i++)
               for (int j = a.length / 2; j < a.length; j++)
                   a[i][j] = b[i - a.length / 2][j - a.length / 2];
           break;
       }
   }

   // 常规做法
   public static int[][] multiply(int[][] a, int[][] b) {
       int n = a.length;
       int[][] c = new int[n][n];

       for (int i = 0; i < n; i++)
           // Initialization
           for (int j = 0; j < n; j++)
               c[i][j] = 0;

       for (int i = 0; i < n; i++)
           for (int j = 0; j < n; j++)
               for (int k = 0; k < n; k++)
                   c[i][j] += a[i][k] * b[k][j];

       return c;
   }

   public static void main(String[] args) {
       int[][] a = { { 1, 2, 6, 7 }, { 3, 4, 5, 4 }, { 5, 8, 3, 8 },
               { -6, 4, 3, 9 } };
       int[][] b = { { 3, 4, 9, 0 }, { 7, 2, -5, -6 }, { 0, 7, -4, 6 },
               { -6, 3, -5, 4 } };
       int[][] c = multiply(a, b);

       System.out.println(c[0][0] + " " + c[0][1] + " " + c[1][0] + " "
               + c[1][1]);
   }
}

• 最近点对问题

这个问题真的很有意思,给定空间上的n个节点S={(xi,yi)}，如何查找这n个点对中最近的点对的距离?
我们都知道两点间距离:((xi-xj)²+(yi-yj)²)^1/2
那么如果使用暴力搜索,需要两两检测,需要花费O(N²).
我们可以采用分治法的思想.首先我们假设这些点都已经按照x坐标排序过,那么可以在中间画一条线,把点集分为Pl和Pr,那么最近的一对点要么都在Pl中,要么都在Pr中,要么分别在Pl和pr中,把这三个距离分别用dl,dr,dc表示.

18

19

20

21

  package com.fredal.structure;
import java.util.ArrayList;
import java.util.Set;
import java.util.TreeSet;
public class Distance {
   static final int NUM=10;//使用穷举法的点数   
   public static void main(String[] args) {
       Set<Point> testData = new TreeSet<Point>();         
       java.util.Random random = new java.util.Random();  
       for(int i = 0;i < 100000;i++){  
           int x = random.nextInt(100000);  
           int y = random.nextInt(100000);  
           testData.add(new Point(x, y));  
       } 
       Point [] points = new Point[testData.size()];  
       points = (Point[]) testData.toArray(points);
       Point[] result=new Point[2];
       long startTime=System.currentTimeMillis();   //获取开始时间
       result=findpair(points);
       long endTime=System.currentTimeMillis(); //获取结束时间
       System.out.println("最近点: ("+result[0].getX()+","+result[0].getY()
               +")--("+result[1].getX()+","+result[1].getY()+")");
       System.out.println("距离为: "+distance(result[0], result[1]));
       System.out.println("分治法运行时间:"+(endTime-startTime)+"ms");
       long startTime2=System.currentTimeMillis();   //获取开始时间
       result=bong(points);
       long endTime2=System.currentTimeMillis(); //获取结束时间
       System.out.println("穷举法运行时间:"+(endTime2-startTime2)+"ms");
   }    
   //寻找最近点对
   public static Point[] findpair(Point[] p){
       Point[] result=new Point[2];
       if(p.length<NUM)
           return bong(p);
       //开始画线了  求所有点在x坐标的中位数
       int minX = (int) Double.POSITIVE_INFINITY; 
       int maxX = (int) Double.NEGATIVE_INFINITY;
       for(int i = 0; i < p.length; i++){  
           if(p[i].getX() < minX)  
               minX = (int) p[i].getX();  
           if(p[i].getX() > maxX)  
               maxX = (int) p[i].getX();  
       }  
       int midX = (minX + maxX)/2;
       //把以midx为界划分出的点分成两组放到两个表
       ArrayList<Point> L1=new ArrayList<Point>();
       ArrayList<Point> L2=new ArrayList<Point>();
       for(int i = 0; i < p.length; i++){  
           if(p[i].getX() <= midX)       
               L1.add(p[i]);  
           if(p[i].getX() > midX)  
               L2.add(p[i]);  
       } 
       //按x坐标排序
       Point [] p1 = new Point[L1.size()];  
       Point [] p2 = new Point[L2.size()];           
       L1.toArray(p1);  
       L2.toArray(p2);  
       mergeSort(p1, "x");     //按X坐标升序排列  
       mergeSort(p2, "x");     //按X坐标升序排列 
       //递归求p1,p2中最近的两个点
       Point[] result1 = new Point[2];  
       result1 = findpair(p1);
       Point[] result2 = new Point[2];  
       result2 = findpair(p2);
       //求二者中的最小值
       if (distance(result1[0], result1[1])<distance(result2[0], result2[1])) {
           result=result1;
       }else {
           result=result2;
       }
       double distance=Math.min(distance(result1[0], result1[1]),distance(result2[0], result2[1]));
       //开始划分带了  在两个子集中找哪些距离划分线小于d的保存
       ArrayList<Point> L3 = new ArrayList<Point>();   
       for(int i = 0; i < p1.length; i++){  
           if(midX - p1[i].getX() < distance)  
               L3.add(p1[i]);  
       }  
       for(int i = 0; i < p2.length; i++){  
           if(p2[i].getX() - midX < distance){  
               L3.add(p2[i]);  
           }  
       } 
       //将得到的按照y升序排列
       Point [] p3 = new Point [L3.size()];  
       L3.toArray(p3);            
       mergeSort(p3, "y");  
       //然后开始优化的穷举 即比较之后的7个点
       if (p3.length<NUM) {
           Point[] temp= bong(p3);
           if (distance(temp[0], temp[1])<distance&&distance(temp[0], temp[1])!=0) {
               result=temp;
           }
       }else {
           for(int i=0;i<p3.length-7;i++){
               double tempd;
               for(int j=1;j<8;j++){
                   if (i+j>=p3.length) {
                       break;
                   }else {
                       tempd=distance(p3[i], p3[i+j]);
                       if (tempd<distance&tempd!=0) {
                           result[0]=p3[i];
                           result[1]=p3[i+j];
                       }
                   }                 
               }
           }
       }
       return result;
   }    
   //归并排序
   private static void mergeSort(Point[] p, String flag) {
       Point[] result = new Point[p.length];  
       mergeSort(p, result, 0, p.length - 1, flag); 
   }
   private static void mergeSort(Point[] a, Point [] result, int left, int right, String flag){  
       if(left < right){  
           int center = (left + right) >> 1;  
           //分治  
           mergeSort(a, result, left, center, flag);  
           mergeSort(a, result, center + 1, right, flag);  
           //合并  
           merge(a, result, left, center + 1, right, flag);  
       }  
     } 
   private static void merge(Point [] a, Point [] result, int leftPos, int rightPos, int rightEnd, String flag){  
       int leftEnd = rightPos - 1;  
       int numOfElements = rightEnd - leftPos + 1;  
         
       int tmpPos = leftPos;       //游标变量, 另两个游标变量分别是leftPos 和 rightPos            
       while(leftPos <= leftEnd && rightPos <= rightEnd){  
           if(flag.equals("x")){  
               if(a[leftPos].getX() <= a[rightPos].getX())  
                   result[tmpPos++] = a[leftPos++];  
               else  
                   result[tmpPos++] = a[rightPos++];  
           }else if(flag.equals("y")){  
               if(a[leftPos].getY() <= a[rightPos].getY())  
                   result[tmpPos++] = a[leftPos++];  
               else  
                   result[tmpPos++] = a[rightPos++];  
           }else  
               throw new RuntimeException();  
       }       
       while(leftPos <= leftEnd)  
           result[tmpPos++] = a[leftPos++];  
       while(rightPos <= rightEnd)  
           result[tmpPos++] = a[rightPos++];         
       //将排好序的段落拷贝到原数组中  
       System.arraycopy(result, rightEnd-numOfElements+1, a, rightEnd-numOfElements+1, numOfElements);  
   }      
   //穷举法
   private static Point[] bong(Point[] p){
       Point[] result=new Point[2];
       if (p.length<=1) {
           result[0]=new Point(Double.MIN_VALUE, Double.MIN_VALUE);
           result[1]=new Point(Double.MAX_VALUE, Double.MAX_VALUE);
           return result;
       }else{
           double min=distance(p[0], p[1]);
           int start=0;
           int end=1;
           for (int i = 0; i < p.length; i++) {
               for (int j = i+1; j < p.length; j++) {
                   if (distance(p[i], p[j])<min&&distance(p[i], p[j])!=0) {
                       min=distance(p[i], p[j]);
                       start=i;
                       end=j;
                   }
               }
           }
           result[0]=p[start];
           result[1]=p[end];
           return result;
       }
   }    
   //计算距离
   private static double distance(Point p1,Point p2){
       return Math.sqrt((p1.getX()-p2.getX())*(p1.getX()-p2.getX())+(p1.getY()-p2.getY())*(p1.getY()-p2.getY()));
   }
   //用一个类来表示点
   static class Point implements  Cloneable,Comparable<Point>{
       double x,y;
       public Point(double x, double y) {
           super();
           this.x = x;
           this.y = y;
       }
       public double getX() {
           return x;
       }
       public double getY() {
           return y;
       }
       public int compareTo(Point o) {  
           if(x == o.getX() && y == o.getY())  
               return 0;  
           else   
               return 1;  
       }
       public boolean equals(Object p) {
           // TODO 自动生成的方法存根
           if (this.x==((Point) p).getX()&&this.y==((Point) p).getY()) {
               return true;
           }else {
               return false;
           }
       }
   }    
}

我们采用了随机数产生器随机产生点,并统计了分治法与纯粹暴力搜索的运行时间,差距相当明显(这个程序当规模特别大的时候还是会栈溢出,为啥)

22

泊松分酒问题

讲这道题纯粹就是比较好玩,就记录一下.泊松分酒是很著名的一道题,讲的是假设某人有12品脱的啤酒一瓶，想从中倒出六品脱，但是恰巧身边没有6品脱的容器，仅有一个8品脱和一个5品脱的容器，怎样倒才能将啤酒分为两个6品脱呢？
我们用代码模拟很简单的就得到了答案

  package com.fredal.structure; import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
public class Oil {
    static class Status{
         static int[] full={12,8,5};//满的状态
         int[] bottle=new int[3];//瓶子的状态
         Status from;//从哪个状态来的
         
         public Status(int a,int b,int c){
             bottle[0]=a;
             bottle[1]=b;
             bottle[2]=c;
         }
         
         //获取某种状态开始下一步的所有的状态
         public Set opreation(){
             Set res=new HashSet();
             
             //开始倒酒
             for(int i=0;i<bottle.length;i++){
                 for(int j=0;j<bottle.length;j++){
                     if(i==j) continue; //不倒自己
                     if(bottle[i]==0) continue;//自己是空的 不倒
                     if(bottle[j]==full[j]) continue;//对方是满的 不倒
                     
                     Status t=new Status(bottle[0], bottle[1], bottle[2]);
                     t.from=this;//从自己这个状态开始变化
                     
                     //真的开始倒酒了                     t.bottle[j]+=t.bottle[i];
                     t.bottle[i]=0;
                     if(t.bottle[j]>full[j]){//装不下了
                         t.bottle[i]=t.bottle[j]-full[j];//满的倒回去
                         t.bottle[j]=full[j];
                     }              
                     res.add(t);
                 }
             }
             return res;
         }
         
         //是否含有某种状态
         public boolean has2(int x){
            int index=0;
            if (bottle[0]==x) index++;
            if (bottle[1]==x) index++;
            if (bottle[2]==x) index++;
            return index==2?true:false;
         }
         
         public Status getFrom() {
            return from;
        }
         
         public String toString(){
                return "<" + bottle[0] + "," + bottle[1] + "," + bottle[2] + ">";
        }
         
        public int hashCode() {
            return 100;
        }
        
        public boolean equals(Object obj) {
            Status x=(Status)obj;
            return bottle[0]==x.bottle[0]&&bottle[1]==x.bottle[1]&&bottle[2]==x.bottle[2];
        }
    }
    
    public static void main(String[] args) {
        Set<Status> all=new HashSet<Status>();//存放所有结果状态
        all.add(new Status(12, 0, 0));
        
        for(;;){
            Set newset=new HashSet();
            
            for(Status x:all){//所有上一种状态产生所有下一种状态
                Set t = x.opreation();
                newset.addAll(t);
            }
            
            if(all.containsAll(newset)) break;//出口
            all.addAll(newset);
        }
        
        LinkedList<Status> list=new LinkedList<Status>();//存放有6的一溜
        
        for(Status k:all){
            if(k.has2(6)){
                while(k!=null){    
                    list.push(k);
                    k=k.getFrom();//从终止状态开始往上追溯
                }
            }
        }   
        //输出
        while(!list.isEmpty()){
            System.out.println(list.pop());
        }
    }    
}

这个解法找到的其实是最优解,至于为什么呢,其实利用set的方法十分巧妙,结果集set里随着一次次的分酒一次次地扩增,当第一次出现含有两个6的状态的时候,再往前追溯,步骤是最少的!因为这个我们想要的状态是第一次出现.
假如我们每次都打印出all集合,可以知道,当第一次找到含有两个6状态的时候程序并没有结束,因为还没有找到所有的状态.
而后面的状态再进行分酒时,仍有可能产生两个6的状态,但是想要加入set集合的时候就行不通了,所以此程序只输出最早加入的那一个解,并且是最优的.
当然这种算法并不能输出所有的解,如果要得到所有的解,我们可以采用以下算法,这种算法借鉴了图的深度搜索(DFS)以及回溯的技巧,需要注意的是,和8皇后问题一样,需要回溯的时机有两个,出错的时候和找到某一组解的时候.

  package com.fredal.structure;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Oil {
    int[] full = new int[3]; //满状态 容量
    int[] bottle = new int[3]; //瓶子的状态
    int target = 0; //目标
    List<int[]> res = new ArrayList<int[]>();//存放结果
    
    public void opreation(int[] bottle) {
        for(int i=0;i<3;i++) {
            for(int j=1;j<3;j++){//每个瓶子都不往自己倒 总共6种可能性
                int[] temp = bottle.clone();//每次循环都创建临时数组 
                int to=(i+j)%3;//(i+j)%3 是除每种i瓶子外其他两个瓶子的序号,即要倒的目标
                if(temp[i]==0) continue;//自己是空的 不倒
                if(temp[to]==full[to]) continue;//对方是满的 不倒
                
                //开始倒酒
                temp[to]+=temp[i];
                temp[i]=0;
                if(temp[to]>full[to]){//装不下了
                    temp[i]=temp[to]-full[to];//满出来的部分倒回去
                    temp[to]=full[to];
                }
                
                if(had(temp)) continue;//检测是否已经存在相同状态,防止重复

                res.add(temp);//添加到结果链表
                if(has2(temp))    return;//如果找到有两个想要的状态的结果就返回
                opreation(temp);//继续下一次分酒
                res.remove(res.size()-1); //回溯 仔细体会
            }
        }
    }

    //是否以及含有状态
    private boolean had(int[] bottlex) {
        for(int[] e:res)
            if(e[0]==bottlex[0]&&e[1]==bottlex[1]&&e[2]==bottlex[2]) return true;
        return false;
    }

    //检测找到结果
    private boolean has2(int[] bottle) {
        int index=0;
        for(int i=0;i<bottle.length;i++)        
            if(bottle[i]==target) index++;        
        if(index==2){
            show(res);//输出
            res.remove(res.size()-1);//回溯
            return true;
        }
        return false;
    }
    //打印
    private void show(List<int[]> res) {
        for(int[] e:res) {
            System.out.println(e[0] + "," + e[1] + "," + e[2]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Oil o = new Oil();
        Scanner scanner = new Scanner(System.in);
        String s =""; 
        if(scanner.hasNext()) {
            s = scanner.nextLine();
        }
        String[] data = s.split(",");
        int[] d = new int[data.length];
        for(int i=0;i<data.length;i++){
            d[i] = Integer.parseInt(data[i]);
        }
        o.full = new int[]{d[0],d[1],d[2]};
        o.bottle = new int[]{d[3],d[4],d[5]};
        o.target = d[6];
        o.res.add(new int[]{d[3],d[4],d[5]});//添加初始状态
        o.opreation(o.bottle);
    }
    
}

显然,按照深度搜索并不能有效地找到最优解.上面两种算法都是比较巧的,我也比较喜欢.
如果要同时找到所有解和最优解,用图的广度搜索(BFS)会很方便,这也是网上采用的最多的,代码到处都有,就不写了.
更多内容与相关下载请查看扩展阅读