寻找数字河流的汇合点
寻找数字河流的汇合点
提问于 2020-02-24 20:26:22
我被问到以下问题：
数字河流(
)数字河流是一个数字序列，每个数字后面跟着相同的数字加上它的数字之和。在这样的序列中，123后面跟着129 (因为1+2+3= 6)，然后又是141。
我们称之为数字河流K，如果它以值K开头，例如：
7河是以{7，14，19，29，40，44，52，.}和
471是以{471,483,498,519，…}开头的序列。
数字河流可以相遇。当两条数字河流共享相同的值时，就会发生这种情况。河流32在47时遇到河流47，而河流471在519与河480相遇。
给两条相遇的数字河流，打印出汇合点。
为了解决这个问题，我编写了以下代码(r_1和r_2是河流的起点)：
r_1 = [int(input())]
r_2 = [int(input())]
while True:
r_1.append(r_1[-1] + sum([int(d) for d in str(r_1[-1])]))
r_2.append(r_2[-1] + sum([int(d) for d in str(r_2[-1])]))
if r_2[-1] in r_1:
print(r_2[-1]),
break
elif r_1[-1] in r_2:
print(r_1[-1])
break这个代码可以工作，但是当r_1或r_2很大时，而且汇合点在河中很远，计算时间就太长了。我使用了一个while循环和两个if语句，所以我看不出如何改进这段代码。
我怎样才能减少时间呢？
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-02-24 20:48:14
很明显，数字河流是一个不断增长的系列，它永远不会减少。因此，要找到两个连接点，只需跟踪两条河流的当前值，并且只更新值最少的河流。如果它超过了另一个，那么推进other...etc，直到得到相同的值。
同样，您只需要以这种方式保持更新的值。没有理由建立一个列表。
示例：
a = 471
b = 480
while a != b:
if a < b:
a += sum([int(d) for d in str(a)])
else:
b += sum([int(d) for d in str(b)])
print(a) # 519Stack Overflow用户
发布于 2020-02-24 20:42:04
您正在向两个列表中添加新项目，而不管它们之间的距离有多大。只尝试计算河流中值较低的下一步，而不是两者都计算，这可能导致不必要的额外计算。
while True:
# if its found, break
if r_1[-1] == r_2[-1]:
print(r_1[-1])
break
else:
# if r_1 is larger, only increment r_2
if r_1[-1] > r_2[-1]:
r_2.append(r_2[-1] + sum([int(d) for d in str(r_2[-1])]))
# if r_2 is larger, only increment r_1
elif r_1[-1] < r_2[-1]:
r_1.append(r_1[-1] + sum([int(d) for d in str(r_1[-1])]))注意:这也没有指定一个上限，所以如果河流永远不匹配的话，可能会永远运行。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60383430
复制相关文章
相似问题
腾讯云开发者
