約瑟夫問題

介紹

約瑟夫問題，又稱約瑟夫置換、丟手絹問題。

一般形式

（本部分內(nèi)容來自百度百科）

約瑟夫問題是個(gè)有名的問題：N個(gè)人圍成一圈，從第一個(gè)開始報(bào)數(shù)，第M個(gè)將被殺掉，最后剩下一個(gè)，其余人都將被殺掉。例如N=6，M=5，被殺掉的順序是：5，4，6，2，3。

代碼

問題描述

本文以以下問題為例

編號(hào)為1-10的10 個(gè)人圍成一圈，從第一個(gè)開始報(bào)數(shù)，第9個(gè)被淘汰出圈，剩下的組成新的圈。依次這樣下去，求最后一個(gè)人的編號(hào)

解決

注意：該段代碼與上篇文章——《 循環(huán)鏈表定義及操作 》相接

//解答約瑟夫問題 bool Joseph(LinkList* &L, int interval) {LinkList *p = L, *q;int i = 0, j = 0;int times = 0; //當(dāng)前輪數(shù)int num = 0;if(!L || p->next == L){cout << "鏈表為空\n";return false;}if(interval < 1){cout << "報(bào)數(shù)淘汰口令不能小于1\n";return false;}do{i += interval;//找查第i個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)while(p->next){if(p->next != L){//如果不是頭結(jié)點(diǎn)的話j++;}if(j >= i) break;p = p->next;}times++;q = p->next; //臨時(shí)保存被刪結(jié)點(diǎn)以備釋放空間num = q->data;cout << "當(dāng)前結(jié)點(diǎn):" << q->data<< " 上一個(gè)結(jié)點(diǎn):" << p->data<<" 下一個(gè)結(jié)點(diǎn):" << q->next->data<< endl;p->next = q->next;delete q; //釋放被刪除結(jié)點(diǎn)內(nèi)存LinkListPrint(L);}while(L->next != L); //鏈表不為空，繼續(xù)報(bào)數(shù)cout << "最后一個(gè)出圈者的編號(hào)" << num << endl;return true; }

完整代碼

代碼

#include <iostream> #include <string>using namespace std;typedef struct _LinkNode {int data;struct _LinkNode *next; }LinkList;bool InitList(LinkList* &L) {L = new LinkList;if(!L) return false;L->next = L;L->data = 0;return true; }bool ListInsert_back(LinkList* &L, LinkList *node) {LinkList *last = NULL;if(!L || !node) return false;if(L == L->next){//頭結(jié)點(diǎn)指針指向了自己（鏈表只有頭結(jié)點(diǎn)）node->next = L;L->next = node;}else{//非空的循環(huán)鏈表last = L->next;//尋找尾結(jié)點(diǎn)（指向頭結(jié)點(diǎn)的結(jié)點(diǎn)）while(last->next != L){last = last->next;}node->next = L;last->next = node;}return true; }void LinkListPrint(LinkList *L) {LinkList *p;if(!L || L == L->next){cout << "鏈表為空\n";return;}p = L->next;while(p != L){cout << p->data << "\t";p = p->next;}cout << endl; }//解答約瑟夫問題 bool Joseph(LinkList* &L, int interval) {LinkList *p = L, *q;int i = 0, j = 0;int times = 0; //當(dāng)前輪數(shù)int num = 0;if(!L || p->next == L){cout << "鏈表為空\n";return false;}if(interval < 1){cout << "報(bào)數(shù)淘汰口令不能小于1\n";return false;}do{i += interval;//找查第i個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)while(p->next){if(p->next != L){//如果不是頭結(jié)點(diǎn)的話j++;}if(j >= i) break;p = p->next;}times++;q = p->next; //臨時(shí)保存被刪結(jié)點(diǎn)以備釋放空間num = q->data;cout << "當(dāng)前結(jié)點(diǎn):" << q->data<< " 上一個(gè)結(jié)點(diǎn):" << p->data<<" 下一個(gè)結(jié)點(diǎn):" << q->next->data<< endl;p->next = q->next;delete q; //釋放被刪除結(jié)點(diǎn)內(nèi)存LinkListPrint(L);}while(L->next != L); //鏈表不為空，繼續(xù)報(bào)數(shù)cout << "最后一個(gè)出圈者的編號(hào)" << num << endl;return true; }int main() {LinkList *L, *s;int i = 0;if(InitList(L)){cout << "創(chuàng)建一個(gè)空的循環(huán)鏈表\n";}else{exit(-1);}cout << "尾插10個(gè)元素...\n";while((++i)<=10){s = new LinkList;s->data = i;s->next = NULL;if(ListInsert_back(L, s)){cout << "success\n";}else{cout << "default\n";}}LinkListPrint(L);Joseph(L,9);return 0;}

輸出結(jié)果

注：0為頭結(jié)點(diǎn)的數(shù)據(jù)，該結(jié)點(diǎn)并不計(jì)入約瑟夫環(huán)中（但最后也將其刪除銷毀鏈表釋放內(nèi)存）

創(chuàng)建一個(gè)空的循環(huán)鏈表 尾插10個(gè)元素... success success success success success success success success success success 1 2 3 4 5 6 7 8 9 10 當(dāng)前結(jié)點(diǎn):9 上一個(gè)結(jié)點(diǎn):8 下一個(gè)結(jié)點(diǎn):10 1 2 3 4 5 6 7 8 10 當(dāng)前結(jié)點(diǎn):8 上一個(gè)結(jié)點(diǎn):7 下一個(gè)結(jié)點(diǎn):10 1 2 3 4 5 6 7 10 當(dāng)前結(jié)點(diǎn):10 上一個(gè)結(jié)點(diǎn):7 下一個(gè)結(jié)點(diǎn):0 1 2 3 4 5 6 7 當(dāng)前結(jié)點(diǎn):2 上一個(gè)結(jié)點(diǎn):1 下一個(gè)結(jié)點(diǎn):3 1 3 4 5 6 7 當(dāng)前結(jié)點(diǎn):5 上一個(gè)結(jié)點(diǎn):4 下一個(gè)結(jié)點(diǎn):6 1 3 4 6 7 當(dāng)前結(jié)點(diǎn):3 上一個(gè)結(jié)點(diǎn):1 下一個(gè)結(jié)點(diǎn):4 1 4 6 7 當(dāng)前結(jié)點(diǎn):4 上一個(gè)結(jié)點(diǎn):1 下一個(gè)結(jié)點(diǎn):6 1 6 7 當(dāng)前結(jié)點(diǎn):1 上一個(gè)結(jié)點(diǎn):0 下一個(gè)結(jié)點(diǎn):6 6 7 當(dāng)前結(jié)點(diǎn):6 上一個(gè)結(jié)點(diǎn):0 下一個(gè)結(jié)點(diǎn):7 7 當(dāng)前結(jié)點(diǎn):7 上一個(gè)結(jié)點(diǎn):0 下一個(gè)結(jié)點(diǎn):0 鏈表為空 最后一個(gè)出圈者的編號(hào)7

總結(jié)

以上是生活随笔為你收集整理的循环链表应用——约瑟夫置换的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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