一行两个整数 n,m,n 表示链表的长度,m 表示每报数到 m 就自杀。
输出最后存活的人的编号(编号从 1 开始到 n)。
5 2
3
import java.util.Scanner; // 一行两个整数 n,m,n 表示链表的长度,m 表示每报数到 m 就***。 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); Person killed = null; // ***的人 Person aheadKilled = null; // ***之前的人,因为是单项环形链,要想形成链就得知道最后一个人,也就是***的人之前的那个人 Person newPerson; // 临时变量,新Person,放在循环之外 // 先组成一个链表 // 创建N个结点,形成单项环形链 for (int i = 1; i <= n; i ++) { newPerson = new Person(i); // 如果是第一个人,那么自己和自己形成环形链 if (killed == null) { killed = newPerson; // 默认***的就是第一个人 aheadKilled = newPerson; // ***之前的那一个人也是自己,因为就剩一个人了 killed.next = newPerson; // 自己的下一个人指向自己 } else { // 如果不是第一个人,则在末尾处添加新的人 aheadKilled.next = newPerson; // 原***之前的那一个人的后一个人指向新Person aheadKilled = newPerson; // 新的***之前的那一个人指向新的Person newPerson.next = killed; // 新Person的后一个人指向***的人 } } // 如果环内所剩之人一直大于1人,那么一直查数 // killed与aheadKilled指针相同时,证明环内只剩一人 while (killed != aheadKilled) { // 每报数到m就***,从1开始数,killed实际上移动了m-1次,例如每报数3就***,那么killed指针移动了3-1次,即1->2,2->3共2次 // 相对应的,***之前的一个人也移动m-1次 for (int i = 0; i < m - 1; i ++) { killed = killed.next; aheadKilled = aheadKilled.next; } // 移动完毕之后,此时killed指针指向的Person即为***之人,将此人从环中除去,即killed后移一位 killed = killed.next; // 重新形成环 aheadKilled.next = killed; } // 此时最后剩下的killed或aheadKilled指向的Person即为最后剩余之人 System.out.print(killed.number); } } class Person { public Person(int number) { this.number = number; } int number; // 编号 Person next; // 下一个人 }
#include <stdio.h> int get_num(int n, int m) { if (n == 1) { return 1; } return (get_num(n - 1, m) + m - 1) % n + 1; } int main(void) { int n, m; scanf("%d%d", &n, &m); printf("%d\n", get_num(n, m)); return 0; }
let [n,m]=readline().split(' ').map(item=>parseInt(item)) const listNode=function(val){ this.val=val this.next=null } let head=new listNode(-1) let p=head for(let i=0;i<n;i++){ const node=new listNode(i+1) p.next=node p=node } p.next=head.next head.next=null let q=p p=q.next // 计算每轮生存节点 // const getLive=function(n,m){ // if(n==1) return 1 // else return (getLive(n-1,m)+m-1)%n+1 // } // const compute=function(head,m){ // if(head==null||head.next==head||m<1) return head // let count=getLive(n,m) // while(count>1){ // head=head.next // count-- // } // console.log(head.val) // } const compute=function(){ if(head==null||head.next==head||m<1) return head let count=1 for(let i=2;i<=n;i++){ count=(count+m-1)%i+1 } // while(count>1){ // head=head.next // count-- // } console.log(count) } compute()
利用递推解决约瑟夫环问题
n, m = map(int, input().split()) live = 0 for i in range(2, n+1): live = (live+m)% i # 活下来的犹太人(同一个人a)倒数第i轮中所处的位置与倒数第i-1轮中所处的位置之间的关系 print(live+1)
n,m=map(int,input().split(" ")) r=0 for i in range(2,n+1): r=(r+m)%i print(r+1)约瑟夫问题有数学公式可以带入计算,正常循环的方式反而会导致超时
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static int josephusKillFast(int n, int m) { if (n == 1) { return 1; } int result = (josephusKillFast(n - 1, m) + m) % n; return result == 0 ? n : result; } public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] parameters = bufferedReader.readLine().split(" "); int n = Integer.parseInt(parameters[0]); int m = Integer.parseInt(parameters[1]); System.out.println( josephusKillFast(n, m)); } }