Question

约瑟夫环问题的C++算法,求用链表和递归两种方法,尽量详细!

用链表和递归两种方法解决这个问题,本人刚学数据结构,感觉无从下手,答案最好加以注释!!!不要随便写个答案!本人要的是理解这个问题的算法!详细会加分!

Answer 1

#include <iostream.h>
typedef struct node {  //结点类型定义，每个结点表示一个孩子
    int data;   //用于存放结点（孩子）编号
    node *next;
    node(int _data = 0, node *_next = NULL)  //带缺省参数的结点构造函数

        : data(_data),next(_next)

    {}
}*PNode, Node, *JosephusCycle;

void InitJCycle(JosephusCycle &last, int n) {

//初始化一个含有n个孩子的约瑟夫环，用带尾指针last的单循环链表表示，建表时采用首插法。
    last = new Node(n);  //last指针始终指向表尾结点，先创建表尾结点
    last->next = last;  //先初始化只含一个结点的环。
    for(int i = n - 1; i > 0; i--)
        last->next = new Node(i, last->next); //将新结点插入到表头(即循环链表表尾的下一个)之前
}

int GetWinner(JosephusCycle &last, int k) { //第一种方法，返回剩下的最后这个孩子的编号
    if(last == NULL) return -1;  //如果为空环，则返回-1表示失败
    int sum; //报数器
    PNode prior = last, current = prior->next;//current表示当前报数结点，prior为当前结点的前驱
    while(prior != current) {//如果prior==current则意味着环中剩下一个孩子
        sum = 1; //报数开始
        while(sum < k) {  //进行报数，报数时，current指针与prior指针需同时移动
            prior = current;
            current = prior->next;
            sum++;
        }
        cout << current->data << "\t"; //将报到k的孩子的序号输出。接下来的两行是该孩子删除出环
        prior->next = current->next;
        delete current;
        current = prior->next; //重新定位当前孩子
    }  //end while，结束循环时，环中只剩最后一个孩子
    last = current;  //将环尾指针指向最后这个孩子
    return last->data;
}

int GetWinner(JosephusCycle &last, int n, int k) {

//方法二，递归，参数last是环尾指针，n表示环中孩子个数，k为报数的目标数
    if(n == 1) return last->data;  //如果环中只有一个孩子，则结束，并返回这个孩子的编号
    int sum = 1; //否则，则开始报数
    while(sum < k) {  //进行报数
        last = last->next;
        sum++;
    }  //结束while时，last->next即为报到k的孩子结点
    PNode p = last->next;//本行及后续3行是输出该孩子并删除该孩子
    cout << p->data << "\t";
    last->next = p->next;
    delete p;
    GetWinner(last, n - 1, k); //在剩下的n-1个孩子的环中继续找优胜者
}

void main( ) {
    JosephusCycle cycle;
    int m, k, winner;
    cin >> m >> k;

    cout << "方法一的出圈序列为：\n";
    InitJCycle(cycle, m);
    winner = GetWinner(cycle, k);
    cout << "\n优胜者：" << winner << endl;

    delete cycle;

    cout << "\n方法二的出圈序列为：\n";
    InitJCycle(cycle, m);
    winner = GetWinner(cycle, m, k);
    cout << "\n优胜者：" << winner << endl;
}