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

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

正如@khelwood所说的，你可以推断出你需要加倍的次数。你知道吗

要理解这一点，请注意，如果您从5个人的列表开始，并在迭代过程中执行5个步骤，那么您将使用与以前相同的顺序，每个人只需重复两次。你知道吗

我不是100%确定你说的第n个位置是什么意思，因为它一直在移动，但是如果你指的是在n次迭代之后在前面的那个人，求出满足的最大整数I

5*2^i<n 

你的单子翻了一倍。然后只看剩下的列表（每个名字都被提到i次），得到位于n-5*2^i位置的名字

Answer 2

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

每一个周期（当谢尔顿再次成为第一个）列表的长度都会翻倍，所以看起来是这样的：

1次循环后：SSLLPPRRHH

2次循环后：ssssllpprprrrhhhh

。。。你知道吗

而他们喝可乐的次数是5*（（2**n）-1），其中n是循环次数。你知道吗

因此，您可以计算最近结束循环时列表的状态。 例如。 可乐50号：

5*（（2**3））=40意味着40杯可乐之后，谢尔顿是下一位。你知道吗

然后您可以使用任务中描述的算法，得到行中的最后一个算法。你知道吗

希望这有帮助。你知道吗

Answer 3

下面是一个在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)正在做的事情）。while在意识到将发生i次追加双列表时停止。最后，在您计算出i之后，您必须计算索引。但是在出现的第i个列表中，每个元素都被复制2^i次，因此您必须按2**i对数字进行划分。一个小细节是索引必须减去1，因为Python中的列表是0索引的，而输入是1索引的。你知道吗