10

2 つの数字がx1ありx2ます。数値については、とyの公約数をできるだけ に近づけたいと思います。x1x2y

これに効率的なアルゴリズムはありますか？

私の問題を言い換えて、より明確にする時が来たと思います。これは整数に関するものではありません...つまり、 と の 2 つの数値があるx1としx2ます。たとえば、ユーザーが数字を入力しますy。私が見つけたいのは、とが非常に小さい (たとえば、 よりも小さいが、この数値を と呼びましょう)y'に近い数値です。言い換えれば、最適なアルゴリズムは必要ありませんが、適切な近似が必要です。yx1 % y'x2 % y'0.02LIMIT

皆さんの時間と労力に感謝します。本当に親切です!

4

4 に答える 4

7

整数因数分解からこの問題への多項式時間の削減があるため、この問題に対する既知の効率的な (多項式時間) アルゴリズムはないと思います。整数因数分解のための既知の多項式時間アルゴリズムがないため、問題の既知のアルゴリズムもあり得ません。

これがどのように機能するかを確認するために、因数分解したい数 n があるとします。次に、任意のアルゴリズムを使用して、n と n の公約数を √n に最も近い値を見つけます。n の非自明な除数は √n よりも大きくならないため、(1) n を割る最大の整数、または (2) n が素数の場合は 1 のいずれかを見つけます。次に、n をこの数で割り、繰り返して n のすべての因数を生成できます。n は最大で O(log n) の因数を持つことができるため、問題のソルバーを多項式で反復する必要があるため、整数因数分解からこの問題への多項式時間の削減があります。前述のように、これは、少なくとも公開文献では、この問題を解決するための既知の効率的な古典的アルゴリズムがないことを意味します。存在するかもしれませんが、それは非常に重要な結果になるでしょう。

否定的な回答で申し訳ありません。これがお役に立てば幸いです。

于 2012-02-08T19:23:48.543 に答える
2

欲張りアルゴリズムでそれを行うことができると思います。最初に一般的なアルゴリズムでGCDを見つけてd（対数時間で計算可能）、次にd各時間の因子を利用可能な最小の因子に除算dして（create ）、小さい場合d'と比較|d'-y|します。方法（およびで|d-y|置き換える）、または、最小公約数で乗算し、再びその距離をyと比較します。d'dd'

于 2012-02-08T18:02:40.743 に答える
2

これは私が得ることができるので効率的です：

from fractions import gcd
primes=[i for i in range(2,1000) if all(i%j!=0 for j in range(2,i))] #ensure you have enough primes.. (can improve efficency here)


def f(x1,x2,y):
    _gcd=gcd(x1,x2)
    if _gcd==1:
        return 1
    factors=(i for i in range(2,_gcd+1) if _gcd%i==0) #can improve efficiency here.. e.g. only go up to root(gcd)
    r1=999999999
    r2=999999999
    for i in factors:
        r1=min(r1,y%i)
        r2=min(r2,i-y%i)
    return y-r1 if r1<=r2 else y+r2


print f(8,4,3)
print f(16,12,5)
print f(997,53,44)
print f(2300*2,2300*3,57)

"""
2
4
1
56
"""
于 2012-02-08T21:13:15.073 に答える
0
  1. x1とのGCDを見つけますx2。
  2. GCD <= Yその後戻る場合GCD
  3. 現在の最良の答えはGCD、であり、最良の距離はGCD - yです。
  4. すべての数値を反復しますY+/-[0...最適な距離]
  5. x1との両方の倍数である最初の整数を返しますx2

GCDを見つけるには

public int getGCD( int a, int b )
{
   return (b==0) ? a : gcd(b, a%b);
}

yに最も近い約数を見つけるには...

public int closestDivisor( int a, int b, int y ){
    int gcd = getGCD( a, b );
    if( gcd <= y ) return gcd;
    int best = gcd - y;
    for( int i = 0; i < best; i++ )
    {
        if( gcd % (i-y) == 0 ) return i - y;
        if( gcd % (i+y) == 0 ) return i + y;
    }
    return gcd;
}

@trinithisが示唆したように、利用可能な唯一の追加の最適化は、gcdを因数分解すること（おそらくふるいを使用するか？）であると私は信じています。

于 2012-02-08T18:02:00.753 に答える