12

これは、私が見つけた興味深いプログラミング パズルです。正の整数の配列と数値 K が与えられた場合、 となるような配列からペア (a,b) を見つける必要がありますa % b = K。

これに対する単純なO(n^2)ソリューションがあり、a%b=k のようなすべてのペアをチェックできます。機能しますが、非効率的です。私たちは確かにこれよりもうまくやることができますよね？同じための効率的なアルゴリズムはありますか? ああ、それは宿題ではありません。

4

3 に答える 3

6

配列とバイナリ検索を並べ替えるか、配列内の各値の数を含むハッシュ テーブルを保持します。

数については、 のような最大xのものを見つけることができます。これをバイナリ検索するか、ハッシュで調べて、それに応じてカウントを増やします。yx mod y = Ky = x - Ky

さて、これは必ずしも機能する唯一の値ではありません。たとえば、8 mod 6 = 8 mod 3 = 2. 我々は持っています：

x mod y = K => x = q*y + K =>
            => x = q(x - K) + K =>
            => x = 1(x - K) + K =>
            => x = 2(x - K)/2 + K =>
            => ...

これは、すべての約数もテストする必要があることを意味yします。で除数を見つけることができます。二分探索を使用し、ハッシュ テーブルを使用する場合O(sqrt y)は全体的に複雑になります (数値がそれほど大きくない場合は特に推奨されます)。O(n log n sqrt(max_value))O(n sqrt(max_value))

于 2012-10-04T18:53:04.233 に答える
0

この問題は、入力として 2 つの別個の配列があるものとして扱います。1 つは数値 a と a % b = K 用、もう 1 つは数値 b 用です。すべてが >= 0 であると仮定します。

まず、任意の b <= K を破棄できます。

ここで、b のすべての数値がシーケンス K、K + b、K + 2b、K + 3b を生成すると考えてください... 数値のペア (pos, b) を使用してこれを記録できます。ここで、pos はそれぞれ b ずつインクリメントされます。ステージ。pos = 0 から始めます。

これらのシーケンスを優先キューに保持して、いつでも最小の pos 値を見つけることができるようにします。数値の配列をソートします。実際、事前にこれを実行して、重複を破棄することができます。

For each a number
  While the smallest pos in the priority queue is <= a
    Add the smallest multiple of b to it to make it >= a
    If it is == a, you have a match
    Update the stored value of pos for that sequence, re-ordering the priority queue

最悪の場合、すべての数値を他のすべての数値と比較することになります。これは単純な解決策と同じですが、プライオリティ キューと並べ替えのオーバーヘッドが伴います。ただし、b の値が大きいと、いくつかの a の数値が通過する間、優先キューに未検査のままになることがあります。この場合は、この方が適切です。処理する数値が多数あり、それらがすべて異なる場合、そのうちのいくつかは大きくなければなりません。

于 2012-10-05T04:54:12.653 に答える
0

この回答では、アルゴリズムの要点 ( 「除数リスト」を使用するためDLと呼ばれます) について言及し、amodb.py と呼ばれるプログラムを介して詳細を提供します。

B を N 個の正の整数を含む入力配列とします。一般性をあまり失うことなく、B が昇順であると仮定B[i] > Kします。( if ; と whereの場合、すべての のペア (B[i]、B[j]) を報告できることにi注意してください。B が最初にソートされていない場合は、ソートに のコストがかかります。)x%B[i] < KB[i] < KB[i] = Kj>iO(N log N)

アルゴリズムDLとプログラム amodb.py では、A は、入力配列要素から事前に減算された K を持つ配列です。すなわち、A[i] = B[i] - K。a%b == Kの場合、場合によってjはa = b*j + Kまたはがあることに注意してくださいa-K = b*j。つまり、a%b == Kiffa-Kは の倍数ですb。さらに、 と が の因数である場合a-K = b*j、pはbのp因数ですa-K。

