crack the coding interviews 8.5

8.5
Recursive Multiply: Write a recursive function to multiply two positive integers without using
the * operator (or / operator). You can use addition, subtraction, and bit shifting, but you should
minimize the number of those operations

这道题很有意思，我自己的实现因为参考了前面scheme /guile 实现，所以很简单。

//my solution
    public static int multiply(int x,int y){
        if(x==0){
            return 0;
        }
        return y+multiply(x-1, y);
    }

下面是除法的实现，当然想想其实可以多写一个 x==y . 可能会更容易明白，但是意义不大。
limitation: 这个除法和乘法其实都只能计算正数，不能计算负数的。

/* Divide compute a/b with recursion */
    public static int divide(int x, int y){
        if(x < y){
            return 0;
        }else{
            return 1+divide(x-y, y);
        }
    }

/* Divide compute a/b with recursion */
    public static int divide(int x, int y){
        if(x < y){
            return 0;
        }else if(x == y){
            return 1;
        }else{
            return 1+divide(x-y, y);
        }
    }

官方的solution 如下，有3个，我把他们写在了一块。

//solution 1
    static int minProduct(int a, int b){
        int bigger = a< b ? b :a;
        int smaller = a<b ? a :b;
        return minProductHelper(smaller, bigger);
    }

    static int minProductHelper(int smaller, int bigger){
        if(smaller == 0){
            // 0 x bigger = 0
            return 0;
        }else if(smaller == 1){
            // 1 x bigger = bigger
            return bigger;
        }

        //compute half, if uneven , compute other half, if even double it
        int s = smaller >> 1;    //Divide by 2
        int side1 = minProduct(s, bigger);
        int side2 = side1;
        if(smaller % 2 ==1){
            side2 = minProductHelper(smaller-s, bigger);
        }
        return side1 + side2;
    }

    //solution 2
    static int minProduct2(int a, int b){
        int bigger = a > b ? a : b;
        int smaller = a < b ? a : b;
        int memo[] = new int[smaller+1];
        return minProduct2(smaller,bigger, memo);
    }

    static int minProduct2(int smaller, int bigger, int[] memo){
        if(smaller == 0){
            return 0;
        }else if (smaller == 1){
            return bigger;
        }else if(memo[smaller] > 0){
            return memo[smaller];
        }
        //compute half, if uneven, compute other half,if even, double it
        int s = smaller >> 1;        //Divide by 2
        int side1 = minProduct2(s, bigger,memo);        //compute half
        int side2 = side1;
        if(smaller % 2 == 1){
            side2 = minProduct2(smaller -s, bigger, memo);
        }

        //sum and cache
        memo[smaller] = side1+side2;
        return memo[smaller];
    }

    //solution 3
    static int minProduct3(int a ,int b){
        int bigger = a < b ? b : a;
        int smaller = a < b ? a : b;

        return minProductHelper3(smaller, bigger);
    }

    static int minProductHelper3(int smaller, int bigger){
        if(smaller == 0){
            return 0;
        }
        if(smaller == 1){
            return bigger;
        }
        int s= smaller >> 1;        //Divide by 2
        int halfProd = minProduct3(s, bigger);

        if(smaller % 2 == 0){
            return halfProd + halfProd;
        }else{
            return halfProd + halfProd + bigger;
        }
    }

最下面是测试代码

public static void main(String[] args){
        int x = 20;
        int y = 9;
        int a = 18;
        int b = -2;
        int c = -1;

        int answer = multiply(x,y);
        System.out.println("answer is "+answer);
        int answer3 = minProduct3(x,y);
        System.out.println("answer3 is "+answer3);
        int answer2 = minProduct2(x,y);
        System.out.println("answer2 is "+answer2);
        int answer1 = minProduct(x,y);
        System.out.println("answer1 is "+answer1);

        /* compute x / y
         *
         */
        int quotient1 = divide(x,y);
        int quotient2 = divide(a, y);
        int quotient3 = divide(b, c);
        System.out.println("quotient1 is "+quotient1);
        System.out.println("quotient2 is "+quotient2);
        System.out.println("quotient3 is "+quotient3);
    }

负数相除会得到0，因为-2 < -1 .