擅长:python、mysql、java
<p>在算法中,搜索所有可能的y值。这是不必要的。这里的诀窍是认识到</p>
<pre><code>y^2 + x^2 = 2n^2
</code></pre>
<p>直接暗示</p>
<pre><code>y^2 = 2n^2-x^2
</code></pre>
<p>这意味着你只需要检查2n^2-x^2是一个完美的正方形。你可以通过</p>
<pre><code>y2 = 2*n*n - x*x
#check for perfect square
y = math.sqrt(y2)
if int(y + 0.5) ** 2 == y2:
#We have a perfect square.
</code></pre>
<p>另外,在您的算法中,您只检查x值到n。这是不正确的。由于y^2始终为正或零,我们可以通过将y^2设置为其最低值(即0)来确定需要检查的最高x值。因此,我们需要检查所有满足</p>
<pre><code>x^2 <= 2n^2
</code></pre>
<p>减少到</p>
<pre><code>abs(x) <= sqrt(2)*n.
</code></pre>
<p>将此与只检查顶部象限的优化结合起来,您就有了一个优化的psearch</p>
<pre><code>def psearch(n):
count = 0
top = math.ceil(math.sqrt(2*n*n))
for x in range(1, top):
y2 = 2*n*n - x*x
#check for perfect square
y = math.sqrt(y2)
if int(y + 0.5) ** 2 == y2:
count+=4
return count
</code></pre>