josephus问题java

Josephus问题是一个经典的算法问题，描述如下：有n个人围成一圈，从第一个人开始报数，数到m的人出圈，然后从下一个人开始重新报数，数到m的人再次出圈，直到所有人都出圈为止。问最后剩下的人在原序列中的位置是多少？

下面是Java的解法：

public static int josephus(int n, int m) {
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = (ans + m) % i;
    }
    return ans + 1;
}

解释如下：

假设f(n,m)表示n个人中，每数到第m个人出圈最后剩下的人的编号，那么对于n个人来说，第一个出圈的人是(m-1)%n，剩下的人继续围成一圈，从第(m-1)%n+1个人开始重新报数。

因此，可以得到递推公式：

f(n,m) = (f(n-1,m) + m) % n

其中，f(1,m) = 0，因为只有一个人时，无需报数，直接出圈。

最后剩下的人的编号就是f(n,m)+1。

时间复杂度为O(n)。

相关问题

java反约瑟夫环问题

反约瑟夫环问题是一个经典的数学问题，也可以通过编程来解决。下面是一个Java的反约瑟夫环问题的示例代码：

import java.util.ArrayList;
import java.util.List;

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

        int index = 0;
        while (people.size() > 1) {
            index = (index + k - 1) % people.size();
            people.remove(index);
        }

        return people.get(0);
    }

    public static void main(String[] args) {
        int n = 7; // 总人数
        int k = 3; // 报数间隔
        int survivor = josephus(n, k);
        System.out.println("Survivor: " + survivor);
    }
}

这段代码中，我们使用了一个列表来表示参与游戏的人员，初始时，列表中包含了从0到n-1的编号。然后，我们使用一个循环来模拟游戏的过程，每次根据报数间隔k找到下一个要被移除的人员，并将其从列表中移除。最后，当列表中只剩下一个人时，该人即为最后的幸存者。

运行上述代码，将输出最后的幸存者的编号。

java约瑟夫问题循环链表

循环链表是解决约瑟夫问题的一种常见方法。下面是一个使用Java循环链表解决约瑟夫问题的示例：

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }
}

class CircularLinkedList {
    private Node head;
    private Node tail;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            tail.next = head;
        } else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head;
        }
    }

    public void remove(Node node) {
        if (head == null) {
            return;
        }
        if (head == node) {
            head = head.next;
            tail.next = head;
        } else {
            Node current = head;
            while (current.next != node) {
                current = current.next;
            }
            current.next = node.next;
            if (node == tail) {
                tail = current;
                tail.next = head;
            }
        }
    }

    public void josephus(int k) {
        Node current = head;
        while (current.next != current) {
            for (int i = 1; i < k; i++) {
                current = current.next;
            }
            System.out.print(current.data + " ");
            remove(current);
            current = current.next;
        }
        System.out.println(current.data);
    }
}

public class Main {
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        int n = 7; // 总人数
        int k = 3; // 报数为3的人出列
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        System.out.println("出列顺序：");
        list.josephus(k);
    }
}

这段代码中，我们首先定义了一个`Node`类来表示循环链表的节点，然后定义了`CircularLinkedList`类来实现循环链表的操作。在`josephus`方法中，我们使用循环链表模拟约瑟夫问题的解决过程，每次找到第k个节点并移除，直到只剩下一个节点为止。