数据结构题目28:约瑟夫问题

题目:约瑟夫问题:一直有n个人(不妨以编号1,2,3,...,n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依次规则重复下去,知道圆桌周围的人全部出列。
例如:当n=8,m=4,k=3时,出列的顺序依次为6,2,7,4,3,5,1,8。

解题思路:解决约瑟夫问题可以利用多种数据结构,但比较简单和自然的方法是利用一个具有n个链结点,且不带头结点的循环链表。将圆桌周围的每一个人对应着该链表中的一个链结点,某个人出列相当于从链表中删除一个链结点。下面的算法就是在该循环链表中不断的报数,不断的删除一个链结点,直到循环链表中还剩一个链结点时游戏结束。
整个算法可以分为以下3步:
1.建立一个具有n个链结点,且无头结点的循环链表
2.确定第1个报数点的位置
3.不断地从链表中删除一个链结点,直至链表中只剩有一个链结点

具体实现如下:

//定义链结点
class Node{
    constructor (data, link) {
        this.data = data,
        this.link = link
    }
}
function  JOSEPHUS(n, m, k) {
    let p, r, list = null
    let i

    //建立一个无头结点的循环链表
    for (i = 1; i <= n; i++) {
        p = new Node(i, null)
        if ( list==null ) {
            list = p
        } else {
            r.link = p
        }
        r = p
    }
    p.link = list
    //至此一个循环链表创建完了

    p = list
    for (i = 1; i < k; i++) {
        r = p
        p = p.link
    }
    //此时p指向第1个出发结点

    while ( p.link!=p ) {
        for (i = 1; i < m; i++) {
            r = p
            p = p.link
        }
        r.link = p.link
        console.log("出列的是:"+p.data)
        p = null
        p = r.link
    }
    console.log("最后出列的是:"+p.data)
}
JOSEPHUS(8, 4, 3)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
禁止转载,如需转载请通过简信或评论联系作者。