《算法导论的Java实现》 1_3.1 分治算法

Question

本帖最后由 chen09 于 2010-03-19 23:57:00 编辑

Answer 1

算法学到了，要会运用。比如下面这些很不起眼，甚至可能是不屑一顾的：public static double pow(double base, int exponent);
计算一个 double 的 int 次方，以 O(lgN) 复杂度实现。辗转相除法求两个数的最大公约数大家肯定都会，那如何求三个数的最大公约数呢？

Answer 2

Arrays.copyOfRange 方法是 JDK 6 中新增的。

Answer 3

这题目出得很好！大家可以想一想。答案可以参考我一个月前的一个blogECPP——利用有限域上的椭圆曲线，精确判定素数的算法那篇里面有个用java实现的模幂算法，复杂度为O(lgN)。把“模”相关的去掉，剩下的“幂”，也就是多少次方了。那就是分治算法了，我把求椭圆曲线的次方的函数贴在下面，看看能否给大家以提示：
   1. static public Point multiply(Point p, int x, Line l) throws EllipticException {  
   2.     mapResult.clear();  
   3.     // mapResult.put(1, p);  
   4.     return multiply(p, x, l, mapResult);  
   5. }  
   6. static private Point multiply(Point p, int x, Line l, Map<Integer, Point> mapResult)  
   7.     throws EllipticException {  
   8.     if (x == 1)  
   9.         return p;  
  10.     if (mapResult.containsKey(x))  
  11.         return mapResult.get(x);  
  12.     int half = x / 2;  
  13.     while (half > 0) {  
  14.         try {  
  15.             Point point = plus(multiply(p, half, l, mapResult), multiply(p, x - half, l,  
  16.                 mapResult), l);  
  17.             mapResult.put(x, point);  
  18.             return point;  
  19.         } catch (EllipticException ee) {  
  20.             half--;  
  21.         }  
  22.     }  
  23.     throw new EllipticException("can't multiply " + p + "*" + x + " mod " + l.p);  
  24. }  
请注意15行，典型的分治算法。

Answer 4

不卖关子了，代码源于《Java 数值方法》一书。public class Test {    public static void main(String[] args) {
        double n1 = pow(2, 6);
        double n2 = pow(2, -6);
        System.out.println(n1);
        System.out.println(n2);
    }    public static double pow(double base, int exponent) {
        if (exponent < 0)
            return 1 / pow(base, -exponent);
        double power = 1;
        while(exponent > 0) {
            if((exponent & 1) == 1) {
                power *= base;
            }
            base *= base;
            exponent >>= 1;
        }
        return power;
    }
}

Answer 5

那俺就来解释一下吧。if((exponent & 1) == 1)
可以这么想象，把exponent当成2进制数，那么这个判断就是判断当前最低位是不是1？如果是0，就不用累乘。exponent >>= 1;
就是除以2了

Answer 6

而且刚才发现了个CSDN的BUG 不过不知道是不是啊 通过全部动态我看到的chen09的信息 我点的明明是插入排序 他给我跳到分治算法了..