SDNU 1263 C语言课后习题10.5约瑟夫环如何实现？

本文共计325个文字，预计阅读时间需要2分钟。

Description: 有n个人围成一圈，按顺序排号。从第1个人开始报数（报数从1到3），凡报到3的的人退出圈子，然后下一个人继续从1开始报数。问最后留下的是原本的第几号位的人。

Input: 初始人数n

Output: 最后一个人的初始编号

Sample:Input: 5Output: 3

Description

有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。

Input

初始人数n

Output

最后一人的初始编号

Sample Input

3

Sample Output

2

Source

Unknown

/// /// _ooOoo_ /// o8888888o /// 88" . "88 /// (| -_- |) /// O\ = /O /// ____/`---‘\____ /// .‘ \\| |// `. /// / \\||| : |||// /// / _||||| -:- |||||- /// | | \\\ - /// | | /// | \_| ‘‘\---/‘‘ | | /// \ .-\__ `-` ___/-. / /// ___`. .‘ /--.--\ `. . __ /// ."" ‘< `.___\_<|>_/___.‘ >‘"". /// | | : `- \`.;`\ _ /`;.`/ - ` : | | /// \ \ `-. \_ __\ /__ _/ .-` / / /// ======`-.____`-.___\_____/___.-`____.-‘====== /// `=---=‘ /// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ /// Buddha Bless, No Bug ! /// #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <vector> using namespace std; #define MAXN 100010 #define ll long long int n, num = 0, sum = 0, id; bool sign[1000000+8]; int main() { num = 0, sum = 0; scanf("%d", &n); for(int i = 0; i < n; i++) sign[i] = 1; id = 0; while(sum < (n - 1)) { if(sign[id])num++; if(num == 3) { sign[id] = 0; num = 0; sum++; } id++; if(id == n)id = 0; } for(int i = id; i < n; i++) if(!sign[id]) id++; else break; printf("%d\n", id + 1); return 0; }