0

数学用語が苦手です。

これは何と呼ばれていますか？

48 という数字があるとします。48 を構成する 2 つの要素を見つける必要があります。48 では 8,6 72 では 9,8 になります。

48 に対して 12,4 や 12,6 とは言いたくない

4

6 に答える 6

2 
public static int[] revominuteFactors(long x) {
    int[] result = new int[2];
    for (int a = 0; a <= x; a++) {
        for (int b = 0; b <= x; b++) {
            if ((a * b) == x) {
                if (result[0] == 0 && result[1] == 0) {
                    result[0] = a;
                    result[1] = b;
                } else if (Math.abs(a - b) < Math.abs(result[0] - result[1])) {
                    result[0] = a;
                    result[1] = b;
                }
            }
        }
    }
    return result;
}

数学の教授に尋ねたところ、その名前はrevominute要因に沿っているとのことでした.

于 2012-07-04T00:56:06.353 に答える
1

そのような数字に特定の名前はないと思います。それらを見つけることに関しては、おそらく最も簡単な方法は次のとおりです（数値nが与えられた場合）：

int factor1, factor 2;
for (int i = (int)(Math.sqrt(n)); i > 0; i--) {
    if (i/n == (double)i/n) {
        factor1 = i;
        factor2 = i/n;
        break;
    }
}

それが役立つことを願っています!

于 2012-07-04T01:01:43.213 に答える
1

距離が最も小さい因子のペアに特定の名前はありません。しかし、それがあなたが望むものかどうかを計算するのは簡単です。(少なくとも一般的な因数分解と同じくらい簡単ですが、小さな数の場合は簡単です。)

これを行う 1 つの方法を次に示します (2 つの因数が接近している場合に最も高速になります)。これは、フェルマーの因数分解アルゴリズムに基づいています。

static int sqrRoot(int n){
    //Find largest square <= n
    int sqr = 0;

    for (int i=15; i >= 0; --i){
        int newsqr = sqr + (1<<i);
        if (newsqr * newsqr <= n) {sqr = newsqr;}
    }

    return sqr;
}

static int[] closestFactors(int n){
    if (n <= 0) {throw new IllegalArgumentException();}

    int s = sqrRoot(n);
    if (s*s == n){
        int[] ans = {s,s};
        return ans;
    }

    int a = s * s - n;      
    while(s < n){
        if (a > 0){ //may not be true on first iteration
            int sa = sqrRoot(a);
            //whole number case
            if (sa*sa == a){    //We found a factorization
                int[] ans = {s-sa, s+sa};
                return ans;
            }
        }

        //half number case
        int sa2 = sqrRoot(a+s);
        if (sa2 * (sa2+1) == a+s){
            int[] ans = {s-sa2, s+sa2+1};
            return ans;
        }

        a += s + s + 1;
        s++;
    }

    int[] ans = {1, n};
    return ans;
}
于 2012-07-04T00:47:06.870 に答える
1

明らかに、すべての因子を見つけて、リストから適切な因子を選択するだけです。

別の方法として、 から始めることもできますlow = high = floor(sqrt(n))。次に、 の場合low * high < n、インクリメントしますhigh。場合low * high > n、減分しますlow。の場合は、答えとしてlow * high = n返します。(low, high)これはそれほど効率的ではありませんが、おそらくいくつかの小さな最適化を行うことができます。

例：

n = 325
low = 18, high = 18, low * high = 324
low = 18, high = 19, low * high = 342
low = 17, high = 19, low * high = 323
low = 17, high = 20, low * high = 340
low = 16, high = 20, low * high = 320
low = 16, high = 21, low * high = 336
low = 15, high = 21, low * high = 315
low = 15, high = 22, low * high = 330
low = 14, high = 23, low * high = 322
low = 14, high = 24, low * high = 336
low = 13, high = 24, low * high = 312
low = 13, high = 25, low * high = 325
answer: 13, 25

これは大雑把ですが、ファクタリングの代替手段です。このような 2 つの因数を見つけるための効率的なソリューションは、暗号化で使用される疑似素数を効率的に因数分解できることに注意してください。

于 2012-07-04T00:57:59.270 に答える
1

通常のケースで因数分解するNには、簡単なアルゴリズムで から開始し、 で除算p = 2するかどうかを確認します。そうでない場合は、次の値 (次の整数、または次の素数など) に設定して繰り返します。pNp

問題の理想的なケースでは、因子は に近くなりsqrt(N)ます。したがって、 から始めて、を割るものが見つかるまでp = floor(sqrt(N))デクリメントできます。pN

毎回テスト値を減らすとうまくいきます。通常の場合、連続する素数を試すなど、数学的に賢い方法があるかもしれません。素数を因数分解できる場合は、素数で因数分解できます。しかし、あなたの問題では、素数は気にしないので、ここで素数をあまり使用できない可能性があります。

于 2012-07-04T01:00:26.030 に答える
1

これの名前がわかりません。

Java では、これを他の言語と同じ方法で計算します。

  1. 数を因数分解します。
  2. 因子セットを 2 つのサブセットに分割して、2 つのセットの積の差が最小になるようにします。ブルートフォースは最初の試みとして機能するはずです...膨大な数の要因がない限り。

最悪の場合、ステップ 1. は NP であり、ステップ 2 (ブルート フォース) は「のみ」O(F^3)でFあることに注意してください。

さらに強引なアプローチは、適切な範囲の数値のペアを反復処理し、それらの積が元の数値であるかどうかをテストすることです。

コーディングとデバッグは、読者の演習として残します :-)

于 2012-07-04T00:50:10.547 に答える