首页 > 试题广场 >

环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题

热度指数：3157 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。

输入描述:

一行两个整数 n 和 m， n 表示环形链表的长度， m 表示每次报数到 m 就自杀。

输出描述:

输出最后存活下来的人编号(编号从1开始到n)

示例1

输入

5 2

输出

备注:

算法知识视频讲解

Java

瞌睡虫BOBO

import java.util.*;
class node{
        int val;
        node next;
        public node(){};
        public node(int val) {
            this.val = val;
        }
}

public class Code61_yuesefuProblem {
    public static void main(String[] args) {
        node ans = new node();
        node index = ans;
        Scanner in = new Scanner(System.in);
        node mynode = new node();
        int n = in.nextInt();
         int m=in.nextInt();
        for (int i = 1; i <= n; i++) {
            node temp = new node(i);
            index.next = temp;
            index = index.next;
        }
        index.next = ans;
        int ch=n;
        int count=1;
        node p=ans;
        node q=ans.next;
        while(ch!=1) {
            if (count == m &&q.val!=0) {
                //System.out.println("所删除的节点"+q.val);
                q = q.next;
                p.next = q;
                count = 1;
                ch--;
            } else if (count != m &&q.val!=0) {
                p = p.next;
                q = q.next;
                count++;
            }
            else{
                p=p.next;
                q=q.next;
            }
        }
        node test=ans.next;
        while(true) {
            if(test.val!=0){
                System.out.println(test.val);
                break;
            }
            test=test.next;
        }
            }
        }


大概思路
1.就是循环赋值然后附完值后让指针指向头形成单循环链表
2.然后删除用的基本操作遇到对应的删除节点时前指针先走一步然后后指针指向他删除该指针并且计数器count置为1,如果不是的话就俩指针各走一步然后count++
3.对了我加了一个q.val!=0是因为我创建的链表是带头节点的方便操作但是头节点不参与循环所以到他的时候基数器不参与任何变化

编辑于 2023-03-10 15:20:21 回复(0)

Java

pein531

这个题如果不是非常经典并且作为教学问题的话，是真心难想。我们考察一下相邻两次报数的差异如下：

长度为i：1 2 3 ...... m-1 m m+1 m+2 ...... i-1 i

×（m被移除掉后）

长度i-1： ..... i-1 1 2 i-m-1 i-m

我们看看对应关系

新 —— 老

i-m+1 —— 1

i-m+2 —— 2

......

1 —— m+1

2 —— m+2

......

i-m-1 —— i-1

i-m —— i

画出函数图像发现就是函数y=x%i经过平移后的图像

根据上加下减左加右减的原理，可以得到本轮报数是x的情况下上一轮的报数y=(x+m-1)%i+1。而游戏进行到最后时，幸存者的报数是1，于是我们可以通过这个公式倒推回有n个人时的报数。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for(int i = 2; i <= n; i++){
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        int live = 1;     // 长度为1时，剩下节点的编号
        // 倒推得到长度为n时它的编号
        for(int i = 2; i <= n; i++) live = (live + m - 1) % i + 1;
        cur = head;
        for(int i = 1; i < live; i++) cur = cur.next;
        System.out.println(cur.val);
    }
}

直接用链表模拟的话每报数m次就删除一个节点，一共要删除n-1个节点，因此时间复杂度为O(mn)；而用公式倒推的话需要调用n-1次时间复杂度为O(1)的公式，整体时间复杂度为O(n)。

编辑于 2021-12-02 16:52:19 回复(0)

Java

潇元紫

## n总人数 m报道数 k第几次剔除的

新旧数组变化连接

import java.util.Scanner;

public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    System.out.println(getResult(n,m,n)+1);
}
public static int getResult(int n,int m,int k) {
    if(n==1)return (n+m-1)%n;
    else return (getResult(n-1,m,k-1)+m)%n;
}
}

发表于 2019-10-16 19:20:24 回复(0)