java - 二进制乘法 - 农民算法

Question

我在十进制数上尝试了二进制乘法技术。

算法:

要将两个十进制数 x 和 y 相乘，请将它们写在每个数的旁边 其他，如下例所示。然后重复以下操作:将第一个数字除以 2， 向下舍入结果(即，如果数字是奇数，则去掉 :5)，然后加倍 第二个数字。继续直到第一个数字下降到 1。然后删除所有行 其中第一个数字是偶数，并将第二列中剩余的内容相加。

11 13

5 26

2 52

1104

........

143(答案)

代码:

class Multiply
{
static int temp;
static int sum;

public static void main(String[] args)
{
    int x = Integer.parseInt(args[0]);
    int y = Integer.parseInt(args[1]);
    int ans = multiply(x , y);
    System.out.println(ans);
}
public static int multiply(int x, int y)
{
    if(x==1)
    {
        System.out.println(x+" : "+y);
        return y;
    }


    temp = multiply(x/2, y*2);

    if(x%2==0)
    {
        System.out.println(x+" : "+y);
        return temp;
    }
    else
    {
        System.out.println(x+" : "+y);
        sum = sum+temp;
        return sum;
    }
}
}

我认为递归有问题，但我找不到它是什么!!

Answer 1

当有递归时，不要在递归方法之外使用变量。这太困惑了。我的意思是递归方法应该是独立的。这是您程序的工作版本:

public class Main {

    public static void main(String[] args) {
        int x = 11;
        int y = 13;
        int ans = multiply(x, y);
        System.out.println(ans);
    }

    public static int multiply(int x, int y) {
        if (x == 1) {
            return y;
        }    

        int temp = multiply(x / 2, y * 2);
        if (x % 2 != 0) {
            temp += y;
        }

        return temp;
    }
}