黑马程序员技术交流社区

标题: 约舍夫环的解答思路 [打印本页]

---

作者: ff774411    时间: 2015-12-12 20:09
标题: 约舍夫环的解答思路
    已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
    求解

---

作者: huaizhexiwang    时间: 2015-12-12 20:09
1.建立一个具有n个链结点，无头结点的循环链表
       2.确定第1个报数人的位置
       3.不断地从链表中删除链结点，直到链表为空

void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
    /* p为当前结点  r为辅助结点，指向p的前驱结点  list为头节点*/
    LinkList p,r,list;

    /*建立循环链表*/
    for(int i=0,i<n,i++)
    {
        p=(LinkList)malloc(sizeof(LNode));
        p->data=i;
        if(list==NULL)
            list=p;
        else
            r->link=p;
        r=p;
    }
    p>link=list; /*使链表循环起来*/
    p=list; /*使p指向头节点*/

    /*把当前指针移动到第一个报数的人*/
    for(i=0;i<k;i++)
    {
        r=p；
        p=p->link;
    }

    /*循环地删除队列结点*/
    while(p->link!=p)
    {
        for(i=0;i<m;i++)
        {
            r=p;
            p=p->link;
        }
        r->link=p->link;
        printf("被删除的元素：%4d ",p->data);
        free(p);
        p=r->link;
    }
    printf("\n最后被删除的元素是：％4d",P->data);
}

---

作者: huaizhexiwang    时间: 2015-12-12 20:13
解决问题的核心步骤：

---

作者: theones    时间: 2015-12-13 19:31
非常好！！！！！！！！！！！

---

作者: zcbcba123    时间: 2015-12-14 00:38
好厉害..

---

作者: w83144378    时间: 2015-12-16 15:28
我当初学的是吧异教徒投入海中  不过算法是一样的~~

---

作者: 344398083    时间: 2015-12-18 22:04
牛逼   这强人

---

作者: song0619    时间: 2015-12-22 19:21
回答的很好，我缺少相关的循环链表方面的知识，不知道谁能提供。

---

作者: huqianqian    时间: 2015-12-27 17:35
哈哈，越来越觉的编程好玩了，就是不会啊！

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2