0

私はここと同じ質問に対して正しい解決策を見つけようとしています が、Javaで、カウントが返されることになっているので少し変更しました。

私は次の解決策を思いついた：

public static int count(int n) {
    // check for 0 or smaller
    if (n <= 0) {
        return -1;
    }

    // find root of N
    int root = (int) Math.ceil(Math.sqrt(n));
    int count = 0;
    for (int i = 1; i < root; i++) {
        if (n % i == 0) {
            // calculate bit_rev(i)
            int reverse = bit_rev(i);

            // calculate bit_rev(N/i)
            int reverseDiv = bit_rev((int)Math.floor(n/i));

            // check whether i * bit_rev(i) == N or i == bit_rev(N/i)
            if (reverse*i == n
                    || i == reverseDiv) {
                System.out.println(String.format("Found reverse (N = %d, i = %d, bit_rev(i) = %d, bit_rev(i) * i = %d, bit_rev(N/i) = %d)", n, i, reverse, reverse*i, reverseDiv));
                count++;
            } else {
                System.out.println(String.format("N = %d mod i = %d == 0, but no match (bit_rev(i) = %d, bit_rev(i) * i = %d, bit_rev(N/i) = %d)", n, i, reverse, reverse*i, reverseDiv));
            }
        }
    }


    if (count == 0) {
        // didn't match -> return -1
        return -1;
    } else {
        // return whatever the count was
        return count;
    }
}

public static int bit_rev(int n) {
    String string = Integer.toBinaryString(n);
    String reverseString = new StringBuffer(string).reverse().toString();
    int reverse = Integer.parseInt(reverseString, 2);
    return reverse;
}

参照サンプルでは、​​N=3245の解はcount=55であると想定されています。

しかし、私の解決策はそれを見つけますcount = 1 (i = 55, bit_rev(i) = 59).

その他の参照サンプルは次のとおりです。

-) N = 50 -> count = 1
-) N = 286 -> count = 2

bit_rev（）を見つけるための解決策が最高（最も効率的な解決策）ではないことは理解していますが、それは間違っているとは思いませんね。

ここに他の間違いがありますか、それともN = 3245の参照サンプルが間違っていますか？

4

1 に答える 1

1

質問を読み間違えたか、参照回答が間違っていると思います。http://algorithmsforever.blogspot.com/2011/12/integer-binary-roots.html?m=1の質問のようなものである場合は、バイナリルートの数ではなく、最小のバイナリルートを返す必要があります。

とにかく、あなたの実装はそれらを正しく機能させていると思います。55は確かに3245の最小のバイナリルートです（ルートの数ではありません）。

于 2012-08-22T06:23:23.817 に答える