约瑟夫环算法_java

资料来源：网络整理时间：2023/3/8 18:40:47 共计：3590 浏览

约瑟夫环算法？

约瑟夫环指的是，n个人按编号顺序围成一个环，设置一个数字m，其中m<n（一般m取0-9之间的数）；并从环中的第一个人开始，按顺时针数数，每数了m个位置，排在m号的位置上的人出列，然后从出列的位置的下一个位置上的人开始数，一直到环中剩下最后一个人为止。

算法步骤：

（1）确定存储结构：由于是一个环，所以建立一个循环链表

（2）设置指针个数：设置一个头指针*front永远指向第一个结点（按数字顺序的话是指向环中最小的那个节点也可又从0开始数），再设置一个尾指针*prior用于指向报数的人的位置，每报一次数，尾指针指向下一个节点，数到m号时，则删除该节点，并将尾指针指向下一个节点，一直循环下去。

定义节点类型：

typedef struct Node

{

int data;

struct Node *next;

struct Node *front；

struct Node *prior；

}Node,*LinkList;

(3)向链表插入n个人（采用尾插法）：

LinkList Create_cirlce()

{

LinkList L,r,p;

L = (Node *) malloc ( sizEOF (Node)); //初始化链表

L->next = L;

r = L; //r始终指向最后一个结点

int n；

while ( scanf ( "%d" ,&n) != EOF)

{

p = (Node *) malloc ( sizeof (Node));

p->data = n;

p->next = r->next;

r->next = p;

r = p;

}

r->next = L;

return L;

}

（4）根据指针判断链表是否已出列到最后一个：判断*prior->next！=L

（5）利用循环遍历出出列的人：此时需利用两个循环，外循环代表遍历到最后一个所需要的循环次数，内循环代表遍历出列的人

void Josephus(int n,int m){

for(int i=0;i<n-1;i++){

for(int j=0;i<m-1;j++){

Next();//遍历出出列的人

cout<<"出列的人是："<<current;//显示出当前出列的人的位置

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。