约瑟夫问题

✍ dations ◷ 2025-06-29 08:29:56 #组合数学,置换,计算机科学基础理论,数学问题

约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,处刑下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。

这个问题是以弗拉维奥·约瑟夫命名的,他是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个。

比较简单的做法是用循环单链表模拟整个过程,时间复杂度是O(n*m)。如果只是想求得最后剩下的人,则可以用数学推导的方式得出公式。且先看看模拟过程的解法。

# -*- coding: utf-8 -*- class Node(object):	def __init__(self, value):		self.value = value 		self.next = Nonedef create_linkList(n):	head = Node(1)	pre = head	for i in range(2, n+1):		newNode = Node(i)		pre.next= newNode		pre = newNode	pre.next = head	return headn = 5 #总的个数m = 2 #数的数目if m == 1: #如果是1的话,特殊处理,直接输出	print (n)  else:	head = create_linkList(n)	pre = None	cur = head	while cur.next != cur: #终止条件是节点的下一个节点指向本身		for i in range(m-1):			pre =  cur			cur = cur.next		print (cur.value)		pre.next = cur.next		cur.next = None		cur = pre.next	print (cur.value)

C++版本

#include <iostream>#include <cstdlib>#include <cstdio>using namespace std;typedef struct _LinkNode {	int value;	struct _LinkNode* next;} LinkNode, *LinkNodePtr;LinkNodePtr createCycle(int total) {	int index = 1;	LinkNodePtr head = NULL, curr = NULL, prev = NULL;	head = (LinkNodePtr) malloc(sizeof(LinkNode));	head->value = index;	prev = head;	while (--total > 0) {		curr = (LinkNodePtr) malloc(sizeof(LinkNode));		curr->value = ++index;		prev->next = curr;		prev = curr;	}	curr->next = head;	return head;}void run(int total, int tag) {	LinkNodePtr node = createCycle(total);	LinkNodePtr prev = NULL;	int start = 1;	int index = start;	while (node && node->next) {		if (index == tag) {			printf("%d\n", node->value);			if (tag == start) {				prev = node->next;				node->next = NULL;				node = prev;			} else {				prev->next = node->next;				node->next = NULL;				node = prev->next;			}			index = start;		} else {			prev = node;			node = node->next;			index++;		}	}}int main() {        if (argc < 3) return -1;	run(atoi(argv), atoi(argv));	return 0;}

数学推导解法

我们将明确解出 k = 2 {\displaystyle k=2} 是2的幂时,便重新从 f ( n ) = 1 {\displaystyle f(n)=1} 、、……、 n / k {\displaystyle \lfloor n/k\rfloor } 个人视为一个步骤,然后把号码改变,可得如下递推公式, 运行时间为 O ( k log n ) {\displaystyle O(k\log n)}

程序实现(C++)

相关

  • NLM美国国家医学图书馆(英语:The United States National Library of Medicine,NLM),由美国联邦政府经营管理,是世界上最大的医学图书馆,并设有研究中心。其前身为成立于1836年的美国
  • 旋转对称性在数学里,给予一个定义于内积空间的函数,假若对于任意旋转,函数的参数值可能会改变,但是函数的数值仍旧保持不变,则称此性质为旋转不变性(rotational invariance),或旋转对称性(rotat
  • 传说时代传说时代,又称传疑时代,是指依靠口耳相传所描述的远古历史时代,是中国地区古代传说和神话的一部分,在汉字记载出现之前,历史靠世世代代的口述而流传,这些内容到后来才被文字记录下
  • 五邑大学五邑大学(英文:Wuyi University)建于1985年,是中国广东省一所全日制本科综合性大学。学校位于珠江三角洲西部的广东省江门市,学校占地约1000亩,天沙河蜿蜒横贯其中,一河两区,毗邻港
  • 奥利弗·史密斯奥利弗·史密斯(英语:Oliver Smithies,1925年6月23日-2017年1月10日),英国出生的美国遗传学家,北卡罗来纳大学教堂山分校教授。因发明基因剔除技术与美国科学家马里奥·卡佩奇和英
  • 阿斯玛·马夫兹阿斯玛·马夫兹(英语:Asmaa Mahfouz,阿拉伯语:أسماء محفوظ‎,1985年2月1日-),埃及女性人权活动家,是2011年埃及革命中4月6日青年运动的发起人:她在运动爆发之前一周的1月18
  • 杰伊·詹金斯杰伊·詹金斯(英语:Jay Jenkins,1977年10月12日-)以其艺名Jeezy (原为Young Jeezy,译为杨·吉兹)出名,是美国嘻哈歌手、嘻哈组合USDA成员、Boyz N Da Hood(英语:Boyz N Da Hood)的前成
  • 双棘原始黄姑鱼双棘原始黄姑鱼(学名:),又名双棘原黄姑鱼、�仔鱼,为石首鱼科原黄姑鱼属下的一个种。本鱼分布在印度西太平洋区,包括波斯湾、斯里兰卡、印度、巴基斯坦、缅甸、泰国、马来西亚、新加
  • 21·萨维奇谢亚·本·亚伯拉罕-约瑟夫(英语:Shéyaa Bin Abraham-Joseph,1992年10月22日 - ),知名于其艺名21·萨维奇(21 Savage),生于英国伦敦,成长并出道于美国亚特兰大的饶舌歌手、词曲作家
  • 天喜星天喜星是紫微斗数中的桃花星,此星属阳水(壬水),主婚姻及喜庆,一喜破三煞,能化凶为吉,遇灾消灾,遇喜添喜,守于身命,主人容貌俊美,婚姻早发。若有天喜入命,为人老实耿直,易冲动而守信用,感