约瑟夫斯问题

✍ dations ◷ 2025-07-11 17:28:03 #约瑟夫斯问题

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

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

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

这个问题是以弗拉维奥·约瑟夫命名的,他是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("%dn", 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/krfloor } 个人视为一个步骤,然后把号码改变,可得如下递推公式, 运行时间为 O ( k log n ) {displaystyle O(klog n)}

程序实现(C++)

相关

  • 仑目雷姆(全称为人体伦琴当量,英语:roentgen equivalent man,符号为rem)为辐射剂量当量的单位,相当于一伦琴的X光射线或伽码射线。1956年国际放射防护委员会把放射性工作人员的防护标
  • 氯丹氯丹(Chlordane)又称可氯丹,是有机氯杀虫剂的一种,为深琥珀色黏性液体,具有类似松柏的气味。氯丹通常以混合物的形态存在,其主成分氯丹占60%,另外含有结构类似的双环五碳双烯化合
  • 可持续性可持续性(英语:sustainability)也称永续性,是人们在满足人类需求与未来发展时,在资源开发、投资方向、技术发展和制度变革中保持环境平衡与和谐的过程。可持续性可以是一种想法、
  • 历史性八文件历史性八文件(英语:Historic Eight Documents)是印度毛派革命家查鲁·马宗达在1966年前后所撰写的八篇文章,其中概述了印度纳萨尔派激进共产主义运动依据的思想原则。 文章提出,
  • 陈柏言陈柏言(1991年-),台湾作家,国立凤山高中、国立政治大学中国文学系学士、国立台湾大学中国文学研究所硕士、国立台湾大学中国文学研究所博士班(在学中)。曾获多项文学奖项,如联合报文
  • SiMSiM(Silence iz Mine),是2004年形成的神奈川县日本金属乐队,所属唱片公司为Universal Music Japan,乐队目前由MAH(主唱),SHOW-HATE(吉他),SIN(贝斯)和GODRi(鼓手)组成。他们的音乐风格混合
  • 埃利奥特冰原岛峰坐标:85°16′S 89°43′W / 85.267°S 89.717°W / -85.267; -89.717埃利奥特冰原岛峰(英语:Elliott Nunatak),是南极洲的冰原岛峰,位于埃尔斯沃思地,属于蒂尔山脉的一部分,海拔高
  • Agnoshydrus见内文是鞘翅目肉食亚目之下的一个属,是龙虱科龙虱亚科之下球龙虱族(西班牙语:Hyphydrini)的成员。本属目前只有一个物种见于台湾,未有中文名称。本属目前只有八个已描述的物种,分别如下:
  • 门原香门原香(日语:門原 かおる1970年5月25日-),日本足球运动员,日本国家女子足球队成员。在1993年12月4日,她代表日本国家女子足球队出赛,在对战中华台北的比赛中首次​​亮相。从1993年到1996年,他共为国家足球队出场12次,打进1球。她也曾代表日本参加1995年国际足联女子世界杯,1996年夏季奥林匹克运动会足球比赛。
  • 艾尔·塞尔维艾尔弗雷德·尼古拉斯·塞尔维(英语:Alfred Nicholas Cervi,1917年2月12日-2009年11月9日),美国NBA联盟前职业篮球运动员。3 乔治·金|4 多尔夫·谢伊斯|5 保罗·西摩(英语:Paul Seymour (basketball))|6 康尼·西蒙斯(英语:Connie Simmons)|7 比利·加博尔|8 沃利·奥斯特霍恩(英语:Wally Osterkorn)|10 强尼·科尔(英语:Johnny Kerr)|11 厄尔·洛依德|12 迪克·法利|14 詹姆斯·塔克