未分类

递归法实现约瑟夫环

【问题描述】 ​ 约瑟夫问题的一种描述为:编号为1,2,…….n的n个人按顺时针方向作一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始顺时针方向自1开始顺时针报数,报到m时停止。报出m的人出列,将他的密码作为新的m的值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,自到所有人全部出列为止。


【基本要求】
​利用单向循环链表储存模拟此过程,按照出列的顺序印出各人的编号。

【测试数据】
m的初始值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m的值为6(正确的出值顺序应为6,1,4,7,2,3,5)
【问题分析】
​ 约瑟夫环就是一个首位相接的链表,实现起来非常简单,完全可以main函数里面用个循环来实现,但是,博主觉得此问题可以通过递归的方式来实现,(主要是为了装B)。代码如下。

struct node{
    int n; //n为每个人的密码
    int i; //i为每个人的编号
    struct node *next;
    node(int x,int y){n = x;i = y;} //使用结构体构造器
};

struct node* createList(int *m,node *n,int x){ //x是编号,m是密码数组
    if(*(m+1) != NULL){  //判断密码数组下一个是否还有值,这儿的NULL为0,因为密码不能为0要不然说不过去。也可以直接把NULL改为0
        n->next = new node(*m,x);
        node *tmp = createList(m+1,n->next,x+1);//这儿最终返回的值是else语句返回的
        return tmp;
    }
    else{
        n->next = new node(*m,x);
        return n->next; //到结尾后返回尾指针。
    }
}
​ 根据以上的代码,我们可以清楚地看到,当到我们输入的最后一个密码数组后,返回最后一个节点的下一个(为空)。在main函数里面做这样的处理。

    int *num = (int *)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++){
        cin>>*(num+i);//num为密码数组
    }
    node *head = new node(*num,1);
    node *tmp = createList(num+1,head,2);
    tmp->next = head;
​ 重新设定一个临时指针*tmp,通过这个临时指针,如何实现的就一目了然了。 ​ 接下来,我们来考虑如何踢人。代码如下。

void kill(node *list,int m,int x){//x为计数;m为要踢出去的那个人的密码,
    if((x+1) == m && list->next != list){
        cout<<list->next->i<<" ";
        m = list->next->n;
        list->next = list->next->next;
        kill(list,m,0);
    }
    else if(list->next == list && (x+1) == m){
        cout<<list->i<<" ";
        exit(1);
    }
    else{
        kill(list->next,m,x+1);
    }
}
​ 这儿有点小细节需要注意下,根据题目,我们要求的删除某个节点,并从下一个开始计数,但是,由于是单向循环链表,删除某个节点后没办法指向上一个节点完成连接,所以需要在需要删除的前一个节点完成判断,就是代码中的(x+1) == m,另外一个需要注意的地方就是,因为是判断下一个节点是否满足条件,所以,当完成删除下一个节点后,继续循环的条件应该是从现在这个节点开始往后计数,开始的编号为0。 ​ 下面是完整的代码

#include <iostream>
#include <stdlib.h>

using namespace std;

struct node{
    int n;
    int i;
    struct node *next;
    node(int x,int y){n = x;i = y;}
};

struct node* createList(int *m,node *n,int x){
    if(*(m+1) != NULL){
        n->next = new node(*m,x);
        node *tmp = createList(m+1,n->next,x+1);
        return tmp;
    }
    else{
        n->next = new node(*m,x);
        return n->next;
    }
}

void kill(node *list,int m,int x){       //x为计数;m为要踢出去的那个人的密码,
    if((x+1) == m && list->next != list){
        cout<<list->next->i<<" ";
        m = list->next->n;
        list->next = list->next->next;
        kill(list,m,0);
    }
    else if(list->next == list && (x+1) == m){
        cout<<list->i<<" ";
        exit(1);
    }
    else{
        kill(list->next,m,x+1);
    }
}

int main(){
    int m,n;
    cout<<"请输入m的值:";
    cin>>m;
    cout<<"请输入n的值:";
    cin>>n;
    cout<<"请依次输入"<<n<<"个人的密码:"<<endl;
    int *num = (int *)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++){
        cin>>*(num+i);
    }
    node *head = new node(*num,1);
    node *tmp = createList(num+1,head,2);
    tmp->next = head;
    kill(head,m,1);
    return 0;
}
​ ps:由于博主懒,就没有释放内存了。

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注