约瑟夫环

问题描述：

m个人围成一个圈，指定一个数字n,从第一个人开始报数，每轮报到n的选手出局，由下一个人接着从头开始报，最后一个人是赢家。其中m>1,n>2。

链表法

用循环链表能完美契合本题

#include<iostream>
using namespace std;
struct Node{
    int data;
    Node* next;
    Node(int value){this->data = value;};
};
//创建一个约瑟夫环的类
class JosephCircle{
private:
    Node* tail;	//尾结点
    //Node* eliminate;	//淘汰结点
public:
    JosephCircle():tail(NULL){}
    ~JosephCircle(){delete tail;}
    void Add(int num);
    void Eliminate(int step);
    void Print();
};
void JosephCircle::Add(int num){
    if(tail == NULL){
        tail = new Node(num);
        tail->next = tail;
    }
    else{
        Node* new_node = new Node(num);
        new_node->next = tail->next;
        tail->next = new_node;
        tail = new_node;
    }
}
void JosephCircle::Eliminate(int step){
    Node* p = tail;
    while(p != NULL && p != p->next){
        for(int i = 0;i < step-1;i++){
            p = p->next;
        }
        Node* eliminate = p->next;
        p->next = eliminate->next;
        if(eliminate == tail){
            tail = p;
        }
        cout<<"deleting"<<eliminate->data<<endl;
        delete eliminate;
        Print();
    }
}
void JosephCircle::Print(){		//这打印还是有点说法的
    Node* cur = tail;
    while(cur != NULL){
        cur = cur->next;
        cout<<cur->data<<"  ";
        if(cur == tail)
            break;
    }
    cout<<endl;
}
int main(){
    JosephCircle jc;
    for(int i = 1;i <= 6;i++){
        jc.Add(i);
    }
    jc.Eliminate(3);
    jc.Print();
    return 0;
}

数组

数组倒是也能完成，代码量好像还要少一丢丢，但是要注意的边界条件太多了，debug的时间都够我写个链表解决的了T_T

#include <iostream>
using namespace std;
int JCArr(int num,int step){
	int arr[num];
	for (int i = 1; i <= num; ++i){
		arr[i-1] = i;
	}
	int n = num,i = 0,curOut = 1;
	while(num != 1){
		if(arr[i] == -1){
			i++;
		}
		else{
			i++;
			curOut++;
		}
		if(i == n){ 	//超过末尾从头开始
			i = 0;
		}
		if(curOut == step && arr[i] != -1){
			cout<<"deleting "<<arr[i]<<endl;
			arr[i] = -1;
			i++;
			if(i == n){		//这里也有可能发生越界，小心呀！
				i = 0;
			}
			curOut = 1;
			num--;	//别忘了总人数减一 
		}
	}
	int k = 0;
	for(;k < n;k++){
		if(arr[k] != -1)
			return arr[k];
	}
	
}
int main(int argc, char const *argv[])
{
	cout<<JCArr(6,3)<<endl;
	return 0;
}

递归

//TO DO

参考链接：

1. 约瑟夫环-递归分析数学解法