二进制乘法 - Peasant算法

Question

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

算法:

要将两个十进制数x和y相乘,请将它们彼此相邻,如下例所示.然后重复以下步骤:将第一个数字除以2,向下舍入结果(即,如果数字为奇数则丢弃:5),并将第二个数字加倍.继续前进,直到第一个数字变为1.然后删除第一个数字为偶数的所有行,并将第二列中的剩余数据加起来.

11 13

5 26

2 52

1 104

........

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;
    }
}