2から97までの素数を「小因数」と呼びます。ある間隔 [X,Y] から N 個の数値が一様にランダムに選択される場合、N/ln(Y) のオーダーの数値には小さな因数がありません。同様の数の最大小因数は 2 です。割合が減少すると、最大の小さな要素が連続的に大きくなります。たとえば、平均して約N/97は 97 で割り切れる、約N/89-N/(89*97)89 で割り切れるが 97 で割り切れない、などです。一般に、B のメンバーがランダムな場合、特定の最大の小さな因子を持つメンバーまたは小さな因子を持たないメンバーのリストは sub-O(N /ln(Y)) の長さ。

最大小因数pで割り切れる B のメンバーを含むリスト Bd が与えられると、DLは、リスト Ad の要素に対して Bd の各要素をテストします。これらの要素は、 pで割り切れます。しかし、小さな因数を持たない B の要素のリスト Bp が与えられると、DLはBpの各要素を A のすべての要素に対してテストします。この例 (および他の多くの例) では、注意することでテストの数を半分に減らすことができますが、amodb.py にはその最適化が含まれていないことに注意してください。N=25p=13Bd=[18967, 23231]Ad=[12779, 162383]12779%18967, 162383%18967, 12779%23231, 162383%2323112779<18967

DLは、要因Jごとに異なるリストを作成します。Jamodb.py のあるバージョンではJ=25、因数セットは 100 未満の素数です。 の値が大きいほど、除数リストを初期化Jする時間が長くなりますが、A の要素に対してリスト Bp を処理O(N*J)する時間がわずかに減少しO(N*len(Bp))ます。以下の結果を参照してください。他のリストを処理する時間は です。これは、以前の回答の方法の複雑さとO((N/logY)*(N/logY)*J)は対照的です。O(n*sqrt(Y))

次に示すのは、2 つのプログラム実行からの出力です。各セットで、最初のFound行は単純な O(N*N) テストからのもので、2 番目の行はDLからのものです。(小さすぎる A 値を徐々に削除すると、DLとナイーブ メソッドの両方がより速く実行されることに注意してください。) 最初のテストの最後の行の時間比率は、 DLとナイーブ メソッドのスピードアップ比が 3.9 と残念なほど低いことを示しています。その実行ではfactors、100 未満の 25 個の素数のみが含まれていました。2 回目の実行では、速度が 4.4 まで向上し、factors2 から 13 までの数と 100 までの素数が含まれていました。

  $ python amodb.py 
  N:  10000   K:  59685 X:  100000   Y:  1000000
  Found 208  matches in 21.854 seconds
  Found 208  matches in 5.598 seconds
  21.854 / 5.598 = 3.904

  $ python amodb.py
  N:  10000   K:  97881 X:  100000   Y:  1000000
  Found 207  matches in 21.234 seconds
  Found 207  matches in 4.851 seconds
  21.234 / 4.851 = 4.377

amodb.py をプログラムします。

import random, time
factors = [2,3,4,5,6,7,8,9,10,11,12,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
X, N = 100000, 10000
Y, K = 10*X, random.randint(X/2,X)
print "N: ", N, "  K: ", K, "X: ", X, "  Y: ", Y
B = sorted([random.randint(X,Y) for i in range(N)])
NP = len(factors);  NP1 = NP+1
A, Az, Bz = [], [[] for i in range(NP1)], [[] for i in range(NP1)]
t0 = time.time()
for b in B:
    a, aj, bj = b-K, -1, -1
    A.append(a)                 # Add a to A 
    for j,p in enumerate(factors):
        if a % p == 0:
            aj = j
            Az[aj].append(a)
        if b % p == 0:
            bj = j
    Bz[bj].append(b)
Bp = Bz.pop()   # Get not-factored B-values list into Bp
di = time.time() - t0; t0 = time.time()
c = 0
for a in A:
    for b in B:
        if a%b == 0:
            c += 1
dq =  round(time.time() - t0, 3); t0 = time.time()
c=0
for i,Bd in enumerate(Bz):
    Ad = Az[i]
    for b in Bd:
        for ak in Ad:
            if ak % b == 0:
                c += 1
for b in Bp:
    for ak in A:
        if ak % b == 0:
            c += 1
dr = round(di + time.time() - t0, 3)
print "Found", c, " matches in", dq, "seconds"
print "Found", c, " matches in", dr, "seconds"
print dq, "/", dr, "=", round(dq/dr, 3)
于 2012-10-06T07:40:23.803 に答える