Chinaunix首页 | 论坛 | 博客
  • 博客访问: 344847
  • 博文数量: 201
  • 博客积分: 305
  • 博客等级: 二等列兵
  • 技术积分: 500
  • 用 户 组: 普通用户
  • 注册时间: 2012-11-30 16:58
文章分类

全部博文(201)

文章存档

2015年(5)

2014年(12)

2013年(173)

2012年(11)

我的朋友

分类:

2013-01-09 17:25:21

原文地址:约瑟夫问题 作者:草根老师

转载请注明来源chengyaogen.blog.chinaunix.net
 
设编号分别为: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开始计数....,直到所有结点都列出时算法结束。
代码如下:
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. typedef struct _node_
  4. {
  5.     int data;
  6.     struct _node_ *next;
  7.     
  8. }ListNode;

  9. ListNode* get_node(int data)
  10. {
  11.     ListNode *temp;

  12.     temp = (ListNode *)malloc(sizeof(ListNode));
  13.     temp->data = data;

  14.     return temp;
  15. }

  16. int insert_data(ListNode **p,ListNode *q)
  17. {
  18.     static ListNode *head;
  19.     
  20.     if(*p == NULL)
  21.     {
  22.         *p = q;
  23.         head = q;
  24.         
  25.     }else{
  26.         
  27.         (*p)->next = q;
  28.         q->next = head;
  29.         //改变移动指针
  30.         *p = q;
  31.     }

  32.     return 0;
  33. }

  34. ListNode *create_loop(int m)
  35. {
  36.     int i = 0;
  37.     ListNode *temp = NULL;
  38.     ListNode *pmove = NULL;
  39.     
  40.     for(i = 1;i <= m;i ++)
  41.     {
  42.         temp = get_node(i);
  43.         insert_data(&pmove,temp);
  44.     }

  45.     return pmove;
  46. }

  47. int delete_data(ListNode **p,ListNode *q)
  48. {
  49.     (*p)->next = q->next;
  50.     free(q);
  51.     q = NULL;

  52.     return 0;
  53. }

  54. int main()
  55. {
  56.     ListNode *p,*q,*temp;
  57.     int i = 0;
  58.     int n,k,m;

  59.     printf("input n k m:");
  60.     scanf("%d%d%d",&n,&k,&m);
  61.     while(getchar()!= '\n');
  62.     
  63.     //创建约瑟夫环
  64.     p= create_loop(n);

  65.     //第一个人的位置
  66.     q = p->next;

  67.     //找到地k个人
  68.     for(i = 1;i < k;i ++)
  69.     {
  70.         p = p->next;
  71.         q = q->next;
  72.     }

  73.     while(q != p)
  74.     {    
  75.         for(i = 1;i < m;i ++)
  76.         {
  77.             p = p->next;
  78.             q = q->next;
  79.         }
  80.         
  81.         printf("%d ",q->data);
  82.         delete_data(&p,q);
  83.         q = p->next;
  84.     }

  85.     printf("%d\n",p->data);
  86.     
  87.     return 0;
  88. }
运行结果:
阅读(518) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~