约瑟夫环
问题描述:
m 个人围成一个圈, 指定一个数字 n, 从第一个人开始报数, 每轮报到 n 的选手出局, 由下一个人接着从头开始报, 最后一个人是赢家. 其中 m>1,n>2.
链表法
用循环链表能完美契合本题
- #include
- 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
- 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
参考链接:
约瑟夫环 - 递归分析数学解法
来源: http://www.bubuko.com/infodetail-3438864.html