循環鏈表解決約瑟夫問題（簡化版）

http://blog.csdn.net/jw903/article/details/38965477

約瑟夫環是一個經典的數學的應用問題：已知N個人（以編號1，2，3...N分別表示）圍坐在一張圓桌周圍。從編號為1的人開始報數，數到M的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重復下去，直到圓桌周圍的人全部出列。

這個代碼非常簡短，但還是利用循環鏈表完成了求解約瑟夫問題的功能

代碼如下：

[cpp]?view plain?copy 
 #include<iostream>??
 #include<cassert>??
 using?namespace?std;??
 typedef?struct?Node??
 {??
 ????int?item;??
 ????struct?Node?*next;??
 }ListNode,*List;??
 int?main()??
 {??
 ????int?M;//規則（隔M個數）??
 ????int?N;//人數（N個人）??
 ????int?a;//編號??
 ????int?i;??
 ????cout<<"input?the?N?and?M"<<endl;??
 ????cin>>N>>M;??
 ????List?head=(List)malloc(sizeof(ListNode));??
 ????assert(head!=NULL);??
 ????cin>>a;??
 ????head->item=a;??
 ????head->next=head;??
 ????ListNode?*p=head;??
 ????for(i=2;i<=N;i++)//構造循環鏈表，值為1的結點為鏈表頭??
 ????{??
 ????????cin>>a;??
 ????????p->next=(List)malloc(sizeof(ListNode));??
 ????????p=p->next;??
 ????????p->item=a;??
 ????????p->next=head;??
 ????}??
 ????while(p!=p->next)//while循環開始時，p指向鏈表的尾結點??
 ????{??
 ????????for(i=1;i<M;i++)??
 ????????????p=p->next;??
 ????????ListNode?*targetnode=p->next;??
 ????????cout<<targetnode->item<<"出局"<<endl;??
 ????????p->next=p->next->next;??
 ????????free(targetnode);??
 ????}??
 ????cout<<p->item<<endl;??
 ????return?0;??
 }??

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/384237.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384237.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384237.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！