2

問題:x =0からxmaxまで増加することが保証されている次数nの多項式(係数a 0からn-1)が与えられた場合、等間隔y持つ最初のm個の点見つける最も効率的なアルゴリズムは何ですか値(つまり、すべてのiについてy i --y i - 1 == c)?

例:間隔をc = 1にし、多項式をf(x) = x^2、にする場合、最初の3つのポイントはy = 1(x = 1)、y = 2(x〜 = 1.4142)、およびy = 3(x〜 = 1.7321)。


それが重要であるかどうかはわかりませんが、私の特定の問題は、与えられた係数を持つ多項式の3乗に関係しています。私の直感では、最も効率的な解決策は同じである必要があると言われていますが、よくわかりません。

私は2012年のワールドファイナルに設定されたACMの問題(問題B)でこの作業に遭遇しているので、これは主に私が興味を持っているためです。


編集:これが数学SEに行くべきかどうかわかりませんか?

4

1 に答える 1

3

二分探索を使用して、特定のYのXを見つけることができます。これは対数時間計算量であり、x値の範囲のサイズをエラー許容度で割ったものに比例します。

def solveForX(polyFunc, minX, maxX, y, epsilon):
    midX = (minX + maxX) / 2.0
    if abs(polyFunc(midX) - y) < epsilon:
        return midX
    if polyFunc(midX) > y:
        return solveForX(polyFunc, minX, midX, y, epsilon)
    else:
        return solveForX(polyFunc, midX, maxX, y, epsilon)

print solveForX(lambda x: x*x, 0, 100, 2, 0.01)

出力:

1.416015625

編集:コメント内のアイデアを拡張するために、複数のX値を検索することがわかっている場合は、[minX、maxX]の検索範囲を絞り込むことができます。

def solveForManyXs(polyFunc, minX, maxX, ys, epsilon):
    if len(ys) == 0:
        return []
    midIdx = len(ys) / 2
    midY = ys[midIdx]
    midX = solveForX(polyFunc, minX, maxX, midY, epsilon)
    lowYs = ys[:midIdx]
    highYs = ys[midIdx+1:]
    return solveForManyXs(polyFunc, minX, midX, lowYs, epsilon) + \
    [midX] + \
    solveForManyXs(polyFunc, midX, maxX, highYs, epsilon)

ys = [1, 2, 3]
print solveForManyXs(lambda x: x*x, 0, 100, ys, 0.01)

出力:

[1.0000884532928467, 1.41448974609375, 1.7318960977718234]
于 2012-08-08T15:56:08.493 に答える