數(shù)據(jù)結(jié)構(gòu)C語言版：約瑟夫問題（殺人問題）

故事背景

據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經(jīng)被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進(jìn)行，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

#include<stdio.h>typedef int ElemType;// 定義結(jié)構(gòu)體 typedef struct Joseph {ElemType data;struct Joseph* next; }Joseph;// 初始化約瑟夫環(huán) Joseph* InitList(Joseph* J) {J = (Joseph*)malloc(sizeof(Joseph)); // 頭結(jié)點J->next = J;J->data = 1; // 不帶頭節(jié)點的約瑟夫循環(huán)Joseph* p, * q;q = J;int People;printf("請輸入約瑟夫環(huán)中有多少人：");scanf("%d", &People);for (int i = 2; i < People + 1; i++) {p = (Joseph*)malloc(sizeof(Joseph));p->data = i;p->next = J->next;J->next = p;J = p;}return q; }// 判斷約瑟夫循環(huán)的人數(shù) int LengthList(Joseph* J) {Joseph* p;int count = 0;p = J;do {p = p->next;count++;} while (p != J);return count; }// 輸出殺人順序 TraverseList(Joseph* J) {Joseph* p, * q, * r;p = J;q = J; // 用來查找p的前一個結(jié)點int number, count = 0;int m = LengthList(J); // 作為循環(huán)結(jié)束的條件printf("請輸入數(shù)到幾死：");scanf("%d", &number);printf("殺人順序為：");while (m) {count++; // 計數(shù)器if (count == number) {printf("%d號 ", p->data);m--; // 每殺一個人，m就自減，直到為零退出循環(huán)// 尋找p的前一個結(jié)點while (q->next != p) {q = q->next;}r = p;p = p->next; // p先自己向后移動一個位置free(r); // 釋放掉之前的pq->next = p; // q(原本是p的前一個結(jié)點)，現(xiàn)在指向p，相當(dāng)于刪除了之前的p結(jié)點count = 0;}else {p = p->next;}}putchar('\n'); }int main() {Joseph* J = NULL;J = InitList(J);TraverseList(J); }

總結(jié)

以上是生活随笔為你收集整理的数据结构C语言版：约瑟夫问题（杀人问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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