手机版
你好,游客 登录 注册
背景:
阅读新闻

约瑟夫问题 C语言链表实现

[日期:2018-04-22] 来源:Linux社区  作者:tao-zhu-forever [字体: ]

1.首先,我们先来了解一下什么是约瑟夫环问题:

讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队40余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后杀死所有人。
于是约瑟夫建议:每次由其他两人一起杀死一个人,而被杀的人的先后顺序是由抽签决定的,约瑟夫有预谋地抽到了最后一签,在杀了除了他和剩余那个人之外的最后一人,他劝服了另外一个没死的人投降了罗马。

通俗来说就是:

按照如下规则去杀人:
所有人围成一圈
顺时针报数,每次报到3的人将被杀掉
被杀掉的人将从房间内被移走
然后从被杀掉的下一个人重新报数,继续报3,再清除,直到剩余一人

那么程序实现为:

链表的定义: 定义为编号即可 所以data项为int

typedef struct NODE{
    struct NODE *next;
    int data;
}Node,*Linklist;

由于是循环,直到最后一个人, 所有可以使用特殊的链表: 循环链表。 当链表中只剩下一个元素后,便认为完事了。 即 L->next = L;

#include <stdio.h>
#include <stdlib.h>
#include "Linklist.h"

void Print_Linklist(Linklist L)
{
    Linklist head = L;
    printf("List: ");
    while(L->next != head)
    {
        printf("%d ",L->data);
        L = L->next;
    }
    printf("%d ",L->data);
    printf("\n");
}

int main()
{
    int i;
    Linklist L;
    Linklist head;
    Linklist Out;
    L = (Node*)malloc(sizeof(Node));
    head = L;
    L->data = 1;
    L->next = head;
    for(i=2;i<=41;i++)
    {
        L->next=(Node*)malloc(sizeof(Node));
        L->next->data = i;
        L->next->next = head;
        L = L->next;
    }
    Print_Linklist(head);
    L = head;
    while(L != L->next)
    {
        for(i=1;i<2;i++)
        {
            L = L->next;
        }
        Out = L->next;
        printf("%2d号 ----> 自杀!\n",Out->data);
        L ->next = Out->next;
        L = L->next;
        free(Out);
    }
    printf("幸存者是:%d",L->data);
    return 0;
}

本文永久更新链接地址https://www.linuxidc.com/Linux/2018-04/152002.htm

linux
相关资讯       C语言链表  约瑟夫问题 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款