精华内容
下载资源
问答
  • 约瑟夫生死游戏

    2013-11-24 12:51:22
    c语言实现约瑟夫生死游戏,从一组数中依次剔除
  • 约瑟夫生死游戏 常见于队列的练习 属于经典算法
  • C语言约瑟夫生死游戏

    千次阅读 2019-01-11 19:41:59
    大二后开始学习数据结构,开始痴迷于各种算法,解决的第一个比较有趣的问题就是约瑟夫生死游戏。当时是用无头结点的循环链表写的,因为个人感觉这种方式比带头结点的循环链表和单链表更符合问题环境,也就是容易想。...

    大二后开始学习数据结构,开始痴迷于各种算法,解决的第一个比较有趣的问题就是约瑟夫生死游戏。当时是用无头结点的循环链表写的,因为个人感觉这种方式比带头结点的循环链表和单链表更符合问题环境,也就是容易想。

    【问题描述】
    约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第9人,便把他投入大海中,然后从他的下一个人数起,数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。

    【问题分析】
    该问题有多种问法,但本质一样,而且每次也不一定是9号被扔。所以,设计一个程序,可以设定初始人数和需要“扔下来”的人数。

    【解决方案】

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Lnode {
    	int date;
    	struct Lnode *next;
    }LNode;
    LNode  *create_LinkList(int a) {
    	LNode *head, *rear, *p;
    	head = rear = (LNode  *)malloc(sizeof(LNode));
    	head->next = head;
    	head->date = 1;
    	for (int i = 2; i <= a; i++) {
    		if (i == 32767)  break;
    		p = (LNode  *)malloc(sizeof(LNode));
    		p->date = i;
    		p->next = rear->next;
    		rear->next = p;
    		rear = p;
    	}
    	return head;
    }
    LNode im(int a, int b, int c) 
    {//a,原始人数;b,删除序号,c,幸存人数
    	LNode *p = create_LinkList(a);
    	for (int i = 1; i < a; i++) 
    	{
    		p = p->next;
    	}
    	for (int i = 1; i <= a - c; i++)
    	{//大循环,删除的个数
    		LNode *q = p->next;
    		if (b > 1)
    		{
    			for (int j = 1; j <= b - 1; j++)
    			{//小循环,让P指针移动几次
    				p = q;
    				q = q->next;
    			}
    			printf("%d  ", q->date);
    			p->next = q->next;
    			free(q);
    		}
    		else
    		{
    			printf("%d  ", q->date);
    			p->next = q->next;
    			free(q);
    		}
    	}
    	printf("\n幸存者序号依次为:\n");
    	for (int i = 1; i <= c; i++) {
    		printf("%d  ", p->date);
    		p = p->next;
    	}
    	return *p;
    	}
    int main(){
    	int a, b, c;
    	printf("请输入初始总人数和要被扔下去的序号:");
    	scanf_s("%d %d", &a, &b);
    	printf("请输入幸存人数:");
    	scanf_s("%d", &c);
    	*create_LinkList(a);
    	printf("初始的编号是:\n");
    	for (int i = 1; i <= a; i++) { printf("%d  ", i); }
    	printf("\n");
    	printf("被扔下去的人依次为:\n");
    	im(a, b, c);
    	}
    
    展开全文
  • 数据结构 线性表 C语言 约瑟夫 生死游戏..........
  • 数据结构实验四 约瑟夫生死游戏

    千次阅读 2020-04-12 09:38:00
    实验四 约瑟夫生死游戏 1、实验目的: 利用线性表解决实际问题。 2、实验环境与设备: 已安装Visual Studio 2010(或其以上版本)集成开发环境的计算机。 3、实验原理: (1)利用线性表的删除功能剔除被杀掉的人。 ...

    实验四 约瑟夫生死游戏

    1、实验目的:
    利用线性表解决实际问题。

    2、实验环境与设备:
    已安装Visual Studio 2010(或其以上版本)集成开发环境的计算机。

    3、实验原理:
    (1)利用线性表的删除功能剔除被杀掉的人。
    (2)利用单链表、不带头结点的循环链表或带头结点的循环链表均可实现。

    4、实验内容:
    约瑟夫生死游戏问题有如下几种表述;
    表述一:古代某法官要判决N个犯人的死刑,他有一条荒唐的法律,将犯人站成一个圆圈,从第S个人开始数起,每数到第D个犯人,就拉出来处决,然后再数D个,数到的再处决……直到剩下的最后一个可赦免。
    表述二:17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事: 15个教徒和15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法: 30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。
    表述三:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第9人,便把他投入大海中,然后从他的下一个人数起,数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
    表述四:据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了规则,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
    其数学模型归结如下:
    数学模型:假设n个人排成一个环形,依次顺序编号1,2,…,n。从第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下k个人为止。
    试利用线性表编程模拟该游戏。
    5、实验考核:
    (1)完成纸质版实验报告
    (2)提交电子版作业

    6、执行结果示例如下:

    图1 示例一
    在这里插入图片描述
    图2 实例二
    在这里插入图片描述
    图3 示例三
    在这里插入图片描述
    上代码

    #include<stdio.h>
    #include<malloc.h>
    #define OK 1
    #define FALSE -1
    #define TURE 1
    #define ERROR -1
    #define INFEASIBLE -1
    
    typedef int Elemtype;
    typedef struct LNode
    {
    	Elemtype data;
    	struct LNode *next;
    }LNode, *LinkList;
    
    LinkList p, r, last = NULL;
    // 构造一个不带头结点的循环链表,并赋值 1~n 
    void CreatList(int n)
    {
    	for (int i = 1; i <= n; i++)
    	{
    		p = (LinkList)malloc(sizeof(LNode)); // 申请一个新的链结点
    		p->data = i;  // 存放第 i 个结点的元素  
    		if (last == NULL)
    			last = p;
    		else
    			r->next = p;
    		r = p;
    	}
    	p->next = last;
    	p = last; // 循环链表建立完成  
    }
    // 将头指针 p 指向第 s 个人 ,从第几个人开始 
    void StartNum(int s)
    {
    	for (int i = 1; i < s; i++)
    	{
    		r = p;
    		p = p->next;
    	}// 此时 p 指向第 1 个出发结点
    }
    // 依次输出被删除的元素及最后剩余的元素。
    void DeleteList(int m)
    {
    	while (p->next != p)//不指向自己
    	{
    		for (int i = 1; i < m; i++)
    		{
    			r = p;
    			p = p->next;
    		}//p 指向第 m 个结点 ,r 指向第 m-1 个结点
    		r->next = p->next;// 删除第 m 个结点
    		printf("Number %d is out\n", p->data);// 依次输出删除结点的元素  
    		free(p);// 释放被删除结点的空间
    		p = r->next;//p 指向新的出发结点
    	}
    	printf("Number %d is save\n", p->data);// 输出最后一个结点的元素  
    }
    
    void DeleteNum(int m,int save,int n)
    {
    	while (p->next!=p)//不指向自己
    	{
    		for (int i = 1; i < m; i++)
    		{
    			r = p;
    			p = p->next;
    		}//p 指向第 m 个结点 ,r 指向第 m-1 个结点
    		r->next = p->next;// 删除第 m 个结点
    		printf("Number %d is out\n", p->data);// 依次输出删除结点的元素  
    		free(p);// 释放被删除结点的空间
    		p = r->next;//p 指向新的出发结点
    		n--;
    		if (n == save) break;
    	}
    
    	while (p->next != NULL) {
    		printf("Number %d is save\n", p->data);
    		p = p->next;
    		save--;
    		if (save == 0) break;
    	}
    }
    
    
    //大佬算法,一行解决!!
    int f(int n, int m)//n:人数   m:间隔
    {
    	return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
    }
    
    int main()
    {
    	int n, m, s,save = 1;//n总人数    m间隔   s开始的位置  先默认save=1
    	printf("请输入总人数 n:\n");
    	//总人数
    	scanf_s("%d", &n);
    	//间隔
    	printf("请输入间隔 m:\n");
    	scanf_s("%d", &m);
    	//开始的位置
    	printf("请输入开始的位置 s:\n");
    	scanf_s("%d", &s);
    	//要剩的人数
    	printf("请输入要保留的人数 s:\n");
    	scanf_s("%d", &save);
    	
    	CreatList(n);
    	StartNum(s);
    	
    	printf("****** Solve Josephus Problem ******\n");
    	DeleteNum(m,save,n);
    	printf("**************** END ***************\n");
    	
    
    	//还有个大佬算法,只保留一个人,递归调用,一行出结果
    	// printf("%d\n",f(n,m));
    
    	system("pause");
    	return 0;
    }
    

    结果
    (1)演示6剩1(间隔3)
    在这里插入图片描述
    (2)表述二和三:30剩15(间隔9)
    在这里插入图片描述
    (3)表述四:41剩2(间隔3)
    在这里插入图片描述

    展开全文
  • 利用线性表解决约瑟夫生死游戏

    千次阅读 2018-03-19 09:36:19
    利用线性表解决约瑟夫生死游戏 一、实验内容: n个人排成一个环形,依次顺序编号1,2,…,n。从第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下...

    利用线性表解决约瑟夫生死游戏
    一、实验内容:
    n个人排成一个环形,依次顺序编号1,2,…,n。从第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下k个旅客为止。
    二、实验分析:
    其数学模型归结如下:
    数学模型:假设n个人排成一个环形,依次顺序编号1,2,…,n。从第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下k个旅客为止。
    三、代码实现:
    1.源程序:

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct Node {
             int Num;
             struct Node *next;
    
    }Node, *PNode, *HeadNode;
    
    
     int ListInit(HeadNode *h)
     {
        if (!h)
        {
          printf("初始化链表错误!\n");
            return 0;
        }
             (*h)->next = (*h);//循环单链表
             return 1;
    
             }
    
    
     int ListInsert(Node *h, int pos, int x)/*尾插法*/
     {
            PNode p = h, q;
             int i = 1;
             if (pos == 1)
                 {
                 p->Num = x;
                 p->next = p;
                 return 1;
                 }
            while (i<pos - 1)
                 {
                 p = p->next;
                 i++;
                }
             q = (PNode)malloc(sizeof(Node));
            q->Num = x;
        q->next = p->next;
             p->next = q;
             return 1;
         }
    
     void ListTraverse(HeadNode h, int M)
     {
            int i = 0;
             PNode p = h;
             printf("参与的人的编号为:\n");
             while (i<M)
                 {
                    printf("%d\t", p->Num);
                     p = p->next;
                     i++;
                 }
        printf("\n");
        }
    
     //囚犯处死函数
     int ListDelete(HeadNode h, int M, int k)
     {    int i;
         PNode p = h, q;
         while (M>1)
         {
                 for (i = 1; i<k - 1; i++)
                    {
                        p = p->next;
                     }
    
                q = p->next;
            p->next = q->next;
            printf("被处决囚犯的序号为%d\n", q->Num);
                free(q);
    
                 p = p->next;
            M--;
            }
         printf("被赦免的囚犯为:%d", p->Num);
         return 1;
     }
    
     int main() {
        int i;//计数器
        int n;//囚犯的人数
        int m;//每轮要处决的序号
        printf("请输入囚犯总人数:");
        scanf_s("%d", &n);
        printf("请输入要处决的囚犯序号:");
         scanf_s("%d", &m);
         HeadNode h = ((HeadNode)malloc(sizeof(Node)));
         ListInit(&h);
         for (i = 1; i <= n; i++)
                {
                    ListInsert(h, i, i);
                 }
            ListTraverse(h, n);
                if (m > 1)
                 ListDelete(h, n, m);
                else
                {
                for (i = 1; i < n; i++)
                         printf("出局的人为:%d号\n", i);
                   printf("被处决的囚犯的编号为:%d", n);
                }
                 printf("\n");
                 printf("\n");
                 return 0;
         }

    2.执行结果:
    这里写图片描述

    展开全文
  • 约瑟夫生死游戏 每30个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长告诉乘客,只有将全船一半乘客投入海中,其余人才能幸免于难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第1...

    约瑟夫生死游戏

    • 每30个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长告诉乘客,只有将全船一半乘客投入海中,其余人才能幸免于难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第1个人数起,依次报数,数到第9人,便把他投入大海中,然后再从他的下一个人数起,数到第9人,再将他扔到大海中,如此循环地进行,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
    • 虽然顺序存储可以实现,但过程中涉及删除结点操作,循环链表效率更高,更方便。

    顺序实现

    #include<iostream>
    
    using namespace std;
    
    int main()
    {
        int person[30];
        int i, j;
        for (i = 0; i < 30; ++i) {
            person[i] = 0;
        }
        int count = 0;
        j = 0;
        while (count < 15) {
            i = 0;
            while (i < 9) {
                if (person[j] == 0) {
                    ++i;
                }
                j = (j + 1) % 30;
            }
            --j;
            if (j < 0)j = 30 + j;
            ++count;
            person[j] = 1;
            cout << j << " ";
            j = (j + 1) % 30;
        }
        system("pause");
        return 0;
    }
    

    链式实现

    #include<iostream>
    
    using namespace std;
    
    typedef struct Node {
        int data;
        //struct Node* prior;
        struct Node* next;
    }Node,*List;
    
    void initList(List& L);
    
    int main()
    {
        List L = new Node;
        initList(L);
        int i,j, count = 0;
        Node* p = L;
        while (count < 15) {
            for (j = 0; j < 7; ++j) {
                p = p->next;
            }
            cout << p->next->data << " ";
            //删除结点
            Node* q = p->next;
            p->next = q->next;
            //移到新起点
            p = p->next;
            ++count;
    
        }
        system("pause");
        return 0;
    }
    void initList(List& L) {
        L->data = 0;
        L->next = nullptr;
        int i;
        Node* p = L;
        for (i = 1; i < 30; ++i) {
            Node* q = new Node;
            q->next = nullptr;
            q->data = i;
            p->next = q;
            p = p->next;
        }
        p->next = L;
    }
    
    展开全文
  • 约瑟夫生死游戏嘛。 老师要抽签选择每个组对应的数据结构。结果宝宝抽到了单链表。。。。 一、项目简介 约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉...
  • c++ 不带头结点的约瑟夫生死游戏链表源程序 关于30个人在船上为了自救选择放弃15个人的程序
  • Python约瑟夫生死游戏

    2021-09-23 10:32:07
    有一艘般上有40个人,由于触礁出现了漏水,现在船上最多只能载20个人,需要20个人下船。于是这40个人排成一队,根据站位,每个人领取了一个编号,从1开始到40。然后从1开始到9进行循环报数,报数为9的人出列下船,...
  • 看完注释秒懂的约瑟夫生死游戏问题 C++实现 当然C也一样啦
  • 约瑟夫生死游戏(含源代码可以运行)本科毕业设计湖南商学院数据结构与算法课程设计题 目约瑟夫双向生死游戏学生姓名梁子嫣学 号140920043学 院计算机工程与信息学院专业班级计科1402指导教师蒋伟进职 称教授2016年6月...
  • C++约瑟夫生死游戏

    千次阅读 2018-03-19 22:47:10
    每30个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长告诉乘客,只有将全船一半乘客投入海中,其余人才能幸免于难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第1个人数起,依次报数...
  • 约瑟夫生死游戏(C++)数据结构实现》由会员分享,可在线阅读,更多相关《约瑟夫生死游戏(C++)数据结构实现(8页珍藏版)》请在人人文库网上搜索。1、题目二:约瑟夫生者死者游戏(链表存储)一:【内容与要求】约瑟夫...
  • 一、项目简介约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免于难。无奈,大家只得统一这种方法,并议定30...
  • python实例:约瑟夫生死游戏

    千次阅读 2019-01-23 00:15:17
    题目: 30 个人在一条船上,超载,需要 15 人下船。 于是人们排成一队,排队的位置即为他们的编号。 报数,从 1 开始,数到 9 的人下船。 ...如此循环,直到船上仅剩 15 人为止,问都有哪些编号的人下船了呢?...
  • 30个人同坐一条船,严重超载,船上必须剩15人才能保证安全,将30个人围成一圈,每数第9个就跳下去,问都哪个位置的人跳下去了??
  • 约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免于难。无奈,大家只得统一这种方法,并议定30个人围成一...
  • 代码如下: #include #include using namespace std; #include typedef int Status;...void KILL(Sqlist &L,int i,int j,int k)//i是总人数,j是要处决囚犯的序号,k是最后幸免的囚犯的人数 ...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 194
精华内容 77
关键字:

约瑟夫生死游戏