这个算法背后的逻辑是什么？

Question

这个问题的解释可以在@http://www.cemc.uwaterloo.ca/contests/computing/2017/stage%201/juniorEF.pdf
中找到（这是标题为 "exactly electrical" 的第三个问题）。

def electrical(a,b,c,d,e) :
  charge = e
  x_dif = abs(c - a)
  y_dif = abs(d - b)
  total_dif = (x_dif + y_dif)

  if (((total_dif) == charge) or ((total_dif % 2 == 0) and (charge %2 == 0)) or ((total_dif % 2 != 0) and (charge % 2 !=0))) :
    return "Y"
  else :
    return "N"

print(electrical(10,2,10,4,5))

此代码也可以在 https://repl.it/@erichasegawa/2017-CCC-Junior-S3 中找到。

这周我正在学习写作加拿大计算机竞赛，我对他们的一个算法有疑问；为什么我的函数 return "Y" 当电荷和距离都均匀或不均匀时，但如果一个是均匀的而另一个不是（反之亦然）它 return 是错误的。我知道这有效，但我不知道 为什么或如何 它有效。如果有人可以解释这一点，那就太好了。

Answer 1

细分条件：

if (((total_dif) == charge) or ((total_dif % 2 == 0) and (charge %2 == 0)) or ((total_dif % 2 != 0) and (charge % 2 !=0)))

我们有...

(total dif == charge) # they are equal, so either both odd or even

or ((total_dif % 2 == 0) and (charge % 2 == 0)) # if their remainder after division by 2 is 0, then they're both even 

or ((total_dif % 2 != 0) and (charge % 2 != 0)) # if their remainder after division by 2 is NOT 0, then they're both odd

注意第一个条件是不必要的；我们已经在稍后检查两者是偶数还是奇数。拥有或删除不应改变程序的行为。

另请注意，"total_dif" 周围的一组括号是不必要的，并且会使本已庞大的条件更加难以阅读。事实上，您应该将表达式分成不同的部分，也许作为变量 both_even 和 both_odd，然后检查

if (both_even or both_odd)

更易读

Answer 2

您的代码声明

if (((total_dif) == charge) or ((total_dif % 2 == 0) and (charge %2 == 0)) or ((total_dif % 2 != 0) and (charge % 2 !=0))) :

第一个条件

(total_dif == charge)

正在确定电荷是否等于所需的距离，因此两者都是偶数或奇数。

第二个条件

((total_dif % 2 == 0) and (charge %2 == 0))

检查两个参数（电荷和距离）除以 2 的余数是否为偶数（% 运算符）；它正在检查它们是否都是偶数。

你的第三个条件正好相反，它检查它们是否都是奇数。

本质上，你的条件是检查电荷和距离之间的差值是否可以被二整除，因为你可以做两个 U-turns 来抵消这个均匀的盈余。

因此，您的条件可以简化为

if ((charge-total_dif) % 2 == 0):

你的问题在技术上与问题无关，因为如果一个论点是偶数，另一个是奇数，你要么有盈余，要么有赤字。总是。

您的代码唯一的另一个问题是它从不检查电荷是否大于或等于距离！

这意味着您可以有一个偶数距离 n（如 28321728932）和 0 电荷并且仍然 return 'Y'，或者有一个奇数距离 x（如 3121）和 3 电荷并且仍然 return 'Y'.

因此，您应该包含条件

charge >= total_dif

在您的代码中。

综上所述，你的情况应该是

if ((charge >= total_dif) and ((charge-total_dif) % 2 == 0):

最后说明：请使用较短的变量名。在像您这样的短程序中，您可以轻松区分较短的名称。

这个算法背后的逻辑是什么？

What is the logic behind this algorithm?

python

python-3.x

algorithm

graph

modulus