python - 生成数字序列,其从左边和右边的第 k 个数字总和为 10,对于所有 k
问题描述
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
然后我遍历所有数字以生成序列:
for i in range(1, 10**9):
if check(i):
print(i)
然而,练习需要一个函数 f(i),它在 10 秒内返回第 i 个这样的数字。显然,我的需要更长的时间,因为它会在数字“i”之前生成整个序列来计算它。是否可以创建一个不必计算所有先前数字的函数?
解决方案
测试每个自然数是一种不好的方法。只有一小部分自然数具有这种性质,当我们进入更大的数字时,这个比例会迅速减少。在我的机器上,下面的简单 Python 程序用了 3 秒多的时间找到了第 1,000 个数字 (2,195,198),用了 26 秒的时间找到了第 2,000 个数字 (15,519,559)。
# Slow algorithm, only shown for illustration purposes
# '1': '9', '2': '8', etc.
compl = {str(i): str(10-i) for i in range(1, 10)}
def is_good(n):
# Does n have the property
s = str(n)
for i in range((len(s)+1)//2):
if s[i] != compl.get(s[-i-1]):
return False
return True
# How many numbers to find before stopping
ct = 2 * 10**3
n = 5
while True:
if is_good(n):
ct -= 1
if not ct:
print(n)
break
n += 1
显然,需要一种更有效的算法。
我们可以遍历数字字符串的长度,并在其中以数字顺序生成具有属性的数字。伪代码中的算法草图:
for length in [1 to open-ended]:
if length is even, middle is '', else '5'
half-len = floor(length / 2)
for left in (all 1) to (all 9), half-len, without any 0 digits:
right = 10's complement of left, reversed
whole-number = left + middle + right
现在,请注意,每个长度的数字计数很容易计算:
Length First Last Count
1 5 5 1
2 19 91 9
3 159 951 9
4 1199 9911 81
5 11599 99511 81
一般来说,如果左半边有n
数字,则计数为9**n
。
因此,我们可以简单地遍历数字计数,计算存在多少解决方案而无需计算它们,直到我们到达包含所需答案的群组。然后,再次计算我们想要的数字应该相对简单,而不必遍历所有可能性。
上面的草图应该会产生一些想法。写完后要遵循的代码。
代码:
def find_nth_number(n):
# First, skip cohorts until we reach the one with the answer
digits = 1
while True:
half_len = digits // 2
cohort_size = 9 ** half_len
if cohort_size >= n:
break
n -= cohort_size
digits += 1
# Next, find correct number within cohort
# Convert n to base 9, reversed
base9 = []
# Adjust n so first number is zero
n -= 1
while n:
n, r = divmod(n, 9)
base9.append(r)
# Add zeros to get correct length
base9.extend([0] * (half_len - len(base9)))
# Construct number
left = [i+1 for i in base9[::-1]]
mid = [5] * (digits % 2)
right = [9-i for i in base9]
return ''.join(str(n) for n in left + mid + right)
n = 2 * 10**3
print(find_nth_number(n))
推荐阅读
- android - 线圈 ImageView 不完全适合
- android - 错误:无法解决:com.github.glomadrian:MaterialAnimatedSwitch:1.1
- node.js - 为 cron 作业注入的服务未定义
- php - Laravel Eloquent 中的“刷新模型”是什么,请帮助我理解这一点
- rest - API PUT 端点是否应该接收所有参数,即使它们不可编辑?
- ruby - 如何使用 ruby 将文本嵌入到黄瓜报告中?
- google-bigquery - 将 Bigquery 结果写入 Datalab 中的 Bigquery
- azure - 通过直接 URL 浏览时上传到 Azure Blob 存储的图像不可用
- java - 为什么 LeakedConnectionCount 在 weblogic 中总是 0?
- button - 如何仅在释放按钮时使连续旋转伺服移动45度?