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 に答える