分别用c++,python,java写一个解决约瑟夫环问题的代码

问题描述

约瑟夫环问题是一个经典的数学和计算机科学问题，它涉及到一组人（通常用编号表示），围坐成一个圈，然后依次报数，每报到指定的数字的人将被淘汰，直到最后剩下一个人。
分别用c++,python,java写一个约瑟夫环问题的算法解决方案，将被报到的人依次打印出来，人数为8，报数为：5。

代码示例

以下是C++、Python 和 Java 中分别解决约瑟夫环问题的算法解决方案，其中有8个人，每次报数为5，并打印出被报数的人：

C++ 示例：

#include 
using namespace std;
struct node{
    long d;
    node * next;
};
long n,m;
node * head, * p, * r;
int main(){
    long i,j,k,l;
    int n=8,m=5;
    head = new node;
    head->d = 1; head->next = NULL;r=head;
    for(i=2;i<=n;i++){
        p = new node;
        p->d=i;
        p->next=NULL;
        r->next = p;
        r=p;
    }
    r->next=head;r=head;
    for(i=0;i<n;i++){
        for(j=1;j<=m-2;j++){
            r=r->next;
        }
        cout<<r->next->d<<" ";
        r->next = r->next->next;
        r=r->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Python 示例：

def josephus(n, k):
    people = list(range(1, n + 1))
    index = 0

    print("约瑟夫环问题解决方案:")
    while len(people) > 0:
        index = (index + k - 1) % len(people)
        print("出局的人:", people.pop(index))



if __name__ == '__main__':
    n = 8  # 8个人
    k = 5  # 报数为5
    josephus(n, k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Java 示例：

import java.util.LinkedList;

public class JosephusProblem {
    public static void josephus(int n, int k) {
        LinkedList<Integer> people = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            people.add(i);
        }

        int index = 0;
        System.out.println("约瑟夫环问题解决方案:");
        while (!people.isEmpty()) {
            index = (index + k - 1) % people.size();
            int eliminatedPerson = people.remove(index);
            System.out.println("出局的人: " + eliminatedPerson);
        }
    }

    public static void main(String[] args) {
        int n = 8; // 8个人
        int k = 5; // 报数为5

        josephus(n, k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

解题思路

解决约瑟夫环问题的一种常见方法是使用模拟，具体思路如下：

java和python通过取模来定位

下列代码，java和python用了这个核心代码：

index = (index + k - 1) % people.size();
int eliminatedPerson = people.remove(index);
System.out.println("出局的人: " + eliminatedPerson);
1
2
3

index = (index + k - 1) % len(people)
print("出局的人:", people.pop(index))
1
2

它实际上是在模拟报数和淘汰的过程。

这行代码的作用是根据当前的 index 和指定的报数值 k 计算出下一个被淘汰的人的索引。让我解释一下为什么这个公式是正确的：

1. index 表示当前报数的人的索引，初始为0，表示第一个人。

2. k 表示每次报数的数目，比如题目中指定的是5。

3. (index + k - 1) 表示下一个被淘汰的人相对于当前报数人的偏移量。例如，如果 k 是5，那么下一个被淘汰的人相对于当前报数人就是偏移4。

4. people.size() 表示当前剩余人数，它决定了圆圈的大小。

5. % people.size() 用于确保计算的偏移量在圆圈内，因为超出圆圈范围的偏移量需要循环到圆圈内部来选择下一个被淘汰的人。

通过这个公式，每次淘汰一个人后，index 就更新为下一个被淘汰人的索引，然后重复这个过程，直到只剩下一个人。

这个计算公式的核心思想是模拟人数不断减少的情况，确保报数超过人数后能够回到圆圈的开头进行淘汰。这是约瑟夫环问题的关键之一。

c++代码通过循环列表来实现

这段代码是用C++编写的解决约瑟夫环问题的算法。它的核心思路是使用一个单向循环链表来表示人，并依次淘汰报数满足条件的人，最终找到幸存者。

以下是代码的核心思路的解释：

1. struct node 定义了一个节点，其中 d 存储了每个人的编号，next 存储了指向下一个节点的指针。

2. n 表示总人数，m 表示报数的数目。

3. 创建一个空的链表，使用 head 表示链表的头节点，p 用于创建新节点，r 用于追踪链表的最后一个节点。

4. 初始化链表，从1到n，依次创建节点，并将它们加入链表中。

5. 连接链表的尾部和头部，形成循环链表。

6. 使用两层循环来模拟报数和淘汰的过程。外层循环控制总共要进行 n 次淘汰，每次淘汰一个人。

   • 内层循环用于循环报数，从1到m-2，将 r 移动到报数满足条件的人之前。m-2是因为后面还要移动两个位置

   • 输出 r->next->d，即报数满足条件的人的编号。

   • 更新链表，将满足条件的人从链表中移除。

   • 更新 r，继续下一次的循环。

7. 重复以上步骤，直到所有人都被淘汰。最后，就会输出约瑟夫环问题的解，即每次淘汰的人的编号。