#include<cstdio> int main() { int cir[1000001]; //足够大的数组,存放每一个人的下一位是几号 int n; //人数 scanf("%d", &n); for(int i = 1;i < n;i++) cir[i] = i + 1; //初始时,i号人下一位为i+1号人 (除n外) cir[n] = 1; //第n号人下一位为1号,形成一圈 int j = 1, k = 1; //轮到第j个人报数字k /*模拟报数*/ while(j != cir[j]) //如果j的下一个是自己,则跳出循环 { k++; if(k != 3) //如果报数不为三 j = cir[j]; //轮到下一人 else //否则 { cir[j] = cir[cir[j]]; //修改下一人为下一人的下一人(类似于删除链表中节点) j = cir[j]; //第j人(下一人)报数字1 k = 1; } } printf("%d", j); return 0; }
典型的环形链表 处理约瑟夫环问题 public static int YueSeFuCircle(int n) { if (n == 1) return 1; Node head = new Node(1); Node cur = head; for (int i = 2; i <= n; i++) { cur.next = new Node(i); cur = cur.next; } cur.next = head; Node pre = null; cur = head; int count = 1; while(cur != pre) { if(count%3 != 0) { pre = cur; cur = cur.next; count++; } else { cur = cur.next; pre.next = cur; count = 1; } } return cur.val; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); Queue<Integer> queue = new LinkedList<>(); for (int i = 1; i <= n; i++) { queue.add(i); } while (queue.size() != 1) { for (int i = 0; i < 2; i++) { queue.add(queue.poll()); } queue.poll(); } System.out.println(queue.peek()); } }
/** * 楼上一位老兄的代码,我做了注释补充 */ public static int YueSeFuCircle(int n) { // 边界值 if (n == 1) return 1; Node head = new Node(1); Node cur = head; // 构造单链表 for (int i = 2; i <= n; i++) { cur.next = new Node(i); cur = cur.next; } // 将尾结点的next指向头节点,形成环链 cur.next = head; // 设置上一个结点 Node pre = null; cur = head; int count = 1; while(cur != pre) { // 报数未达3,将当前结点后移,上一个结点跟着往后移 if(count%3 != 0) { pre = cur; cur = cur.next; count++; } // 报数达到3,将当前结点的上一个结点的next指向当前结点的next // 相当于是删除链表中这个结点, // 再将count置为1,当前结点变成当前结点的下一结点 else { cur = cur.next; pre.next = cur; count = 1; } } return cur.val; } // 链表结点 static class Node{ public Node(int val){ this.val = val; } private int val; private Node next; }
const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, ouput: process.stdout }) let inArr = [] rl.on('line', line=>{ if(!line) return inArr.push(line.trim()) if(inArr.length === 1){ let n = +inArr[0] let res = lastRemaining(n,3) console.log(res+1) } }) var lastRemaining = function(n, m) { let res = 0 for(let i =2;i<=n;i++){ res = (res+m)%i } return res };
#include <iostream> #include <queue> using namespace std; int main() { int a,count = 1; cin>>a; queue<int> q; for(int i = 0; i<a;i++){ q.push(i + 1); } while (q.size() > 1) { if(count++ == 3){ count = 1; }else{ q.push(q.front()); } q.pop(); } cout<<q.front(); } // 64 位输出请用 printf("%lld")
//约瑟夫环(C语言) int GetPeople(int n){ if(n==1)return 1; int *people=(int*)malloc((n+1)*sizeof(int)); memset(people,0,(n+1)*sizeof(int)); int j=0;//计数器 int outCount=0;//出局人数 for(int i=1;outCount<n-1;i++){ if(i>n){//保证循环 i=1; } if(people[i]==0){//people还未出局 j++; if(j%3==0){ j=0;//计数再次从1开始 people[i]=1; outCount++; } } } for(int i=1;i<=n;i++){ if(people[i]==0)return i; } return 0; } int main(){ int n=0,x; scanf("%d",&n); x=GetPeople(n); printf("%d",x); }
import java.util.LinkedList; import java.util.Scanner; /** * @Author: Yr-zwx * @Date: 2021/10/16 * @Content: */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int nextInt = scanner.nextInt(); LinkedList<Integer> integers = new LinkedList<>(); int count=1; for (int i = 0; i < nextInt; i++) { integers.add(i+1); } while (true){ if (integers.size()==1){ break; } if (count%3==0){ integers.pollFirst(); count=1; } else { integers.addLast(integers.pollFirst()); count++; } } System.out.println(integers.peek()); } }--610 (懂哥至水哥)
//用Java数组实现约瑟夫环问题 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //数组解决约瑟夫环问题 int[] p = new int[n]; int[] flag = new int[n]; for (int i = 0; i < n; i++) { p[i] = i + 1; //初始化数组 flag[i] = 0; //初始默认都在圈里 } int c = 0; //当前喊的人的牌号 int k = 0; //当前喊的数 int targetNum = 3; //出圈口令,喊到3就出圈 int outNum = 0; //当前已出圈人数 while (outNum != n - 1){ //当当前已出圈人数 不等于 输入的人数时 c++; //1号位准备喊数 if (c > n){ //如果当前喊的人的位子大于所有人数 c = 1; //从头再来 } if(flag[c-1] == 0){ //如果这个人在圈里 k++; //让他喊数 if (k == targetNum){ //如果喊得数是目标值3,就出圈 flag[c-1] = 1; //标志已出圈,不再参与下一轮 outNum++; //出圈人数增加 k = 0; //只要一喊到3,就初始化下一轮的喊数 //System.out.print(c + " "); //打印出圈顺序 } } } //找到剩下的唯一flag=0的人并输出 for (int i = 0; i < flag.length; i++) { if (flag[i] == 0){ System.out.println(p[i]); } } } }
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; int num = 0; int person = n; for (int i = 0;i < n;i++){ a[i] = i + 1; } for (int i = 0;;i++){ if (i == n){ i = 0; } if (a[i] != 0){ num++; }else{ continue; } if(num == 3){ a[i] = 0; person--; num = 0; } if(person == 1){ break; } } for (int i = 0;i < n;i++){ if (a[i] != 0){ System.out.println(a[i]); } } } }
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int pos=0; for(int i=2;i<=n;i++) { pos=(pos+3)%i; } cout<<pos+1; return 0; }