實驗四 約瑟夫生死游戲

1、實驗目的：
利用線性表解決實際問題。

2、實驗環境與設備：
已安裝Visual Studio 2010（或其以上版本）集成開發環境的計算機。

3、實驗原理：
（1）利用線性表的刪除功能剔除被殺掉的人。
（2）利用單鏈表、不帶頭結點的循環鏈表或帶頭結點的循環鏈表均可實現。

4、實驗內容：
約瑟夫生死游戲問題有如下幾種表述；
表述一：古代某法官要判決N個犯人的死刑，他有一條荒唐的法律，將犯人站成一個圓圈，從第S個人開始數起，每數到第D個犯人，就拉出來處決，然后再數D個，數到的再處決……直到剩下的最后一個可赦免。
表述二：17世紀的法國數學家加斯帕在《數目的游戲問題》中講了這樣一個故事: 15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法: 30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就將他扔入大海，如此循環進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。
表述三：30個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數，數到第9人，便把他投入大海中，然后從他的下一個人數起，數到第9人，再將他投入大海，如此循環，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。
表述四：據說著名猶太歷史學家 Josephus有過以下的故事:在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人(因為第一個人已經被越過)，并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了規則，一開始要站在什么地方才能避免被處決?Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
其數學模型歸結如下：
數學模型：假設n個人排成一個環形，依次順序編號1，2，…，n。從第1號開始，沿環計數，每數到第m個人就讓其出列，且從下一個人開始重新計數，繼續進行下去。這個過程一直進行到剩下k個人為止。
試利用線性表編程模擬該游戲。
5、實驗考核：
（1）完成紙質版實驗報告
（2）提交電子版作業

6、執行結果示例如下：

圖1 示例一

圖2 實例二

圖3 示例三

上代碼

#include<stdio.h> #include<malloc.h> #define OK 1 #define FALSE -1 #define TURE 1 #define ERROR -1 #define INFEASIBLE -1typedef int Elemtype; typedef struct LNode {Elemtype data;struct LNode *next; }LNode, *LinkList;LinkList p, r, last = NULL; // 構造一個不帶頭結點的循環鏈表，并賦值 1~n void CreatList(int n) {for (int i = 1; i <= n; i++){p = (LinkList)malloc(sizeof(LNode)); // 申請一個新的鏈結點p->data = i; // 存放第 i 個結點的元素 if (last == NULL)last = p;elser->next = p;r = p;}p->next = last;p = last; // 循環鏈表建立完成 } // 將頭指針 p 指向第 s 個人 ,從第幾個人開始 void StartNum(int s) {for (int i = 1; i < s; i++){r = p;p = p->next;}// 此時 p 指向第 1 個出發結點 } // 依次輸出被刪除的元素及最后剩余的元素。 void DeleteList(int m) {while (p->next != p)//不指向自己{for (int i = 1; i < m; i++){r = p;p = p->next;}//p 指向第 m 個結點 ,r 指向第 m-1 個結點r->next = p->next;// 刪除第 m 個結點printf("Number %d is out\n", p->data);// 依次輸出刪除結點的元素 free(p);// 釋放被刪除結點的空間p = r->next;//p 指向新的出發結點}printf("Number %d is save\n", p->data);// 輸出最后一個結點的元素 }void DeleteNum(int m,int save,int n) {while (p->next!=p)//不指向自己{for (int i = 1; i < m; i++){r = p;p = p->next;}//p 指向第 m 個結點 ,r 指向第 m-1 個結點r->next = p->next;// 刪除第 m 個結點printf("Number %d is out\n", p->data);// 依次輸出刪除結點的元素 free(p);// 釋放被刪除結點的空間p = r->next;//p 指向新的出發結點n--;if (n == save) break;}while (p->next != NULL) {printf("Number %d is save\n", p->data);p = p->next;save--;if (save == 0) break;} }//大佬算法，一行解決！！ int f(int n, int m)//n：人數 m：間隔 {return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1; }int main() {int n, m, s,save = 1;//n總人數 m間隔 s開始的位置 先默認save=1printf("請輸入總人數 n:\n");//總人數scanf_s("%d", &n);//間隔printf("請輸入間隔 m:\n");scanf_s("%d", &m);//開始的位置printf("請輸入開始的位置 s:\n");scanf_s("%d", &s);//要剩的人數printf("請輸入要保留的人數 s:\n");scanf_s("%d", &save);CreatList(n);StartNum(s);printf("****** Solve Josephus Problem ******\n");DeleteNum(m,save,n);printf("**************** END ***************\n");//還有個大佬算法，只保留一個人，遞歸調用，一行出結果// printf("%d\n",f(n,m));system("pause");return 0; }

結果
（1）演示6剩1（間隔3）

（2）表述二和三：30剩15（間隔9）

（3）表述四：41剩2（間隔3）

總結

以上是生活随笔為你收集整理的数据结构实验四 约瑟夫生死游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。