1

我正在做作业，我必须使用平方乘幂来做两件事。一个是得到乘法的次数，另一个是得到实际的结果。

下面是一些例子：

2
11

应该输出

2048
5

因为2^11 = 2(2((2)²)²)²

我在没有递归的情况下这样做，我得到了正确的结果，但是乘法的数量是错误的。如果我输入2^6我得到3乘法，那没关系，但如果我输入2^8我得到4乘法，这是错误的。

你能指出我在正确乘法方面做错了什么吗？

这是代码：

public static void main(String[] args) {
    double x, result = 1;
    int n, multiplications = 0;
    DecimalFormat df = new DecimalFormat("#.00");
    Scanner readLine = new Scanner(System.in);

    x = readLine.nextDouble();
    n = readLine.nextInt();

    if (n == 1) {
        multiplications++;
        System.out.print(df.format(x) + "\n" + multiplications + "\n");
    } else if (n == 2) {
        x *= x;
        multiplications++;
        System.out.print(df.format(x) + "\n" + multiplications + "\n");
    } else {
        while (n > 0) {
            if (n % 2 == 0) {
                multiplications++;
            } else {
                multiplications++;
                result *= x;
                n--;
            }
            x *= x;
            n /= 2;
        }
        System.out.print(df.format(result) + "\n" + multiplications + "\n");
    }
}
4

2 回答 2

1

如果n % 2 == 0，则不乘；你只是广场。所以离开multiplications++吧。

然后对于 2^8 你得到：

n  |  n % 2  |  multiplications
----------------------
8  |  0      |  0
4  |  0      |  0
2  |  0      |  0
1  |  1      |  1

1乘法应该是正确的。自从2^8 = (((1² * 2)²)²)²

如果你想把平方算作乘法，你应该这样做

... else
    multiplications = multiplications + 2

然后减去 2 进行初始平方和乘法运算。

所以总的来说：

while (n > 0) {       
    if(n % 2 == 1) {
        multiplications++;
        result *= x;
        n--;
    }
    multiplications++;
    x *= x; // shouldn't that be result *= result?
    n /= 2;
}
multiplications -= 2;
于 2013-02-17T10:27:40.717 回答
1

你应该看的是数字的二进制表示。11 的二进制表示为 1011。从左到右读取。对于每个新的二进制数字，将结果平方。然后对于每个 1，也乘以因子。

对于 2 ^ 11，您可以：

第一个数字是一个，所以是 2。

下一个是零，所以只平方 2. 4。

下一个是 1，所以将 4 平方并乘以 2。4 的平方是 16。乘以 2 是 32。

下一个是一个，所以平方和相乘。32 的平方是 1024。乘以 2 是 2048。

于 2013-02-18T00:04:38.270 回答