Josephus环问题两种求解算法（C语言实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Josephus环问题两种求解算法（C语言实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1849字，纯文字阅读大概需要3分钟。

内容图文

Josephus环问题两种求解算法（C语言实现）

一、算法一

构造双向循环链表。
首先创建结构体数组，每个结构体包括元素的编号、前驱元的索引(previous)及后继元的索引(next)。每次循环删除一个元素，使该元素的前驱元的next指向后继元的previous，后继元的previous指向前驱元的next，并将此元素标号置为-1。
从被删除元素的下一个元素开始继续循环，直到数组中只剩下一个元素（此元素的previous与next相等）
显然该算法时间复杂度为O(m*n)

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

struct node
{
	int number;      //序号
	int previous;    //前驱元标号
	int next;        //后继元标号
};

struct node* InitArray(int n)//初始化游标形式的双向循环链表
{
	struct node* people = (struct node*)malloc(sizeof(struct node) * n);
	for (int i = 0; i < n; i++)
	{
		people[i].number = i + 1;
		people[i].next = (i + 1) % n;
		people[i].previous = (i + n - 1) % n;
	}
	return people;
}

int Josephus(int n, int m)
{
	struct node* people = InitArray(n);
	int current = m;  
	while ((current != people[current].next))//只剩下一个元素时，结束循环
	{
		printf("%d->", people[current].number);
		people[current].number = -1;
		people[people[current].previous].next = people[current].next;//删去结点，修改指针指向
		people[people[current].next].previous = people[current].previous;
		for (int i = 0; i <= m; i++)
		{
			if (people[people[current].next].number > 0)
			{
				current = people[current].next;
			}
		}
	}
	return people[current].number;
}

int main()
{
	int x;   //初始总人数
	int y;   //相邻两个倒霉的人之间相隔的人数
	printf("初始总人数为：");
	scanf_s("%d", &x);
	printf("相邻两个倒霉的人之间间隔的人数为：");
	scanf_s("%d", &y);
	printf("\n最后幸存的人标号为：%d", Josephus(x, y));

	return 0;
}

二、算法二

首先删除标记为k - 1的人，把最初标记为k的人标 记为0，并从0开始，重新标记其余的标签;

则有关系式Josephus(n, k) = (Josephus(n - 1, k) + k)) % n;
另有Josephus(1, k) = 0;
据此即可在O(n)时间内完成迭代计算
(代码略）

• 点赞
• 收藏
• 分享
• • 文章举报

DarkSide_ 发布了2 篇原创文章 · 获赞 0 · 访问量 14 私信 关注

内容总结

以上是互联网集市为您收集整理的Josephus环问题两种求解算法（C语言实现）全部内容，希望文章能够帮你解决Josephus环问题两种求解算法（C语言实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---