"Kinda“加法链计算器
我构建了一个加法链(有关加法链的更多信息：维基百科)计算器，它产生的链比链长等于所要达到的数的链短。
它并不总是产生最短的链(如果谈论的是一个大的数字)。然而，仍然给出了一个相当短的链相比，最大尺寸的链，将得到的数字。
它比蛮力计算更快(但是)。在寻找最短链方面不太准确(就像我前面说的那样)，因为它依赖于一个算法(我不确定算法是否是正确的词，但基本上我只是使用逻辑步骤来找到一个短链)。基本上，它从给定的数字开始，然后返回到1。
它的工作方式如下：
- 检查这个数字是偶数还是奇数，如果是奇数，检查它是否是素数。
- 如果它是一个偶数，除以2，如果它是奇数，找出最大的因子并除以它，直到这个因子本身达到。如果它是素数，将它减去1，然后按照偶数的步骤进行。
- 步骤1和步骤2总是重复的，在此之前(之前和之后将重复值，因此只有‘前面’)每个操作，数字的当前状态将被添加到列表中。
(它也在检查每个数字是否有(n+1)/2长度的链，所以这是一个很小的步骤，但这并不是很重要。这是我在数学课上做的另外一件事。)
假设我们有5，它是一个奇数，所以我们减去1，得到一个偶数: 4。现在我们除以它，得到2，因为2也是偶数，我们又除以1，程序停止并打印列表，即：5、4、2、1。
我正在自学编程，没有接触过排序/搜索算法，在代码的质量方面，甚至在我用来计算的逻辑步骤方面，我还能做得更好吗？
n = int(input()) # kan tot 8 cijfers snel(<1min), na 8 traag
BewijsN = (n + 1) / 2
List1 = []
def IsEven(n):
if n % 2 == 0:
return True
else:
return False
def IsPrime(n):
for x in range(n - 2):
x += 2
if n % x == 0:
return False
return True
def BigFactorCheck(n):
for x in range(n):
x += 1
if n % (n - x) == 0:
return n - x
while n > 1:
if IsEven(n) == False:
if IsPrime(n):
List1.append(n)
n += -1 # Prim naar even
else: # Oneven
List1.append(n)
BigFactor = BigFactorCheck(n)
for x in range((n // BigFactor) - 2):
x += 1
List1.append(n - BigFactor * x)
n = n - BigFactor * (x + 1) # lelijk, maar werkt
while IsEven(n):
List1.append(n)
n = n // 2
if n == 1:
List1.append(n)
List1.sort()
print(len(List1), List1)
if len(List1) - 1 <= BewijsN:
print(True, len(List1) - 1, "<=", BewijsN)回答 2
Code Review用户
发布于 2020-10-16 14:06:19
改进的实现
下面是相同算法的改进实现，包含了其他答案中的内容：
from math import isqrt
def smallest_factor(n):
for i in range(2, isqrt(n) + 1):
if n % i == 0:
return i
def addition_chain(n):
chain = []
while n:
if small := smallest_factor(n):
big = n // small
for _ in range(small - 1):
chain.append(n)
n -= big
else:
chain.append(n)
n -= 1
chain.reverse()
return chainDemo
演示了几个n的输出，包括所用的时间、链的长度以及(可能缩短的)链：
n=1 5.15 μs len=1 [1]
n=2 5.01 μs len=2 [1, 2]
n=3 9.16 μs len=3 [1, 2, 3]
n=4 481.24 μs len=3 [1, 2, 4]
n=5 356.58 μs len=4 [1, 2, 4, 5]
n=6 10.75 μs len=4 [1, 2, 3, 6]
n=7 17.10 μs len=5 [1, 2, 3, 6, 7]
n=8 451.55 μs len=4 [1, 2, 4, 8]
n=9 381.45 μs len=5 [1, 2, 3, 6, 9]
n=10 372.24 μs len=5 [1, 2, 4, 5, 10]
n=123 426.09 μs len=10 [1, 2, 4, 5, 10, 20, 40, 41, 82, 123]
n=123456789 2178.51 μs len=3630 [1, 2, 3, 6, 9, '...', 13717421, 27434842, 41152263, 82304526, 123456789]产生上述输出的代码：
from time import perf_counter as timer
def abbreviated(chain):
if len(chain) <= 10:
return chain
return chain[:5] + ['...'] + chain[-5:]
for n in [*range(1, 11), 123, 123456789]:
t0 = timer()
chain = addition_chain(n)
t1 = timer()
print(f'{n=} {(t1 - t0) * 1e6:.2f} μs ', f'len={len(chain)}', abbreviated(chain))a观察
注意，当n是偶数时，不需要特殊情况，我在代码中忽略了它。你的处理是把它除以2，通过和任何其他因素一样的处理，我们只减去n/2一次。这是等价的。当然，这可能会使情况稍微变慢，但无论如何它们都是非常快的，所以这并不重要。
--一种更简单更好的替代
考虑一下这一简单得多的备选方案：
def addition_chain(n):
chain = []
while n:
chain.append(n)
if n % 2:
n -= 1
else:
n //= 2
chain.reverse()
return chain和以前一样的演示：
n=1 2.32 μs len=1 [1]
n=2 2.17 μs len=2 [1, 2]
n=3 2.85 μs len=3 [1, 2, 3]
n=4 2.55 μs len=3 [1, 2, 4]
n=5 2.58 μs len=4 [1, 2, 4, 5]
n=6 2.64 μs len=4 [1, 2, 3, 6]
n=7 3.26 μs len=5 [1, 2, 3, 6, 7]
n=8 2.01 μs len=4 [1, 2, 4, 8]
n=9 2.58 μs len=5 [1, 2, 4, 8, 9]
n=10 5.20 μs len=5 [1, 2, 4, 5, 10]
n=123 4.21 μs len=12 [1, 2, 3, 6, 7, '...', 30, 60, 61, 122, 123]
n=123456789 14.99 μs len=42 [1, 2, 3, 6, 7, '...', 30864196, 30864197, 61728394, 123456788, 123456789]请注意，这要快得多，并为n=123456789生成了一个更短的链:长度42，而不是原始算法中的长度3630。虽然原始算法在最小因子较大时产生长链，但这种简单的算法总是产生长度为O(log )的链。
Code Review用户
发布于 2020-10-16 15:50:07
Internationalization
我想进一步阐述代码语言和i18n (国际化)/本地化(l10n)之间的区别。
这是个好主意(请原谅我的谷歌翻译)：
# Will be fast up to 8 digits; will be slow after 8
n = int(input(
'Voer het nummer in'
))面向用户的内容应该使用用户的语言。这可以非常简单(如上面使用硬编码区域设置的示例中所示)，或者根据您的需求非常复杂。有些Python包(如https://docs.python.org/3.8/library/locale.html )将支持这种工作。
这可能是有问题的：
# Ik begrijp dit, maar mijn collega's misschien niet
# kan tot 8 cijfers snel(<1min), na 8 traag不管好坏，英语实际上是编程和工程的语言.我工作过的几乎所有的工作场所都是多语言的，英语是一种标准--就像Python本身一样--我们都同意这是为了促进交流。对于互联网上的开源合作来说，这一点尤为重要。
https://codereview.stackexchange.com/questions/250722
复制相似问题
腾讯云开发者
