我正在尝试编码(全天(数字生成系统，它从 3 开始，值减少 1 直到达到 1。一旦达到 1，它就会将其数字重置为新的起始值，作为第一个数字的 2 倍。然后用每个新的重置 2x 作为先前重置的第一个数字。如波纹管所示，
3 2 1 6 5 4 32 1 12 11 10 9 8 7 6 5 4 3 2 1...
程序应返回用户请求的第n 个位置的值。
用户可以输入 n <(10^12(
如果目标位置远离循环的当前位置，则尝试跳过一些步骤
# requesting position
tt = int(input())
# starting t
t = 1
# starting value
sv = 3
# current value
cv = 3
while (True):
# check if we have reached target time
if (t == tt):
# print the current value
print("{}".format(cv))
break
# if there's a loong way to go, skip some
if (t + cv < tt): # starting_t+current_value<target_t
t += cv
sv = sv * 2
cv = sv
if cv % 2 == 0:
if (t + cv // 2 < tt):
t += cv // 2
cv = cv // 2
continue
continue
# check if value is 1 and double it
if (cv == 1):
# set new starting value
sv = sv * 2
# set new current value
cv = sv
# elapse time
t += 1
continue
# elapsed time
t += 1
# changed value
cv -= 1
目前，此程序需要 2 分钟以上才能返回n>10^10的结果。我需要尽可能减少该过程所需的时间。我能做些什么来减少该过程所需的时间？(期望将其减少到几秒钟(任何参考都可能有所帮助
总结
你可以只做(索引从0开始，否则你需要用n - 1替换n(：
def my_seq(n):
k = int(math.log2(n / 3 + 1)) + 1
return 3 * (2 ** k - 1) - n
print([my_seq(i) for i in range(2)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
这基本上是步长等于 2 的几何级数的变体，如下所示。
解释
第一步是注意"峰"的基本序列是一个几何级数：
x_k = a * r ** k
几何级数的前 n 项之和是几何级数：
sum(x_k for k in 1 to n) = a * (1 - r ** n) / (1 - r)
目标序列基本上是通过从不超过索引本身的序列的最大项中减去索引来获得的。
在代码中，这看起来像：
# note that this uses integer division hence expects integer `r`
def geom_series_int(a, r, n):
return a * (1 - r ** n) // (1 - r)
def my_seq_int(n, a=3, r=2):
i = 1
cumsum = geom_series_int(a, r, i)
while cumsum < n + 1:
i += 1
cumsum = geom_series_int(a, r, i)
return cumsum - n
print([my_seq_int(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
当然，人们也可以迭代计算几何级数，这将具有与上述代码相似的计算效率，因为找到不超过索引n的最小cumsum是通过循环完成的，但上面的代码更快：
def i_geom_progression(a, r):
i = 0
while True:
yield a * r ** i
i += 1
def i_geom_series(a, r):
gp = i_geom_progression(a, r)
result = next(gp)
while True:
yield result
result += next(gp)
def my_seq(n, a=3, r=2):
gs = i_geom_series(a, r)
cumsum = next(gs)
while cumsum < n + 1:
cumsum = next(gs)
return cumsum - n
print([my_seq(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
这两种情况下的计算复杂度都是log(n)。
更有效的方法是通过求解几何级数的表达式k并使用索引n作为累积总和的代理来分析执行此操作：
n = a * (r ** k - 1) / (r - 1)
成为：
k = log_r(1 - n * (1 - r) / a)
而作为不可或缺的一部分，这变成了：
import math
def my_seq_analytic(n, a=3, r=2):
k = int(math.log2(1 - n * (1 - r) / a) / math.log2(r)) + 1
return geom_series_int(a, r, k) - n
print([my_seq_analytic(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
这是最快的方法。
总的来说，所提出的方法比最初提出的方法快得多，其简化如下my_seq_loop()报告：
def my_seq_loop(n, a=3, r=2):
peak = a
for i in range(1, n + 1):
if a == 1:
peak *= r
a = peak
else:
a -= 1
return a
print([my_seq_loop(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
给出一些时间的想法，请参阅下面的基准：
%timeit my_seq_loop(10 ** 8)
# 1 loop, best of 3: 6.65 s per loop
%timeit my_seq(10 ** 8)
# 100000 loops, best of 3: 14.1 µs per loop
%timeit my_seq_int(10 ** 8)
# 100000 loops, best of 3: 11.7 µs per loop
%timeit my_seq_analytic(10 ** 8)
# 1000000 loops, best of 3: 938 ns per loop
(已编辑以修复分析代码中的错误，其中使用整数除法而不是常规除法(。
您可以在没有任何循环的情况下计算答案：
n重置后，您的号码3*2^n。因此，您已经完成了 3*(2^{n}-1( 步骤。
所以，如果用户输入了数字x，你需要找到到目前为止你做了多少次重置(这是log_2(x/3)的整数值(，让我们调用R这个数字，并找出自这次重置以来你又执行了多少步，让我们称这个数字为S。
那么你的解决方案是3*(2^{R}-1) - S.
检查一下这个工作的简单例子，我可能在数学上做了一个 mstake，但方法应该没问题。
简单地说，你可以做到：
def get_n_th_number(x, n):
if n <= x:
return x - n + 1
return get_n_th_number(2 * x, n - x)
x = 3
assert get_n_th_number(x, 1) == 3
assert get_n_th_number(x, 3) == 1
assert get_n_th_number(x, 4) == 6
assert get_n_th_number(x, 9) == 1
assert get_n_th_number(x, 10) == 12
时间复杂度：log2(n / x)
空间复杂度：log2(n / x)(由于递归。
这个问题可以通过分析来解决，而无需如上所述迭代数字和计算。终于能够解决问题了(当然是在帮助下(
import math
def get_n_th(t):
a=math.log((t/3)+1,2) #if you input t,you need to get how many resets have done == integer value of log((t/3)+1, 2)
# it always returns value > 0, even for the first reset (which is n need to be equal to zero) so we have to round number to least significant figures to get the correct reset value and substract 1 reset to get actual reset count
# (3,2,1), (6,5,4,3,2,1), (12,11,10...)
# ^ ^ ^
# 0th reset 1st reset 2nd reset
#Bellow condition used to round number to least significant figures and sustract 1 reset. For further clarification please refer how log_2(n) return value and mentioned theory in the answer
if(a%1 == 0):
n = int(a-1) # here n is equals to how many resets
print("if")
else:
n = int(a)
#here n gives how many resets occured
#3*2**n will give the starting number of the last reset ---(1)
#(t-3*(2**n-1))-1) will return how many steps remaining ---(2)
# the difference between (1)-(2) will give the value in t position
return (3*2**n)-((t-3*(2**n-1))-1)
#or simplified equation
#return 3 * 2 ** (n + 1) - t - 2
input = int(input()) #input the position
print(get_n_th(input))
print("[*] Ended in %.3f seconds." % (time.time() - start_time))
为了理解这段代码，你必须参考这个理论和答案。并且还需要知道log_2(n(的行为。