10-约瑟夫环的几种解法

/* 题目内容：

 有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的

人退出圈子，问最后留下的是原来第几号的那位?

输入描述

正整数n

输出描述

直接输出结果

输入样例

10

输出样例

4
*/

1.个人的垃圾解法： 纯数组模拟游戏过程，初始为0，出局为-1，0开始标号， 注意点是取模
#include <iostream>
using namespace std;

int main(){
    int n, a[100] = {0}, count = 0;    //count记录出局人数
    cin >> n;
    int xu = 0;
    for(int i = 0; count < n - 1; i++){
        if(a[(i) % n] != -1){
            xu++;
            if(xu == 2){
                count++;
                while(a[(i + 1)%n] == -1){  //搜索下一位合要求的出局者
                    i++;
                    i = i % n;
                }
                i = (i + 1) % n;
                a[i] = -1;
//                cout << a[i] << " i" << i << endl;
                xu = 0;
            }
        }
        i = i % n;
//        cout << i << "i ";
    }
    for(int i = 0; i < n; i++){
        if(a[i] != -1)
            cout << i + 1 << " ";
//        cout << a[i] << " ";
    }
    return 0;
}

附上更新代码：动态数组模拟链表：

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

int main(){
	vector <int> v;
	int n; 
	cin >> n;
	for(int i = 1; i <= n; i++){
		v.push_back(i);
	}
	int i = 0, ct = 0;
	while(v.size() > 1){
		ct++;
		if(ct == 3){
			v.erase(v.begin() + i);
			ct = 0;
		}	
		else{
			i = (++i) % v.size();
		}
	}
	cout << v[0] << endl;
	return 0;
}

　　

2，高手的数学公式解法：能处理较大数据，耗时少，但不能模拟过程，不能显示各阶段结果

参考博客：http://blog.csdn.net/qq_25973267/article/details/50405616     http://blog.163.com/soonhuisky@126/blog/static/157591739201321341221179/

#include <iostream>
using namespace std;

int main(){
    int n, s = 0, m = 3;  // m为规定数到三出局， s 是剩余人重新从上一个出局后面开始计数后的编号
    cin >> n;             //最后一次一个人肯定是0，所以i = 1时s = 0;
    for(int i = 2; i <= n; i++)
        s = (s + m) % i;
    cout << s + 1;
    return 0;
}