C语言版约瑟夫问题算法实现

1、问题描述：

       有n个人围坐一圈,现从第s个人开始报数,数到m的人出列,接着从出列的下一个人开始重新报数,数到m的人又出列.如此下去,直到所有人都出列为止.试设计确定他们出列次序序列的程序

2、算法步骤：

        1、确定存储结构：n个人围成一圈，故使用循环单链表来存储序号

        2、算法实现：

该问题共n、m、s三个未知量，所以可以通过三个循环来实现，第一个循环用来确定最开始第一个报数的人的指针位置（单链表的头节点指针指向第s个人），第二个循环用来控制输出序号的次数（共n次），第三个循环用来数数（每一次循环使指针移动m次）

3、实现源代码：

# include <stdio.h>
# include <malloc.h>

typedef struct Node
{
	int number;
	struct Node * pNext;
}NODE, *PNODE;

PNODE creat_list(int n);

int main (void)
{
	int n,m,s;
	printf("约瑟夫环问题：\n");
	printf("设有n（编号为“0 1 2 3 .....n-1 n”）个人围坐一圈,现从第s个人开始报数，数到m的人出列,\n求最后的出列顺序。\n");
	printf("请设置n, s, m ：\n");
	printf("n = ");
	scanf("%d", &n);
	printf("s = ");
	scanf("%d", &s);
	printf("m = ");
	scanf("%d", &m);                    //问题引导提示代码段

	PNODE pHead = NULL;
	pHead = creat_list(n);
    pHead->number = 1;                   //创建单链表

	PNODE p = pHead;                       //定义头指针
	int i,j,k;                            //定义循环参数
	for(j = 1; j < s; j++)
		{
			p = p->pNext;
		}                                //第一个循环确定第一个报数的人在循环单链表中的位置  

	for(i = 1; i <= n; i++)              //外部循环代表遍历到最后一个所需要的循环次数
	{
		for(k = 1; k < m; )              //内部循环代表遍历出列的人
		{
			if(p -> pNext -> number != 0)
			{
				p = p -> pNext;
				k++;
			}
			else
			{
				p = p -> pNext;
			}
		}
		printf("%d  ",p -> number);
		p -> number = 0;
	    do
		{
		    p = p -> pNext;
		}while(p -> number == 0);
	}
	printf("\n");

	return 0;
}
PNODE creat_list(int n)                        //单链表的创建
{
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
    PNODE pTail = pHead;
	int i;
    for(i = 2; i <= n; i++)
	{
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		pNew->number = i;
		pTail->pNext = pNew;
		pNew->pNext = pHead;
		pTail = pNew;
	}
	return pHead;
}

