约瑟夫环

问题描述：

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. 约瑟夫环-递归分析数学解法

约瑟夫环的三种解法（循环链表、数组、递归）

原文：https://www.cnblogs.com/ziyuemeng/p/12375536.html