algorithm - 找到 a、b 和 c 的值，使得 X^a * Y^b * Z^c 最接近 N 并且 a+b+c 最小

Question

X、Y 和Z 是三个正整数。我必须找到 a、b 和 c 的值，这样 X^a * Y^b * Z^c 最接近某个给定的数字 N 并且 a+b+c 是最小值(a、b 和c 是正整数)。

编辑:我目前的解决方案是迭代 X、Y 和 Z 从 1 开始的幂。计算这些项的乘积，与之前的最佳结果进行比较，并相应地更新 a 的值、b 和 c。下面粘贴了这种方法的 Python 片段。我假设 X、Y 和 Z 是大于 1 的整数。

def foo(X, Y, Z, N):
    res = a = b = c = -1

    for i in range(1, int(math.log(N)/math.log(X))):
        for j in range(1, int(math.log(N)/math.log(Y))):
            for k in range(1, int(math.log(N)/math.log(Z))):
                product = pow(X, i) * pow(Y, j) * pow(Z, k)
                if product > N:
                    break
                if product > res:
                    res = product
                    a = i
                    b = j
                    c = k

    return a, b, c

这种方法为 X、Y 和 Z 的小值提供了正确的结果，但我不确定它是否适用于所有值。有什么我遗漏的或任何其他更复杂的方法。

Answer 1

您的解决方案似乎不错。无论如何，您都不会进行那么多次迭代，因为幂的增长速度有多快并以对数步长达到 N。

一些优化是您不必每次都计算乘积。拥有一个数字并继续操纵该值。 (参见代码)这有助于在 python 中处理大量数据。

稍微优化的代码:

def foo2(x, y, z, N):

    a = b = c = -1
    i = j = k = -1

    maxProd = 1
    curProd = 1

    for i in range(1, N):
        curProd *= x
        for j in range(1, N):
            curProd *= y
            for k in range(1, N):
                curProd *= z
                if curProd > N:
                    break
                if curProd > maxProd:
                    maxProd = curProd
                    a,b,c = i,j,k

            curProd //= z**k
            if curProd > N:
                break
        curProd //= y**j
        if curProd > N:
            break
    curProd //= x**i

    return a, b, c

输入:

x = 4
y = 7
z = 3
N = 21563163762572572574634215165164617645147157

输出:

(30, 22, 14)

时间分析:

您的实现:82 毫秒

我的实现:14 毫秒

最坏情况: