温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2021-12-31 14:12:00 来源:亿速云 阅读:182 作者:小新 栏目:开发技术

这篇文章主要为大家展示了“如何实现C语言版约瑟夫问题算法”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“如何实现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语言版约瑟夫问题算法”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI