代码之家 › 专栏 › 技术社区 › TAMEEM ALHARTHI

有没有办法优化这个简单的乘法算法?

mathematical-optimization optimization

0

TAMEEM ALHARTHI · 技术社区 · 2 年前

在进行本地编码竞赛时,我发现了一个简单但难以优化的问题,问题如下:“给定一个数组 [1, 2, 3] ,使用以下公式找到第i个数字: arr[i] = arr[i - 3] + arr[i - 2] * arr[i - 1] ,并键入的值 arr[249] % 169 进入答案框。"

这并不太难,但由于公式使用了数组中的最后3个数字,这意味着它是非常指数的,arr[8]和arr[9]之间的差在数万亿中,而且它变得更大更快。

比赛中的问题似乎要求很多,但我确实怀疑它的模数部分可能会大大简化这个过程。怎样我真的不知道。

我在python中尝试了一个简单的递归函数和for循环(我没有任何其他语言的经验,所以我不能用更快的语言来尝试),这两种方法都不能在可接受的时间内强行解决这个问题,我没有尝试利用模部分,因为我不知道如何实现这一点,也不确定这是否可能。

以下是我的解决方案,以函数形式表示:

def recursion(n):
    if n <= 3:
        return n
    
    return recursion(n - 3) + recursion(n - 2) * recursion(n - 1)
 
def forLoop(n):
    arr = []
    for i in range(n):
        if len(arr) < 3:
            arr.append(i + 1)
            continue
        
        arr.append(arr[0] + arr[1] * arr[2])
        arr.pop(0)
    
    return arr[2]
 
 
testNum = 6
r = recursion(testNum)
f = forLoop(testNum)
 
print(r, f)

1 回复 | 直到 2 年前

1

Aakash Gupta 2 年前

您的方法存在两个问题:

这个问题可以在线性时间内解决,而不是递归,使用简单的for循环。
我们可以使用模运算规则来保持数字始终在 [0, 169) .

解决第一个问题

我们可以在这里使用记忆。假设我们想找到 arr[100] 。我们需要什么信息才能找到这个?

我们有一个公式: arr[i] = arr[i - 3] + arr[i - 2] * arr[i - 1]

因此,我们将 arr[100] = arr[97] + arr[98] * arr[99] .

考虑以下场景:我们有 arr[0] , arr[1] , arr[2] .如果我们计算并存储 arr[3] ?如果储存后 arr[3] ,我们计算 arr[4] ? ...?如果储存后 arr[99] ,我们计算 arr[100] ?

我们很容易看出 arr[100] 可以在恒定的时间内计算,正如我们已经拥有的那样 arr[97] , arr[98] 和 arr[99] 与我们一起存储。

您可以在此处看到此方法的另一个示例: nth Fibonacci number in linear time .

解决第二个问题

进入第二个问题,该问题可以使用模运算规则来求解。以下是我们需要的规则:

(a + b) % n = ((a % n) + (b % n)) % n
(a * b) % n = ((a % n) * (b % n)) % n

因为我们只需要 arr[249] % 169 ,我们可以假设 n=169 我们的问题归结为 arr[i] % n 为所有人 i 从…起 0 到 249 因此,我们可以将方程转换为:

Let b[i] = arr[i] % n. We need b[249].

b[i]
= arr[i] % n
= (arr[i - 3] + arr[i - 2] * arr[i - 1]) % n
= ((arr[i - 3] % n) + (arr[i - 2] * arr[i - 1]) % n) % n
= (b[i - 3] + ((arr[i - 2] % n) * (arr[i - 1] % n)) % n) % n
= (b[i - 3] + (b[i - 2] * b[i - 1]) % n) % n.

因此,与其返回 arr[249]%169 ,我们只是简单地返回 b[249] .

伪代码

以下是相同的伪代码:

mod = 169
b = [0,0,0,...] # Size of b is 250
b[0] = 1
b[1] = 2
b[2] = 3

for i = 3 to 249 (included):
    b[i] = (b[i - 3] + (b[i - 2] * b[i - 1]) % mod) % mod

print b[249]

这应该会让一切变得清楚。