約瑟夫環(huán)問(wèn)題可以簡(jiǎn)單的使用數(shù)組的方式實(shí)現(xiàn)，但是現(xiàn)在我使用循環(huán)鏈表的方法來(lái)實(shí)現(xiàn)，因?yàn)樯衔缈吹揭坏烂嬖囶}規(guī)定使用循環(huán)鏈表解決約瑟夫環(huán)問(wèn)題。

　　什么是約瑟夫環(huán)？

　　“約瑟夫環(huán)是一個(gè)數(shù)學(xué)的應(yīng)用問(wèn)題：已知n個(gè)人（以編號(hào)1，2，3...n分別表示）圍坐在一張圓桌周?chē)木幪?hào)為k的人開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到圓桌周?chē)娜巳砍隽小！?#xff08;百度百科中的解決辦法列出了很多，可以看到循環(huán)鏈表并不是最簡(jiǎn)單的方法）

　　這道面試題考察了循環(huán)鏈表的“創(chuàng)建”，“遍歷”和“刪除”。

創(chuàng)建的循環(huán)鏈表的結(jié)構(gòu)圖：

解決約瑟夫環(huán)問(wèn)題的過(guò)程

C++實(shí)現(xiàn)代碼如下：

循環(huán)鏈表解決約瑟夫問(wèn)題 1 /**循環(huán)鏈表解決約瑟夫環(huán)問(wèn)題 2 * 問(wèn)題：約瑟夫環(huán) 3 * 有編號(hào)從1到N的N個(gè)人坐成一圈報(bào)數(shù)，從第K個(gè)人開(kāi)始報(bào)數(shù)，報(bào)到M的人出局， 4 * 下一位再?gòu)?開(kāi)始報(bào)數(shù)，如此持續(xù)，直止剩下一位為止，報(bào)告此人的編號(hào)X。 5 * 輸入N,K,M，求出X。 6 */ 7 8 #include <iostream> 9 using namespace std; 10 11 struct MyNode 12 { 13 MyNode(int a_data):m_data(a_data),m_pNext(NULL) {} 14 15 int m_data; 16 MyNode *m_pNext; 17 }; 18 19 class Josephus 20 { 21 public: 22 Josephus(int a_N, int a_K, int a_M):m_N(a_N),m_K(a_K),m_M(a_M) 23 { 24 createList(); 25 outputList(); 26 } 27 28 protected: 29 void createList(); 30 void outputList(); 31 32 private: 33 MyNode *m_pHead;//循環(huán)鏈表的頭節(jié)點(diǎn) 34 int m_N; //鏈表節(jié)點(diǎn)個(gè)數(shù) 35 int m_K; //第一個(gè)報(bào)數(shù)人的序號(hào) 36 int m_M; //報(bào)數(shù)出局的數(shù) 37 }; 38 39 void Josephus::createList() 40 { 41 MyNode *pre = NULL; 42 MyNode *cur = NULL; 43 MyNode *p = new MyNode(1); 44 m_pHead = p; 45 cur = p; 46 for (int i=2; i<=m_N; i++) 47 { 48 p = new MyNode(i); 49 pre = cur; 50 cur = p; 51 pre->m_pNext = cur; 52 } 53 cur->m_pNext = m_pHead; 54 55 int n=m_N; 56 p = m_pHead; 57 while (n--) 58 { 59 cout << p->m_data << ","; 60 p = p->m_pNext; 61 } 62 cout << endl; 63 } 64 65 void Josephus::outputList() 66 { 67 MyNode *pre = NULL; 68 MyNode *cur = m_pHead; 69 m_K--; 70 while (m_K--) //尋找第K個(gè)人（開(kāi)始報(bào)數(shù)的人） 71 { 72 pre = cur; 73 cur = cur->m_pNext; 74 } 75 while (m_N--) //輸出鏈表中所有的節(jié)點(diǎn)值 76 { 77 int s = m_M-1; 78 while (s--) //尋找間隔M的人 79 { 80 pre = cur; 81 cur = cur->m_pNext; 82 } 83 MyNode *p = cur; 84 cout << p->m_data << ","; 85 cur = cur->m_pNext; //刪除節(jié)點(diǎn)的過(guò)程 86 pre->m_pNext = cur; 87 delete p; 88 p=NULL; 89 } 90 } 91 92 int main() 93 { 94 Josephus josephus(100,5,5); 95 return 0; 96 }

?

測(cè)試結(jié)果：

轉(zhuǎn)載于:https://www.cnblogs.com/hanxi/archive/2012/10/10/2718413.html

總結(jié)

以上是生活随笔為你收集整理的循环链表解决约瑟夫环问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。