gpt4 book ai didi

c++ - 有没有办法降低程序的时间复杂度?

转载 作者:太空狗 更新时间:2023-10-29 20:33:02 28 4
gpt4 key购买 nike

Assume there are n prisoners standing in a circle. The first prisoner has a knife with which he kills the second prisoner and passes on the knife to the third person who kills the fourth prisoner and passes the knife to the fifth prisoner.

This cycle is repeated till only one prisoner is left. Note that the prisoners are standing in a circle, thus the first prisoner is next to the nth prisoner. Return the index of the last standing prisoner.

我尝试使用循环链表来实现该解决方案。这是我的代码

循环链表的结构是:-

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。

有什么办法可以降低时间复杂度或使用更高效的数据结构来实现同样的问题。

最佳答案

这被称为 Josephus problem .正如维基百科页面所示和其他人所指出的,当 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)

关于c++ - 有没有办法降低程序的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57743695/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com