到此这篇关于C语言版约瑟夫问题算法实现的文章就介绍到这了,更多相关C语言约瑟夫问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言用循环单链表实现约瑟夫环

    C语言用循环单链表实现约瑟夫环

    用循环单链表实现约瑟夫环(c语言),供大家参考,具体内容如下 源代码如下,采用Dev编译通过,成功运行,默认数到三出局. 主函数: main.c文件 #include <stdio.h> #include "head.h" #include "1.h" int main() { Linklist L; int n; printf("请输入约瑟夫环中的人数:"); scanf("%d",&n); Create

  • 详解约瑟夫环问题及其相关的C语言算法实现

    约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

  • 约瑟夫环问题(数组法)c语言实现

    问题说明这个问题是以弗拉维奥·约瑟夫斯命名的,它是1世纪的一名犹太历史学家.他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中.他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁.约瑟夫斯和另外一个人是最后两个留下的人.约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀.约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个机智的约瑟夫! 有N个编号为1~N的人围成一圈,现在每隔两个人(比如:1.4 之间隔了2.3)就将一个人淘汰出去,问最后剩下的是编号为几的人? 算法代

  • C语言约瑟夫环的实现

    C语言约瑟夫环的实现 一.典故: 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是商量了一个自杀方式: 41个人排成一个圆圈,由第1个人 开始报数,每数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要 他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死

  • C语言版约瑟夫问题算法实现

    1.问题描述:        有n个人围坐一圈,现从第s个人开始报数,数到m的人出列,接着从出列的下一个人开始重新报数,数到m的人又出列.如此下去,直到所有人都出列为止.试设计确定他们出列次序序列的程序 2.算法步骤:         1.确定存储结构:n个人围成一圈,故使用循环单链表来存储序号         2.算法实现: 该问题共n.m.s三个未知量,所以可以通过三个循环来实现,第一个循环用来确定最开始第一个报数的人的指针位置(单链表的头节点指针指向第s个人),第二个循环用来控制输出序号的

  • 哈希表实验C语言版实现

    复制代码 代码如下: /* 数据结构C语言版 哈希表 */#include <stdio.h>#include <malloc.h>#define NULLKEY 0 // 0为无记录标志 #define N 10  // 数据元素个数 typedef int KeyType;// 设关键字域为整型 typedef struct{ KeyType key; int ord;}ElemType; // 数据元素类型 // 开放定址哈希表的存储结构 int hashsize[]={11

  • 基于Go和PHP语言实现爬楼梯算法的思路详解

    爬楼梯(Climbing-Stairs) 题干: 假设你正在爬楼梯.需要 n 阶你才能到达楼顶.每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数.示例 1:  输入: 2  输出: 2  解释: 有两种方法可以爬到楼顶.  1. 1 阶 + 1 阶  2. 2 阶示例 2:  输入: 3  输出: 3  解释: 有三种方法可以爬到楼顶.  1. 1 阶 + 1 阶 + 1 阶  2. 1 阶 + 2 阶  3. 2 阶 + 1 阶来源:力扣 这题

  • C语言版学生信息管理系统

    C语言版学生信息管理系统

    本文实例为大家分享了C语言版学生信息管理系统的具体代码,供大家参考,具体内容如下 一.题目分析 1.功能概述 1)查询学生信息 2)添加学生信息 3)修改学生信息 4)删除学生信息 5)刷新学生信息 6)保存学生信息 7)输出当前学生信息 2.题目要求: 1)使用结构体建立学生信息体制 2)实现七大基本功能 3)采用文件存储学生信息 二.算法构造 1.难点解析----对文件的操作 1.1文件读取 FILE * fp; if ((fp = fopen(filename, "r")) ==

  • Go语言实现Snowflake雪花算法

    Go语言实现Snowflake雪花算法

    每次放长假的在家里的时候,总想找点简单的例子来看看实现原理,这次我们来看看 Go 语言雪花算法. 介绍 有时候在业务中,需要使用一些唯一的ID,来记录我们某个数据的标识.最常用的无非以下几种:UUID.数据库自增主键.Redis的Incr命令等方法来获取一个唯一的值.下面我们分别说一下它们的优劣,以便引出我们的分布式雪花算法. 雪花算法 雪花算法的原始版本是scala版,用于生成分布式ID(纯数字,时间顺序),订单编号等. 自增ID:对于数据敏感场景不宜使用,且不适合于分布式场景. GUID:采

  • C语言版扫雷小游戏

    C语言版扫雷小游戏

    本文实例为大家分享了C语言版扫雷小游戏的具体代码,供大家参考,具体内容如下 一.游戏功能 1.显示该点周围雷的个数 2.第一次下子,不炸死 3.坐标周围没雷,可以实现展开 二.效果展示 三.设计思路 这里由于博主目前能力有限,所以这里就用输入坐标的形式来进行排雷. 要想实现上方游戏功能其实也不难,总体思路就是:我们用几个算法模块来模拟游戏规则,实现上方的功能,然后用函数来调用各个模块使游戏跑起来. 接下来我们就来看看如何用C语言代码来实现游戏吧! 四.游戏实现步骤 1.游戏菜单 首先我们需要打印

  • go语言版的ip2long函数实例

    本文实例讲述了go语言版的ip2long函数.分享给大家供大家参考.具体分析如下: 这里介绍的go语言版的ip2long 函数不会对 IP 的合法性进行校验. 复制代码 代码如下: // 注意: 该函数不会对 IP 的合法性进行校验 func Ip2Long(ip string) (ips string) {     var ip_pieces = strings.Split(ip, ".")  ip_1, _ := strconv.ParseInt(ip_pieces[0], 10,

  • Java简单实现约瑟夫环算法示例

    Java简单实现约瑟夫环算法示例

    本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

  • Java版C语言版简单使用静态语言实现动态数组的方法

    动态语言相对于静态语言的一个优势,就是数组可以不需要预先确定大小,对于一些数组长度不确定的场景下是非常有用的.像PHP,只需要声明一下数组 $arr = array() 然后就可以直接 $arr[] = 1,$arr[] = 2,$arr[] = 3...这样一直加元素了,删除一个元素就直接使用unset($arr[1]),元素的空间就被释放了,而C和JAVA原生的数组就没有这么方便,声明的时候就必须先预先确定长度,由编译器分配相应的内存空间.不过通过一些巧妙的做法,也是可以实现一样的功能的,这

  • PHP基于递归实现的约瑟夫环算法示例

    本文实例讲述了PHP基于递归实现的约瑟夫环算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php $nu

随机推荐