数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究剑谜的代码解决方案
我们将讨论两种解决剑谜的方法。在第一种方法中，我们将使用循环链表，而第二种方法基于一般的直觉。在本文中，我们将讨论什么是剑谜问题以及如何解决剑谜问题。
问题陈述
我们在一个圆圈中排列了 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、C++、Java 和 Python -
#include <stdio.h>
#include <stdlib.h>
// Defining the linked list as Soldier
struct Soldier {
int data;
struct Soldier* next;
};
struct Soldier* newSoldier(int data) {
struct Soldier* soldier = (struct Soldier*)malloc(sizeof(struct Soldier));
if (soldier == NULL) {
// Handle memory allocation failure
exit(EXIT_FAILURE);
}
soldier->data = data;
soldier->next = NULL;
return soldier;
}
// This function calculates the luckiest person alive
int Luckiest(int N) {
if (N == 1)
return 1;
struct Soldier* last = newSoldier(1);
last->next = last;
for (int iterator = 2; iterator <= N; iterator++) {
struct Soldier* dummy = newSoldier(iterator);
dummy->next = last->next;
last->next = dummy;
last = dummy;
}
struct Soldier* current = last->next;
struct Soldier* dummy;
while (current->next != current) {
dummy = current;
current = current->next;
dummy->next = current->next;
free(current);
dummy = dummy->next;
current = dummy;
}
int result = dummy->data;
free(dummy);
return result;
}
int main() {
int N = 100;
printf("The luckiest person alive at last is the person numbered as %d\n", Luckiest(N));
return 0;
}
输出
The luckiest person alive at last is the person numbered as 73
#include <bits/stdc++.h>
using namespace std;
// Defining the linked list as soldier
struct Soldier {
int data;
struct Soldier* next;
};
Soldier *newSoldier(int data){
Soldier *soldier = new Soldier;
soldier->data = data;
soldier->next = NULL;
return soldier;
}
// This function calculates the luckiest person alive
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 << "The luckiest person alive at last is the person numbered as " << Luckiest(N)<< endl;
return 0;
}
输出
The luckiest person alive at last is the person numbered as 73
class Soldier {
int data;
Soldier next;
Soldier(int data) {
this.data = data;
this.next = null;
}
}
public class LuckiestPerson {
static Soldier newSoldier(int data) {
return new Soldier(data);
}
// This function calculates the luckiest person alive
static 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 = null; // Initialize dummy to null
while (current.next != current) {
dummy = current;
current = current.next;
dummy.next = current.next;
dummy = dummy.next;
current = dummy;
}
if (dummy != null) {
return dummy.data;
} else {
// Handle the case where dummy is not initialized
System.err.println("Error: dummy not initialized");
return -1; // or some other appropriate error value
}
}
public static void main(String[] args) {
int N = 100;
System.out.println("The luckiest person alive at last is the person numbered as " + luckiest(N));
}
}
输出
The luckiest person alive at last is the person numbered as 73
class Soldier:
def __init__(self, data):
self.data = data
self.next = None
def new_soldier(data):
soldier = Soldier(data)
soldier.next = None
return soldier
# This function calculates the luckiest person alive
def luckiest(N):
if N == 1:
return 1
last = new_soldier(1)
last.next = last
for iterator in range(2, N + 1):
dummy = new_soldier(iterator)
dummy.next = last.next
last.next = dummy
last = dummy
current = last.next
dummy = None
while current.next != current:
dummy = current
current = current.next
dummy.next = current.next
dummy = dummy.next
current = dummy
return dummy.data
def main():
N = 100
print("The luckiest person alive at last is the person numbered as", luckiest(N))
if __name__ == "__main__":
main()
输出
The luckiest person alive at last is the person numbered as 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 个士兵将最后存活。
示例
以下是不同编程语言中上述方法的实现：C、C++、Java 和 Python -
#include <stdio.h>
#include <stdlib.h>
// Function to calculate largest number (which can be represented as a power of 2) smaller than the given number
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;
}
// main code goes here
int main() {
int number=100;
int m= Power_of_two(number);
int p;
p=number-m;
printf(" The luckiest person alive is person numbered as %d ", (2*(p)) +1);
return 0;
}
输出
The luckiest person alive is person numbered as 73
#include <bits/stdc++.h>
using namespace std;
// Function to calculate largest number (which can be represented as a power of 2) smaller than the given number
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;
}
// main code goes here
int main(){
int number=100;
int m= Power_of_two(number);
int p;
p=number-m;
cout<< " The luckiest person alive is person numbered as " <<(2*(p)) +1;
return 0;
}
输出
The luckiest person alive is person numbered as 73
public class Main {
// Function to calculate largest number (which can be represented as a power of 2) smaller than the given number
public static 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;
}
public static void main(String[] args) {
int number=100;
int m= Power_of_two(number);
int p;
p=number-m;
int res = (2*(p)) + 1;
System.out.println(" The luckiest person alive is person numbered as " + res);
}
}
输出
The luckiest person alive is person numbered as 73
# Function to calculate the largest number (which can be represented as a power of 2) smaller than the given number
def power_of_two(number):
result = 0
for iterator in range(number, 0, -1):
if (iterator & (iterator - 1)) == 0:
result = iterator
break
return result
# main code goes here
number = 100
m = power_of_two(number)
p = number - m
print("The luckiest person alive is person numbered as", (2 * p) + 1)
输出
The luckiest person alive is person numbered as 73
时间复杂度 - 此方法的时间复杂度为 O(n)
空间复杂度 - 由于我们仅使用常量空间来存储变量，因此空间复杂度将为 O(1)。
结论
在本文中，我们讨论了两种解决剑谜问题的方法。在第一种方法中，我们使用了循环链表，并不断删除在此过程中死亡的每个节点，最后一个剩下的元素是最幸运的存活士兵。在我们的第二种方法中，我们创建了一个直观的公式来找到我们的解决方案。
更新于： 2024 年 2 月 9 日
304 次查看
广告