如何用C語言代碼實現約瑟夫環

本篇內容介紹了“如何用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; 
}

“如何用C語言代碼實現約瑟夫環”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！