Project Euler problem 33要求求解器找到“奇怪的分数”:等于通过删除同时出现在分子和分母中的数字获得的分数的分数(例如，49/98，通过删除 9“抵消”为 4/8)。
注意:这不是以最快速度解决欧拉计划问题的竞赛。我已经将此代码重写为一个与 Nickie 的一样快的解决方案。这是通过删除 for 循环和 if float(numer)... 条件来完成的。它看起来像这样:
def curious(numer,denom):
n = str(numer)
d = str(denom)
if len(n) == 2 and len(d) == 2:
if n[1] == d[0]:
if n != d:
if d[1] != "0":
if Fraction(int(n[0]), int(d[1])) \
== \
Fraction(numer, denom):
return n + d
虽然我还是不明白条件问题。
我对 Python 编程并不陌生，这是我第一次遇到这样的事情。在下面定义的函数中，有成对的 if 和 elif 语句:
import time
from fractions import Fraction
def curious(numer,denom):
n = str(numer)
d = str(denom)
if len(n) == 2 and len(d) == 2:
if n[1] == d[0]:
for i in range(2, numer+1):
if float(numer)/i == float(int(n[0])) \
and float(denom)/i == float(int(d[1])):
if n != d:
return n + "/" + d
elif d[1] != "0":
if Fraction(int(n[0]), int(d[1])) \
== \
Fraction(numer, denom):
if n != d:
return n + d
start = time.time()
nums = []
denoms = []
for i in range(10, 100):
for j in range(10, 100):
if i < j:
if type(curious(i, j)) == str:
frac = (curious(i,j))
nums.append(frac[0]+frac[1])
denoms.append(frac[2]+frac[3])
print frac
pro = 1
duct = 1
for i in range(0, len(nums)):
pro *= int(nums[i])
duct *= int(denoms[i])
print Fraction(pro, duct)
elapsed = time.time() - start
print "The elapsed time is %s seconds." % (elapsed)
当我运行注释掉 elif 语句的代码时，结果是这样的:
16/64,
19/95,
26/65,
The elapsed time is 0.0500001907349 seconds.
但是当包含 elif 时，if 语句被忽略，结果是这样的:
1664,
1995,
2665,
4998,
The elapsed time is 0.59700012207 seconds.
看起来 Python 更喜欢走低效的路线，即使在这两种情况下都满足 if 语句的条件。谁能帮我解开这个谜团？
理想情况下，我希望结果是:
16/64,
19/95,
26/65,
4998,
The elapsed time is 0.0500001907349 seconds.
请您参考如下方法:
这是一个结构奇怪的答案，因为它是逐步编写的。我为此道歉。即便如此，我认为还是值得按这个顺序阅读。每个部分用水平标尺分隔，表示不同的内容。
浮点运算中的相等比较通常是麻烦的来源，应该避免。而不是测试:
float(numer)/i == float(int(n[0])) and float(denom)/i == float(int(d[1]))
为什么不是下面的？更简单且等效(在数学中，但在 Python 中不是!):
numer == i * int(n[0]) and denom == i * int(d[1])
最重要的是，浮点运算不仅是麻烦的根源，而且从 int 翻译而来至 float过于频繁也不利于性能。
我不明白为什么您希望您的程序在删除 elif 时打印相同的结果条款。当您拥有 elif 时，它会做两件不同的事情当你不这样做的时候。您只是返回相同的结果 (n/d)，所以您看不到差异。
if声明不是“被绕过”。但是，如果它在 for 的第一次迭代中没有返回任何内容循环，然后是 elif语句(在每次迭代中做同样的事情)将有机会返回它的值。然后 if语句不会再次执行。
由于现在已经提供了有关该问题的更多信息(这是作为 Euler project's problem #33 解决方案的一部分)，我将坚持问题的原始版本并尝试重构功能 curious ，我认为写得不好。我相信下面的函数是等价的并且更快，因为 for loop 只计算依赖于 i 的东西:
def curious(numer,denom):
n = str(numer)
d = str(denom)
if len(n) == 2 == len(d) and n[1] == d[0] and n != d:
for i in range(2, numer+1):
if numer == i*int(n[0]) and denom == i*int(d[1]):
return n + "/" + d
elif i == 2 and d[1] != "0":
if Fraction(int(n[0]), int(d[1])) == Fraction(numer, denom):
return n + d
有了这个函数，Cawb07 的程序可以更快地产生相同的输出(四个分数加上 1/100，这是问题的答案)。
现在我明白了什么curious正在尝试做，让我建议一个更好的方法。让我们假设要寻求蛮力解决方案。它可以很容易地排列成curious总是使用两个 2 位参数调用，为此 numer < denom是真的，它返回一个 bool 结果，表示分数是否好奇。此外，不需要 for循环 curious , 这可以大大简化。
import time
from fractions import Fraction
def curious(numer, denom):
n = str(numer)
d = str(denom)
return (n[0] == d[1] != '0' and denom * int(n[1]) == numer * int(d[0])) \
or (n[0] == d[0] != '0' and denom * int(n[1]) == numer * int(d[1])) \
or (n[1] == d[0] != '0' and denom * int(n[0]) == numer * int(d[1])) \
or (n[1] == d[1] != '0' and denom * int(n[0]) == numer * int(d[0]))
start = time.time()
for i in range(10, 100):
for j in range(i+1, 100):
if curious(i, j):
print i, "/", j
elapsed = time.time() - start
print "The elapsed time is", elapsed, "seconds."
这个程序只打印四个奇怪的分数，同样比前一个快得多。
另请注意，为了将好奇分数的乘积简化为最低常用项，您可以轻松计算分母和分母，然后除以它们的 GCD，这可以使用 Euclid's algorithm 找到。 .
Cawb07:也可以使用 fractions.gcd(n,d) :).
