最新消息:点击查看大S的省钱秘笈

约瑟夫问题(猴子选大王)循环链表C语言实现

编程相关 Slyar 12198浏览 10评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

昨天数据结构课讲循环链表和双向链表,双向链表没什么意思,不写了;循环链表有个典型应用就是解约瑟夫问题(Josephus),这里用的典型题目是”猴子选大王”。

题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1,2 ……… n 编号并按照顺序围成一圈,从第 k 个猴子起,由1开始报数,报到m时,该猴子就跳出圈外,下一只猴子再次由1开始报数,如此循环,直到圈内剩下一只猴子时,这只猴子就是大王。

输入数据:猴子总数n,起始报数的猴子编号k,出局数字m

输出数据:猴子的出队序列和猴子大王的编号

代码修改了一天才完成,第一次是用多个函数写的,但是发觉C语言没有引用参数这个特性,使得形参指针不能被直接修改,必须靠返回值来修改才行,这样太麻烦了…于是第二次写的时候就没有使用函数,直接在main()里完成了循环链表的操作,感觉应该没什么问题,哪位大牛看出问题跟我说下,thx…

/*
约瑟夫问题(猴子选大王)
循环链表C语言实现
Slyar 2009.3.31
//www.slyar.com
*/

#include 
#include 

/* 定义链表节点类型 */
typedef struct node
{
    int data;
    struct node *next;
}linklist;

int main()
{
    int i, n, k, m, total;
    linklist *head, *p, *s, *q;
    /* 读入问题条件 */
    printf("请输入猴子的个数:");
    scanf("%d", &n);
    printf("请输入要从第几个猴子开始报数:");
    scanf("%d", &k);
    printf("请输入出局数字:");
    scanf("%d", &m);
    /* 创建循环链表,头节点也存信息 */
    head = (linklist*) malloc(sizeof(linklist));
    p = head;
    p->data = 1;
    p->next = p;
    /* 初始化循环链表 */
    for (i = 2; i <= n; i++)
    {
        s = (linklist*) malloc(sizeof(linklist));
        s->data = i;
        s->next = p->next;
        p->next = s;
        p = p->next;
    }
    /* 找到第 k 个节点 */
    p = head;
    for (i = 1; i < k; i++)
    {
        p = p->next;
    }
    /* 保存节点总数 */
    total = n;
    printf("\n出局序列为:");
    q = head;
    /* 只剩一个节点时停止循环 */
    while (total != 1)
    {
        /* 报数过程,p指向要删除的节点 */
        for (i = 1; i < m; i++)
        {
            p = p->next;
        }
        /* 打印要删除的节点序号 */
        printf("[%d] ", p->data);
        /* q 指向 p 节点的前驱 */
        while (q->next != p)
        {
            q = q->next;
        }
        /* 删除 p 节点 */
        q->next = p->next;
        /* 保存被删除节点指针 */
        s = p;
        /* p 指向被删除节点的后继 */
        p = p->next;
        /* 释放被删除的节点 */
        free(s);
        /* 节点个数减一 */
        total--;
    }
    /* 打印最后剩下的节点序号 */
    printf("\n\n猴子大王为第 [%d] 号\n\n", p->data);
    free(p);
    //system("pause");
    return 0;
}

转载请注明:Slyar Home » 约瑟夫问题(猴子选大王)循环链表C语言实现

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (10)

  1. /* p 指向被删除节点的后继 */ 应改为p = q->next;
    118年前 (2013-02-26)回复
  2. 见过这个公式, for(int i=2;i<n;i++) s=(s+m)%i; s++; 貌似求出来的猴王号,始终比真正的猴王小一..不懂中间数学方法的奥妙... 猜测大概是逆反思维...
    wangjieest9年前 (2012-02-21)回复
  3. @Slyar 大概是那么个东西,给你个连接你看看把 https://acm.whu.edu.cn/blog/read.php?26
    Felix02112年前 (2009-04-03)回复
  4. @Felix021, 用数组描述树么?是不是就是2n和2n+1那个...如果是的话我就会,不是的话...有标程么?
    Slyar12年前 (2009-04-03)回复
  5. @Slyar 唔,我做这题的时候不是用公式,是用数状数组做的,这个数据结构很有意思的,很值得一学~
    Felix02112年前 (2009-04-03)回复
  6. @Felix021, 哎,这有数学解法的,我原来写过,用约瑟夫只是写一下循环链表而已...
    Slyar12年前 (2009-04-01)回复
  7. @Jutoy, 不是,这个是上课无聊的时候折腾的东西...
    Slyar12年前 (2009-04-01)回复
  8. 这个就是这两天你一直在折腾的那东西么…………
    Jutoy12年前 (2009-04-01)回复
  9. https://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1071 试试这题:)
    Felix02112年前 (2009-04-01)回复