在几乎无限的列表中查找元素

Question

我正在尝试解决这个问题：

A list is initialized to ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], and then undergoes a series of operations. In each operation, the first element of the list is moved to the end of the list and duplicated. For example, in the first operation, the list becomes ["Leonard", "Penny", "Rajesh", "Howard", "Sheldon", "Sheldon"] (with "Sheldon" being moved and duplicated); in the second operation, it becomes ["Penny", "Rajesh", "Howard", "Sheldon", "Sheldon", "Leonard", "Leonard"] (with "Leonard" being moved and duplicated); etc. Given a positive integer n, find the string that is moved and duplicated in the nth operation. [paraphrased from https://codeforces.com/problemset/problem/82/A]

我已经写了一个可行的解决方案，但是当 n 很大时它太慢了：

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

 for i in range(n):
    t = l.pop(0)
    l.append(t)
    l.append(t)

    #debug
    # print(l)

print(t)

我怎样才能更快地做到这一点？

Answer 1

你将无法避免计算列表，但也许你可以让它更容易一些：

每个循环（当 sheldon 再次成为第一个时）列表的长度加倍，因此看起来像这样：

1 个周期后：SSLLPPRRHH

2 个周期后：SSSSLLLLPPPPRRRRHHHH

...

而他们喝的可乐数量是 5*((2**n)-1)，其中 n 是循环次数。

所以你可以在最近结束的周期计算列表的状态。例如。 50 号可乐：

5*((2**3)) = 40 表示在喝了 40 杯可乐后，谢尔顿排在下一个。

然后你可以使用任务中描述的算法并得到行中的最后一个。

希望对您有所帮助。

Answer 2

这是一个在 O(log(input/len(l))) 中运行但不进行任何实际计算（无列表操作）的解决方案：

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

i = 0
while n>(len(l)*2**i):
    n = n - len(l)* (2**i)
    i = i + 1

index = int((n-1)/(2**i ))

print(l[index])

说明：每次推回整个列表，列表长度都会增长len(l) x 2^i。但是你必须首先找出这种情况发生了多少次。这就是 while 正在做的事情（这就是 n = n - len(l)* (2**i) 正在做的事情）。当意识到将发生 i 次追加双列表时，while 停止。最后，在计算出 i 之后，您必须计算索引。但是在第 i 个附加列表中，每个元素都被复制 2^i 次，所以你必须将数字除以 2**i。一个小细节是，对于索引，您必须减去 1，因为 Python 中的列表是 0 索引的，而您的输入是 1 索引的。

Answer 3

正如@khelwood 所说，您可以推断出必须将列表加倍的次数。

要理解这一点，请注意，如果您从一个 5 人的列表开始并执行迭代的 5 个步骤，您将获得与之前相同的顺序，只是每个人都在其中两次。

我不是 100% 确定第 n 个位置是什么意思，因为它一直在变化，但如果你指的是 n 次迭代后前面的人，请求解满足

的最大整数 i

5*2^i<n

获取列表翻倍的次数。然后只看剩下的列表（每个名字被提到 i 次）得到位置 n-5*2^i.

的名字

在几乎无限的列表中查找元素

Find the element in virtually infinite list

python

algorithm

math

implementation