设编号分别为:1,2,...,n的n个人围坐一圈。约定序号为k(1 <= k < = n)的人从1开始计数,数到m的那个人出列,他的下一位又从1开始计数,数到m的那个人又出列,依次类推,直到所有人出列为止。
设n=8,k=3,m=4时,如图所示:
出列为:6,2,7,4,3,5,1,8
算法思路:用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结点的单循环链表,然后从第k结点起从1计数,计到m时,对应结点从链表中删除;然后再从被删除结点的下一个结点起又从1开始计数....,直到所有结点都列出时算法结束。
代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct _node_
- {
- int data;
- struct _node_ *next;
-
- }ListNode;
- ListNode* get_node(int data)
- {
- ListNode *temp;
- temp = (ListNode *)malloc(sizeof(ListNode));
- temp->data = data;
- return temp;
- }
- int insert_data(ListNode **p,ListNode *q)
- {
- static ListNode *head;
-
- if(*p == NULL)
- {
- *p = q;
- head = q;
-
- }else{
-
- (*p)->next = q;
- q->next = head;
- //改变移动指针
- *p = q;
- }
- return 0;
- }
- ListNode *create_loop(int m)
- {
- int i = 0;
- ListNode *temp = NULL;
- ListNode *pmove = NULL;
-
- for(i = 1;i <= m;i ++)
- {
- temp = get_node(i);
- insert_data(&pmove,temp);
- }
- return pmove;
- }
- int delete_data(ListNode **p,ListNode *q)
- {
- (*p)->next = q->next;
- free(q);
- q = NULL;
- return 0;
- }
- int main()
- {
- ListNode *p,*q,*temp;
- int i = 0;
- int n,k,m;
- printf("input n k m:");
- scanf("%d%d%d",&n,&k,&m);
- while(getchar()!= '\n');
-
- //创建约瑟夫环
- p= create_loop(n);
- //第一个人的位置
- q = p->next;
- //找到地k个人
- for(i = 1;i < k;i ++)
- {
- p = p->next;
- q = q->next;
- }
- while(q != p)
- {
- for(i = 1;i < m;i ++)
- {
- p = p->next;
- q = q->next;
- }
-
- printf("%d ",q->data);
- delete_data(&p,q);
- q = p->next;
- }
- printf("%d\n",p->data);
-
- return 0;
- }
运行结果:
阅读(383) | 评论(0) | 转发(0) |