如何用C语言编写约瑟夫环算法？

本文共计533个文字，预计阅读时间需要3分钟。

C语言实现约瑟夫环问题：一、经典案例：据传说著名历史学家Josephus有过以下经历：在罗马人占领耶路撒冷后，城中的犹太人被置于一个困境，39个犹太人被围困在一座庙里，他们决定通过抽签的方式选出一个人牺牲，其余人得以逃生。39个犹太人围成一圈，从第一个人开始报数，每数到第3个人时，该人就必须离开圈子。如此循环，直到最后只剩下一个人，这个人就可以逃生。

C语言约瑟夫环的实现

一、典故:

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是商量了一个自杀方式：

41个人排成一个圆圈，由第1个人 开始报数，每数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要 他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

二、用循环链表实现

1.约瑟夫环实现

sListNode* JosephCycle(sListNode* pHead, DataType x) { if(pHead == NULL) return NULL; sListNode* cur = pHead; while(1) { DataType m = x; if(cur->next == cur) { return cur; } while(--m) { cur = cur->next; } //delete替换法 cur->data = cur->next->data; sListNode* del = cur->next; cur->next = cur->next->next; free(del); del=NULL; }

2.测试

void TestJosephCycle() { sListNode* list = NULL; Push_Back(list, 1); Push_Back(list, 2); Push_Back(list, 3); Push_Back(list, 4); Push_Back(list, 5); Push_Back(list, 6); Push_Back(list, 7); Push_Back(list, 8); Push_Back(list, 9); PrintList(list); //建环 sListNode* cur = list; while(cur->next != NULL) { cur = cur->next; } cur->next = list; sListNode* ret = JosephCycle(list, 3); cout<<"Joseph:"<<ret->data<<endl; //解环 free(ret); //明确知道只有一个节点，直接释放 ret = NULL; }

以上就是约瑟夫环的简单实现，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！