问题定义:
这是codewars的问题.
定义一个自反转电源序列，S，为:
S(0) = 0
S(1) = 1
S(2) = 1^2 + 2 = 3
S(3) = 1^3 + 2^2 + 3 = 8
...
S(n) = 1^n + 2^(n-1) + ... + (n-1)^2 + n
实现一个带有 2 个参数(num_dig 和 ord_max)的函数，并找到序列中小于 num dig 的最小数字，它也有 ord_max 个数字。
如果有一个数字的位数正确，结果应该是一个数组，格式如下:
[True, smallest found term]
[False, -1]
这些是一些例子:
n-th Term Term Value
1 0
2 1
3 3
4 8
5 22
6 65
7 209
8 732
9 2780
10 11377
11 49863
12 232768
13 1151914
14 6018785
因此示例测试包括:
min_length_num(5, 10) == [True, 10] # 10th term has 5 digits
min_length_num(7, 11) == [False, -1] # no terms before 13th has 7 digits
min_length_num(7, 14) == [True, 13] # 13th term already has 7 digits
我的方法:
我创建了一个生成器，它生成幂级数 S 的所有值，直到值 n:
def seq(n):
for i in range(n):
s = range(i+1)
j = i+1
tot = 0
while j > 0:
for k in s:
tot += k**j
j -=1
break
yield tot
然后我检查生成器的值，并且:要么在遇到第一个具有所需位数的值时立即返回 True，否则返回 False:
def min_length_num(num_dig, ord_max):
i = 1
for n in seq(ord_max):
if len(str(n)) == num_dig:
return [True, i]
elif len(str(n)) > num_dig:
break
i +=1
return [False, -1]
这通过了所有测试，但由于超时而未完成测试过程。输入范围假定 ord_max <= 1000。
我对生成器不是很精通，所以也许我在那里做错了什么，或者做得不合适。我会很感激一些帮助。谢谢。
编辑:另一个解决方案。
因为我知道 ord_max <= 1000，所以我可以预先计算所有值并修改代码如下:
p = [n for n in seq(1000)]
def min_length_num(num_dig, ord_max):
i = 1
for k in p[:ord_max]:
if len(str(k)) == num_dig:
return [True, i]
elif len(str(k)) > num_dig:
break
i +=1
return [False, -1]
这更快并且解决了我的问题，但我发现它是一个非常丑陋的解决方案，更像是一个肮脏的 hack。我想要更好的东西。
最佳答案
不是完整的解决方案，而是一些优化提示:
您不需要一次又一次地计算自然数的所有幂 - 我怀疑取幂是相当长的操作。而是存储当前功率列表，并在每一步将 power[k] 乘以 k
1 4 3 //3rd stage
1 8 9 4 //4th stage
并用新旧功率之差更新和值
S(4) = S(3) + (8-4) + (9-3) + 4 = 22
同时预先计算所需位数的目标值
powten = 10**(num_dig-1) //1 000 000 for num_dig=7
并在不转换为字符串的情况下将总和与 powten 进行比较
关于python:涉及幂级数的问题的效率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52868811/