Python：Collatz序列--找一个长度大于起始数的数
Python: Collatz sequence -- find a number where the length is greater than the starting number
问题来了，我正在尝试解决它，但我越来越困惑了。
这道题希望你找到一个起始编号，它创建的 Collatz 序列的长度大于使用当前起始编号创建的当前编号，并且该编号必须小于或等于当前编号一.
假设我们最初的起始数字是 4：
4->2->1（3的长度）
3->10->5->16->8->4->2->1（长度为8）
2 -> 1（长度 2）
1（长度1）
现在答案应该是你 return 3，因为 3 小于或等于你的起始数字 4，而且它是唯一一个以它为起始的数字，你会得到一个序列长度大于起始编号的长度，在本例中为 4。
我尝试做一个递减每个的循环，并将当前起始数字和长度添加到字典中，起始数字作为键，长度作为值。然后进去 return 具有更大值（长度）的密钥，但它不起作用。不知道是我写错了还是思路错了...
我觉得它与循环有关，因为 while 循环实际上确实会自己创建正确的序列，当我将它包装在 for 循环中并使用 i 进行计算时，它变得不正确，甚至创建序列时。
def solution(x):
sequence = []
d = {}
length_of_sequence = 0
for i in range (x, 1, -1):
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence += len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
在此先感谢您，我一直在考虑这个问题，但我一无所获，非常感谢您的帮助！
TL;DR
(main, IMO) 问题来自行 length_of_sequence += len(sequence)，因为它应该是 length_of_sequence = len(sequence)，而且您没有在每次迭代时重置 sequence .
但是还有其他多个错误。这是正确的版本。
def solution(x):
d = {}
for i in range(2, x+1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0: i //= 2
else: i = 3*i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
这里有一个更好（更快）的递归方法。
def solution(x):
d = {1: 1}
def collatz(n):
if n not in d: d[n] = (collatz(n//2) if n % 2 == 0 else collatz(3*n+1)) + 1
return d[n]
return max(range(1, x+1), key=collatz)
说明
让我们从您的代码开始，逐步重构到正确的代码，然后继续到更快的代码。
def solution(x):
sequence = []
d = {}
length_of_sequence = 0
for i in range (x, 1, -1):
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence += len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
打补丁sequence
请注意，您只初始化了 sequence 一次，但您一直在追加它，这意味着在第二次迭代中，它已经包含第一次迭代中的元素，因此它的长度严格增加。由于您以 2 结尾，最大值可能是 2。
补丁很简单，只需为您正在查看的每个 i 重新创建序列。
def solution(x):
d = {}
length_of_sequence = 0
for i in range (x, 1, -1):
sequence = []
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence += len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
打补丁length_of_sequence
然而，之前的补丁没有效果，因为您仍然将序列的长度从一个迭代带到下一个迭代，因此您应该在每次迭代时对其进行初始化，并且仅在完成序列后才更新它。
我也要变身
length_of_sequence = 0
length_of_sequence += len(sequence)
进入
length_of_sequence = len(sequence)
def solution(x):
d = {}
for i in range (x, 1, -1):
sequence = []
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence) # This has been de-indented
# because we are not interested
# in the temporary length of the sequence,
# but only in the final one.
d.update({i: length_of_sequence})
return max(d, key=d.get)
打补丁append
目前，每次向序列中追加一个新元素时，您都会 appending 1，因此结果是 4 -> 1 -> 2 -> 1。您只想在末尾附加一次。
def solution(x):
d = {}
for i in range (x, 1, -1):
sequence = []
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
抛光码
现在代码正确，但它很丑陋，这意味着它不是惯用的。我不会在这里争论你的代码为什么和如何应该是惯用的（如果你好奇或不相信，你可以 google 它），所以我假设你 想要 拥有惯用代码（因为每个人都应该想要）。
布尔条件周围的括号
我们不使用 C 或类似 C 的语言，这里 while 和 for 中的布尔条件不应该有括号。
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0:
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
词典更新
您正在使用一种矫枉过正的方法来简单地向字典中添加一个值。这应该是 d[i] = length_of_sequence.
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0:
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
操作赋值shorthand
i = i // 2可以缩短为i //= 2。
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0:
i //= 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
单层短块
这更多是个人喜好，但由于您的一些街区真的很短，所以它们可能是单行的。
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0: i = i // 2
else: i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
顺序range
以相反的顺序进行循环没有意义，所以我们不要这样做！
def solution(x):
d = {}
for i in range(2, x+1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0: i = i // 2
else: i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
性能
还有，瞧！我们已经达到了正确的版本。现在，我们有了正确且惯用的代码，我们可以开始编写更快的代码了。当然，这对于 x 的小值没有用，所以如果您不觉得当前代码很慢，您可能不需要此改进。但是，您可能仍然对如何改进它感到好奇。我们开始了！
瓶颈
当前代码的问题在于，它没有利用这样一个事实，即从本质上讲，从起点计算序列的长度是一个纯和 确定性 函数。我不打算解释它是什么意思，只是声明它提供了一种固定代码的方法。
思路如下。当我计算以 4（即 4 -> 2 -> 1）开头的序列的长度时，我还必须计算其序列。但是，它的序列 (4 -> 2 -> 1) 也严格包含以 2 开头的序列（即 2 -> 1），所以如果我按正确的顺序进行计算，我应该首先计算2的序列长度，然后加一得到4.
的序列长度
这有两个好处。首先，我只为每个数字做一次繁重的工作。其次，我实际上不需要存储序列，我可以直接使用序列的长度（这个优化也可以用你的版本完成）。
为此，我们将在计算出序列长度后，将其从 n 开始存储在字典中。
我们将递归地计算从 x 开始的序列的长度，方法是将从 下一个 数字开始的子序列的长度加一。但是，我们之前会检查我们是否已经计算过它。最后，对 1 和 x 之间的每个 i 执行此操作。
def solution(x):
d = {1: 1}
def collatz(n):
if n not in d: d[n] = (collatz(n//2) if n % 2 == 0 else collatz(3*n+1)) + 1
return d[n]
return max(range(1, x+1), key=collatz)
编辑：应用来自@dont-talk-just-code 的建议。
问题来了，我正在尝试解决它，但我越来越困惑了。
这道题希望你找到一个起始编号，它创建的 Collatz 序列的长度大于使用当前起始编号创建的当前编号，并且该编号必须小于或等于当前编号一.
假设我们最初的起始数字是 4：
4->2->1（3的长度）
3->10->5->16->8->4->2->1（长度为8）
2 -> 1（长度 2）
1（长度1）
现在答案应该是你 return 3，因为 3 小于或等于你的起始数字 4，而且它是唯一一个以它为起始的数字，你会得到一个序列长度大于起始编号的长度，在本例中为 4。
我尝试做一个递减每个的循环，并将当前起始数字和长度添加到字典中，起始数字作为键，长度作为值。然后进去 return 具有更大值（长度）的密钥，但它不起作用。不知道是我写错了还是思路错了...
我觉得它与循环有关，因为 while 循环实际上确实会自己创建正确的序列，当我将它包装在 for 循环中并使用 i 进行计算时，它变得不正确，甚至创建序列时。
def solution(x):
sequence = []
d = {}
length_of_sequence = 0
for i in range (x, 1, -1):
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence += len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
在此先感谢您，我一直在考虑这个问题，但我一无所获，非常感谢您的帮助！
TL;DR
(main, IMO) 问题来自行 length_of_sequence += len(sequence)，因为它应该是 length_of_sequence = len(sequence)，而且您没有在每次迭代时重置 sequence .
但是还有其他多个错误。这是正确的版本。
def solution(x):
d = {}
for i in range(2, x+1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0: i //= 2
else: i = 3*i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
这里有一个更好（更快）的递归方法。
def solution(x):
d = {1: 1}
def collatz(n):
if n not in d: d[n] = (collatz(n//2) if n % 2 == 0 else collatz(3*n+1)) + 1
return d[n]
return max(range(1, x+1), key=collatz)
说明
让我们从您的代码开始，逐步重构到正确的代码，然后继续到更快的代码。
def solution(x):
sequence = []
d = {}
length_of_sequence = 0
for i in range (x, 1, -1):
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence += len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
打补丁sequence
请注意，您只初始化了 sequence 一次，但您一直在追加它，这意味着在第二次迭代中，它已经包含第一次迭代中的元素，因此它的长度严格增加。由于您以 2 结尾，最大值可能是 2。
补丁很简单，只需为您正在查看的每个 i 重新创建序列。
def solution(x):
d = {}
length_of_sequence = 0
for i in range (x, 1, -1):
sequence = []
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence += len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
打补丁length_of_sequence
然而，之前的补丁没有效果，因为您仍然将序列的长度从一个迭代带到下一个迭代，因此您应该在每次迭代时对其进行初始化，并且仅在完成序列后才更新它。 我也要变身
length_of_sequence = 0
length_of_sequence += len(sequence)
进入
length_of_sequence = len(sequence)
def solution(x):
d = {}
for i in range (x, 1, -1):
sequence = []
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence) # This has been de-indented
# because we are not interested
# in the temporary length of the sequence,
# but only in the final one.
d.update({i: length_of_sequence})
return max(d, key=d.get)
打补丁append
目前，每次向序列中追加一个新元素时，您都会 appending 1，因此结果是 4 -> 1 -> 2 -> 1。您只想在末尾附加一次。
def solution(x):
d = {}
for i in range (x, 1, -1):
sequence = []
while(i != 1):
sequence.append(i)
if(i % 2 == 0):
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
抛光码
现在代码正确，但它很丑陋，这意味着它不是惯用的。我不会在这里争论你的代码为什么和如何应该是惯用的（如果你好奇或不相信，你可以 google 它），所以我假设你 想要 拥有惯用代码（因为每个人都应该想要）。
布尔条件周围的括号
我们不使用 C 或类似 C 的语言，这里 while 和 for 中的布尔条件不应该有括号。
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0:
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d.update({i: length_of_sequence})
return max(d, key=d.get)
词典更新
您正在使用一种矫枉过正的方法来简单地向字典中添加一个值。这应该是 d[i] = length_of_sequence.
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0:
i = i // 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
操作赋值shorthand
i = i // 2可以缩短为i //= 2。
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0:
i //= 2
else:
i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
单层短块
这更多是个人喜好，但由于您的一些街区真的很短，所以它们可能是单行的。
def solution(x):
d = {}
for i in range(x, 1, -1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0: i = i // 2
else: i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
顺序range
以相反的顺序进行循环没有意义，所以我们不要这样做！
def solution(x):
d = {}
for i in range(2, x+1):
sequence = []
while i != 1:
sequence.append(i)
if i % 2 == 0: i = i // 2
else: i = 3 * i + 1
sequence.append(1)
length_of_sequence = len(sequence)
d[i] = length_of_sequence
return max(d, key=d.get)
性能
还有，瞧！我们已经达到了正确的版本。现在，我们有了正确且惯用的代码，我们可以开始编写更快的代码了。当然，这对于 x 的小值没有用，所以如果您不觉得当前代码很慢，您可能不需要此改进。但是，您可能仍然对如何改进它感到好奇。我们开始了！
瓶颈
当前代码的问题在于，它没有利用这样一个事实，即从本质上讲，从起点计算序列的长度是一个纯和 确定性 函数。我不打算解释它是什么意思，只是声明它提供了一种固定代码的方法。
思路如下。当我计算以 4（即 4 -> 2 -> 1）开头的序列的长度时，我还必须计算其序列。但是，它的序列 (4 -> 2 -> 1) 也严格包含以 2 开头的序列（即 2 -> 1），所以如果我按正确的顺序进行计算，我应该首先计算2的序列长度，然后加一得到4.
这有两个好处。首先，我只为每个数字做一次繁重的工作。其次，我实际上不需要存储序列，我可以直接使用序列的长度（这个优化也可以用你的版本完成）。
为此，我们将在计算出序列长度后，将其从 n 开始存储在字典中。
我们将递归地计算从 x 开始的序列的长度，方法是将从 下一个 数字开始的子序列的长度加一。但是，我们之前会检查我们是否已经计算过它。最后，对 1 和 x 之间的每个 i 执行此操作。
def solution(x):
d = {1: 1}
def collatz(n):
if n not in d: d[n] = (collatz(n//2) if n % 2 == 0 else collatz(3*n+1)) + 1
return d[n]
return max(range(1, x+1), key=collatz)
编辑：应用来自@dont-talk-just-code 的建议。