一个Python编码练习要求生成一个函数f,使得f(k)是第k个数字,使得它从左到右的第k个数字和所有k的10。例如,5, 19, 28, 37
是序列中的前几个数字。在
我使用这个函数显式检查数字“n”是否满足属性:
def check(n):
#even digit length
if len(str(n)) % 2 == 0:
#looping over positions and checking if sum is 10
for i in range(1,int(len(str(n))/2) + 1):
if int(str(n)[i-1]) + int(str(n)[-i]) != 10:
return False
#odd digit length
else:
#checking middle digit first
if int(str(n)[int(len(str(n))/2)])*2 != 10:
return False
else:
#looping over posotions and checking if sum is 10
for i in range(1,int(len(str(n))/2) + 1):
if int(str(n)[i-1]) + int(str(n)[-i]) != 10:
return False
return True
然后我循环所有的数字生成序列:
^{pr2}$然而,这个练习需要一个函数f(i),它在10秒内返回第i个这样的数字。显然,我的方法需要更长的时间,因为它在数字'i'之前生成整个序列来计算它。有没有可能做一个不需要计算所有先前数字的函数?在
测试每一个自然数是一个糟糕的方法。只有一小部分的自然数具有这种性质,并且当我们得到更大的数时,分数会迅速减少。在我的机器上,下面的简单Python程序花了3秒多的时间找到第1000个数字(2195198),用了26秒找到第2000个数字(15519559)。在
显然,需要一个更有效的算法。在
我们可以在数字字符串的长度上循环,在这个长度内,按照数字顺序生成带有属性的数字。伪码算法示意图:
^{pr2}$现在,请注意,每个长度的数字计数很容易计算:
通常,如果左半部分有
n
个数字,则计数为9**n
。在因此,我们可以简单地迭代数字计数,计算出存在多少个解,而不必计算它们,直到我们到达包含所需答案的队列为止。然后,计算出我们想要的数字应该相对简单,同样,不需要迭代所有的可能性。在
上面的草图应该会产生一些想法。一旦我写好了要遵循的代码。在
代码:
这是一个利用模式的函数,其中相邻的10次方之间的“有效”数是9的幂次方。这使我们可以跳过很多数字。在
我把这个和你定义的方法结合起来。如果我们对第45个号码感兴趣, 这说明搜索从1000开始,我们只需要找到1000之后的第26个“有效”数字。保证不到1万。当然,这种限制在规模上越来越差,您可能希望使用本文中其他社区成员建议的技术。在
^{pr2}$输出:
第45个号码好像是3827。在
相关问题 更多 >
编程相关推荐