2

我一直在尝试解决关于 spoj 的问题。这是问题的链接。

http://www.spoj.pl/problems/TAP2012B/

根据我的解释，我需要找到方程 xy+yz+xz = N 的解数，其中 n 给了我们。x>=y>=z z 可以为零。但是 x 和 y 不能。我尝试通过实现 3 个 for 循环（不好的方法）来解决这个问题。它给出了正确的答案，但它太慢了。此外，其他人几乎很快就解决了它（0.00）所以我相信这个问题有一种非常不同的方法。对于 N = 20，不同解的数量为 5： (6,2,1) (5,4,0) (10,2,0) (4,2,2,) (20,1,0)

4

3 回答 3

2

也许有一些基于数论的绝妙解决方案。但简单地重新考虑任务也可以降低算法的复杂性。

例如，我们不需要第三个循环，因为我们可以计算z为(N - x*y)/(x+y). 而且我们不必每次y都一直跑到，因为我们知道，这不是负数，因此.xzN >= xy

N = 9747
for x in range(1, N+1):
    max_y = min( N / x, x) 
    for y in range(1, max_y+1):
        if (N - x*y) % (x+y) == 0:
            z = (N - x*y) / (x+y)
            if z <= y:
                print x,y,z
于 2013-07-04T11:33:13.240 回答
1

You are approaching towards the right direction there will be 3 nested loops but try to reduce the no. of times the loop operates.... Follow the question and conditions carefully.....

于 2013-07-04T11:10:31.087 回答
0

你显然在学习，所以如果你自己做所有事情会更好，但你现在从 akalenuk 那里得到了一个很好的解决方案，我希望你也能从中学到一些东西。

如果你同时学习 python，我会给你一个与 akalenuk 等效的解决方案，但这次使用列表理解，这是一个非常有用的机制：

N = 10000

print [(x, y, z)
       for x in range(1, N+1)
       for y in range(1, min( N/x, x) + 1 )
       for z in [ (N - x*y) / (x+y) ] 
       if (N - x*y) % (x+y) == 0
       if z <= y]

关键在于修剪解决方案空间。上面的代码已经很优化了。您可能会从以下内容开始：

N = 10000

print [(x, y, z)
       for x in range(1, N+1)
       for y in range(1, x+1 )
       for z in range(y+1) 
       if N == x*y + y*z + x*z]

这将运行很长时间。因此，优化的第一点可能是在 y 上添加条件：

N = 10000

print [(x, y, z)
       for x in range(1, N+1)
       for y in range(1, x+1 )
       if x*y <= N
       for z in range(y+1) 
       if N == x*y + y*z + x*z]

这已经大大减少了时间，因为没有希望y-loopz根本不运行。然后，您注意到您实际上可以通过显式计算最大 y 来替换该 if 语句，就像 akalenuk 所做的那样：

N = 10000

print [(x, y, z)
       for x in range(1, N+1)
       for y in range(1, min(x, N/x) +1)
       for z in range(y+1) 
       if N == x*y + y*z + x*z]

这将再次加快速度。

在您学习的过程中，我建议您尝试所有这些以及您自己的方法，计时并从中学习。我还建议尝试不同的、类似的解决方案

于 2013-07-04T12:11:34.000 回答