1

私は宿題をやっています.squaringによるべき乗を使用して2つのことをしなければなりません. 1 つは乗算の数を取得することで、もう 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

注目すべきは、数値のバイナリ表現です。11 のバイナリ表現は 1011 です。左から右に読み取ります。新しい 2 進数ごとに、結果を 2 乗します。次に、1 ごとに係数を掛けます。

2 ^ 11 の場合、次のようにします。

1桁目は1なので2。

次はゼロなので、2 を 2 乗するだけです。 4.

次は 1 なので、4 を 2 乗して 2 を掛けます。4 の 2 乗は 16 です。2 を掛けると 32 です。

次は1なので、2乗して掛けます。32 の 2 乗は 1024 です。2 倍は 2048 です。

于 2013-02-18T00:04:38.270 に答える
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)²)²)²

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 に答える