剑谜代码解决方案
我们将讨论两种解决剑谜的方法。在第一种方法中，我们将使用循环链表，而第二种方法则基于一般直觉。在本文中，我们将讨论什么是剑谜问题以及如何解决剑谜问题。
问题陈述
我们将 n 个人排成一圈，其中第一个人拿着剑。第一个人杀死第二个人，并将剑交给圈中的下一个活着的人。现在，下一个拿着剑的人杀死下一个人，并将剑交给下一个活着的人。这个过程一直持续到只剩下一个人。我们称唯一活着的人为最幸运的人。现在让我们通过一个例子来考虑这种情况。
示例
N=10
我们有 10 个人排成一个圆圈，即人 1、人 2 ...、人 10、人 1。
首先，人 1 杀死了人 2，并将剑交给了人 3。
因此，从人 1 到人 10 经过 1 次迭代后，我们得到了一个活着的人列表，即 {人 1、人 3、人 5、人 7、人 9
并且人 1 拿着剑，现在在下一次迭代中，我们又得到了一个活着的人列表，即:{人 1、人 5、人 9}，并且人 9 拿着剑。
在下一次迭代中，我们得到了活着的人作为第 5 个人
因此，我们可以说最幸运的人是活到最后的第 5 个人。
方法 1:使用循环链表
我们首先使用循环链表解决难题。为此，我们将首先创建一个循环链表，其中有 n 个不同的节点代表 n 个不同的士兵，然后开始迭代链表。根据规则，我们必须杀死一个相邻的士兵并将剑交给下一个活着的人，并重复此操作，直到只剩下一个人，我们将通过删除相邻的链表来表示被杀的士兵，最后一个剩余的链表代表活着的士兵。
示例
以下是剑谜题的 C++ 程序。本代码采用循环链表实现。
#include <bits/stdc++.h>
using namespace std;
// 将链表定义为 soldier
struct Soldier {
int data;
struct Soldier* next;
};
Soldier *newSoldier(int data){
Soldier *soldier = new Soldier;
soldier->data = data;
soldier->next = NULL;
return soldier;
}
// 此函数计算出最幸运的人
int Luckiest (int N){
if (N == 1)
return 1;
Soldier *last = newSoldier(1);
last->next = last;
for (int iterator = 2; iterator <= N; iterator++) {
Soldier *dummy = newSoldier(iterator);
dummy->next = last->next;
last->next = dummy;
last = dummy;
}
Soldier *current = last->next;
Soldier *dummy;
while (current->next != current) {
dummy = current;
current = current->next;
dummy->next = current->next;
delete current;
dummy = dummy->next;
current = dummy;
}
int result = dummy->data;
delete dummy;
return result;
}
int main(){
int N = 100;
cout << "最后活着的最幸运的人是被编号为 " << Luckiest(N)<< endl;
return 0;
}
输出
编译上述 C++ 程序时，将产生以下输出 -
最后活着的最幸运的人是被编号为 73
由于我们遍历 n 个元素的循环，时间复杂度为 O(n)。
空间复杂度 - 由于我们为链表使用了额外的空间，空间复杂度为 O(n)
方法 2
在这种方法中，我们将推导出一种凭直觉计算最幸运元素的方法。如果士兵的数量可以表示为 2 的幂，那么我们可以说第一个开始杀戮过程的士兵最终会活下来。我们知道，每次迭代后，士兵的数量都会减少 2，没有任何余数。因此，每次迭代开始时，我们都会让第一个士兵自动携带剑，并且这种情况会一直持续，但第一个士兵永远不会被杀死。
如果我们的士兵数量不是 2 的幂，那么在第一次迭代中，当士兵数量变为 2 的幂时，那时带剑的士兵将获胜。这背后的直觉是:当士兵数量变为 2 的幂时，我们可以假设这是一个新的谜题，士兵数量为 2 的幂，带剑的士兵是第一个士兵。我们将首先推导出一种实现此方法的方法。
步骤 1 - 找到小于给定数字的最大数字(可以表示为 2 的幂)。让它成为 m。
步骤 2 - 从给定的数字"n"中减去 m。
步骤 3 - 现在，将 m 乘以 2 以了解被杀的人数。
步骤 4 - 最后，我们将在第 (2*m+1) 个士兵手中拿着剑，因此最后有 2m+1 个士兵活着。
示例
在下面的示例中，我们实现了上面讨论的方法
#include <bits/stdc++.h>
using namespace std;
// 函数用于计算小于给定数字的最大数字(可以表示为 2 的幂)
int Power_of_two(int number){
int result = 0;
for (int iterator = number; iterator >= 1; iterator--) {
if ((iterator & (iterator - 1)) == 0){
result = iterator;
break;
}
}
return result;
}
// 主要代码放在这里
int main(){
int number=100;
int m= Power_of_two(number);
int p;
p=number-m;
cout<< " 最后活着的最幸运的人是被编号为 " <<(2*(p)) +1;
return 0;
}
输出
编译时，上述 C++ 程序将产生以下输出 -
最后活着的最幸运的人是被编号为 73
时间复杂度 - 这种方法的时间复杂度为 O(n)
空间复杂度 - 由于我们仅使用常量空间来存储 od 变量，因此空间复杂度将为 O(1)。
在本文中，我们讨论了两种解决剑谜问题的方法。在第一种方法中，我们使用了一个循环链表，并不断删除过程中死亡的每个节点，剩下的最后一个元素就是最幸运的活着的士兵。在第二种方法中，我们创建了一个直观的公式来找到解决方案。
