-1

たとえば
、2つの異なる平方数の積によって数値を形成できるかどうかを見つけるためのより短く効率的な方法はありますか?

  • 36=4*9
  • 144=16*9

アルゴリズムまたはロジックについて教えてください

4

4 に答える 4

1

かなり簡単なはずです。あなたの数を取り、それを素因数分解します。さまざまな言語でのアルゴリズムと実装は、こちらから入手できます。

素因数が分かれば後は簡単です。それらを調べて、同じ数字のペアが 2 つあるかどうかを確認します。

例えば：

36 = 2 * 2 * 3 * 3. 2 つのペア (2 と 3)。できます。

144 = 2 * 2 * 2 * 2 * 3 * 3 => 2 つのペア (2*2 と 3)。できます

唯一のトリッキーな部分は、X = A * A * B * B になるように素因数を再結合することです。しかし、それもそれほど難しいことではありません。

于 2012-12-26T13:41:58.857 に答える
0

これはどう？

package Math;
public class NearestNumber {
    public static void main(String[] args) {

        int myNumber = 144;
        int min = (int) Math.sqrt(myNumber);
        int i, j, counter = 0;

        for (i=2;i<min;i++) {
            for (j=i+1;j<=min;j++) {
                if (myNumber == (i*i*j*j)) {
                    System.out.println("Possible combination are " + (i*i) + " and " + (j*j));
                    counter++;
                }
            }
        }
        if (counter==0) {
            System.out.println("No possible combination found!!!");
        }
    }
}

注:これは可能なすべての組み合わせを出力しており、最も近いものではありません。私は最初が最も近いと信じています...

上記の出力は

Possible combination are 4 and 36
Possible combination are 9 and 16

デモ

于 2012-12-26T14:21:39.620 に答える
0

次のことを検討することをお勧めします。

数値が 2 つの異なる平方数の積である場合、その数値は n という形式になります。ここで、a と b の値に対して n = a^2 * b^2 です。ただし、a^2 * b^2 = (a*b)^2 であることはわかっています (上記の 2 つの例で自分で確認できます)。したがって、ある数が 2 つの平方の和であるかどうかを知るには、その数自体が平方数でなければなりません。

あとは、それが 2 つの異なる平方数の積であることを確認するだけです。これは、次のように簡単に行うことができます。

n = a^2 * b^2 の場合、a <> b の場合、n は a^4 に等しくなりません。n = a^4 の場合、a^2 * b^2 = a^4 となり、これは b^2 = a^2 を意味し、最終的には b = a または -a を意味します (値をカウントし、このテストの目的では「個別」として負です)。

于 2012-12-26T13:51:04.163 に答える
0

あなたはロジックを求めたので、ここに行きます。実装は簡単です。

数値を取得し、その平方根を抽出します。整数でない場合、A*A = N となる数値 A はありません。したがって、B*C = A となる数値が 2 つ存在することはありません。そこで停止します。

ルート Aが整数の場合、そのルートを再度抽出します。その整数部分を R とします。2 と R の間のすべての素数をループし、A を因数分解するために使用します。残り。余りなく割った回数がその素数のべき乗です。そのべき乗の数だけ、その素数をリストに入れます。割り算で 1 になったらやめます。R より大きい数を思いついた場合は、それをリストに追加してループを終了します。

最後に、[ 3, 3, 5, 5, 5, 7 ] のようなリストが表示されます。

セットのメンバーが 1 つしかない場合、問題の解決策はありません。R を計算すると整数であることがわかるため、これをすばやく確認できます。それが素数でもある場合、R より小さい約数はなく、セットは [ R ] になり、2 つの空でないセットに分割することはできません。

あなたの例では、次のようになります。

144 -- root is 12
Root of 12 is 3.4, so you need only check from 2 to 3 to fill [ ]
2 divides 12 and you get 6: [ 2 ]
2 divides 6 and you get 3 [ 2 2 ]
2 does not divide 3
3 divides 3 and you get 1 [ 2 2 3 ], so exit.
Factors of 12: [ 2, 2, 3 ]

これで、ディクショナリの各2 パーティションは適切な数のペアを表します。たとえば、[ [ 3 2 ], [ 2 ] ] は 2^2 と (2*3)^2 が適切な候補であることを意味し、[ [ 2 2 ] [ 3 ] ] は (2 *2)^2 と 3^2 が適切な候補です。

最初の 1,000 個の素数を含むテーブルを使用すると、約 5,000 億までの数を効率的にチェックできます。それに到達するために BigNum ライブラリ (libgmp、NumPy、...) が必要な場合でも。

于 2012-12-26T18:35:10.263 に答える