>假设有n个囚犯站成一圈。第一个囚犯有一把刀，他用刀杀死第二个囚犯，并将刀交给杀死第四个囚犯的第三个人，并将刀交给第五个囚犯。
重复这个循环，直到只剩下一个囚犯。请注意，囚犯站成一圈，因此第一个囚犯紧挨着第 n 个囚犯。返回最后一个站立囚犯的索引。
我尝试使用循环链表实现解决方案。这是我的代码
循环链表的结构是：-
struct Node
{
int Data;
Node *Next;
};
Node *Head = NULL;
这是我的 deleteByAddress(( 和 main(( 函数：-
inline void deleteByAddress(Node *delNode)
{
Node *n = Head;
if(Head == delNode)
{
while(n -> Next != Head)
{
n = n -> Next;
}
n -> Next = Head -> Next;
free(Head);
Head = n -> Next;
return ;
}
while(n -> Next != delNode)
{
n = n -> Next;
}
n -> Next = delNode -> Next;
delete delNode;
}
int main(void)
{
for(int i = 1 ; i <= 100 ; i++)
insertAtEnd(i);
Node *n = Head;
while(Head -> Next != Head)
{
deleteByAddress(n -> Next);
n = n -> Next;
}
cout << Head -> Data;
return 0;
}
上面的代码运行良好，并在 n = 100 时生成所需的输出，即 73。
有什么方法可以降低时间复杂度或使用更有效的数据结构来实现相同的问题。
这被称为约瑟夫斯问题。正如维基百科页面显示和其他人所指出的那样，有一个公式可以说明k何时为 2。一般复发率
// zero-based Josephus
function g(n, k){
if (n == 1)
return 0
return (g(n - 1, k) + k) % n
}
console.log(g(100, 2) + 1)使用以下命令可以轻松解决O(1)复杂性
last = (num - pow(2, int(log(num)/log(2)))) * 2 + 1
例如，对于num= 100 ：
last = (100 - pow(2, int(log(100)/log(2)))) * 2 + 1 = 73
如果你有log2()函数，你可以替换一个有点丑陋的log(num)/log(2)它基本上以 2 为底的对数。
使用 1 个循环。您可以在每次迭代时抓取当前迭代的下一个，然后将当前设置为下一个下一个，然后删除下一个。
这假设所有数据都是事先设置的，并且在达到边界时忽略下一个变量的重写。
降低时间复杂度的诀窍是提出比通过模拟暴力破解更聪明的算法。
在这里，和往常一样，关键显然是解决数学问题。例如，第一个循环用i%2=1杀死每个人(假设基于 0 的索引(，第二个循环杀死每个人的i%4=(n+1)%2*2左右等等 - 我正在寻找一个封闭的形式来直接计算幸存者。它可能会归结为一些位操作，产生一个几乎即时实践的 O(log n( 算法，因为所有算法都完全在 CPU 寄存器中运行，甚至没有 L1 缓存访问。
对于如此简单的处理，列表操作和内存分配将主导计算，您可以只使用一个数组，其中您有一个索引到第一个活着的元素，每个元素都是下一个活着的索引。
也就是说，您确实可以搜索一个避免循环的公式......例如，如果囚犯的数量是偶数，那么在第一个"循环"之后，你最终会得到一半的囚犯和刀回到第一个囚犯的手中。这意味着当n是偶数时，幸存囚犯的指数是
f(n) = 2 * f(n / 2) # when n is even
万一n奇怪，事情有点复杂......在第一个循环之后，你最终会得到(n + 1)/2囚犯，但最后一个手中的刀，所以需要一些模算术，因为你需要"调整"递归调用的结果f((n + 1)/2)。
减少时间复杂度的方法是，在大多数情况下，由于时间过长的原因而失败的挑战，不要模拟和使用数学。运气好的话，它变成了单行本。
该算法可以大大加快，如果您更改为：
请注意，对于囚犯总数(2的幂(，始终索引0将存活。
对于其他情况：
- 确定低于或等于囚犯人数的 2 的最高幂
- 确定 R，其余的当将囚犯人数减少 2 的幂时
- 最终幸存下来的囚犯将是杀死该数量的囚犯后获得刀的人
试图找出那是哪个囚犯。
5名囚犯(1比2高2，R=1(的情况：
01234
Deaths 1: x x
Deaths 2:x x
last : O
6 的情况 (R=2(：
012345
Deaths 1: x x x
Deaths 2:x x (index 4 kills index 0 after index 2 was killed by index 0)
last : O
7 的情况 (R=3(：
0123456
Deaths 1:xx x x (index 6 kills index 0 after index 5 was killed by index 2)
Deaths 2: x x (index 6 kills index 2 after index 4 was killed by index 2)
last : O
8 的情况是 2 的下一个幂，索引 0 幸存。
最后，最终的幸存者总是索引 2*R 处的那个.因此，您只需要确定 R.
在对数量级到总数的底数 2 的时间复杂度中最坏的情况下，这应该是可能的。