這是一道經典的鏈表題
約瑟夫環–自殺環問題
約瑟夫環問題有著這樣的歷史：
Josephus有過的故事：39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓，于是決定了自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后下一個重新報數，直到所有人都自殺身亡為止，然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲，
大致意思
一共有N個人圍坐在一起， 回圈周期是M， 第一個人報數1， 第二個人報數2， 當報數到M時， 這個人就會出列， 下一個人繼續從1開始報數， 整個程序持續到所有人出列為止， 這種問題一般會問最后一個出列的人是誰， 或者問你某個人是第幾個出列的，，，
對于學習了計算機的我們來說，重復性如此強的程序，當然要交給計算機來幫我們完成吶，所以我們一起來撰寫這個程式吧，
之前更了陣列實作和數學推理方法，現在來補鏈表法，
大致思路
建立一個單向回圈鏈表（看題目而定），先建立一個表頭，在把每個人一個一個的尾插進去，然后把頭尾相連，在模擬報數，把要自殺的人一個一個刪掉，最后留下來的那個，就是答案，
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
} node;
node* creat(int data)
{
node *head;
head = (node *)malloc(sizeof(node));
head->data = data;
head->next = NULL;
return head;
}
//建立鏈表
node* creatnode(node* head, int data)
{
node *now = head;
node *neww = (node*)malloc(sizeof(node));
neww->data = data;
neww->next = NULL;
while(NULL != now->next)
now = now->next;
now->next = neww;
return neww;
}
//插入節點
void merge(node* head, node* end)
{
end->next = head;
}
//首尾相連
void detele(node* qian, node* need){
qian->next = need->next;
free(need);
}
//洗掉節點
int main()
{
node *head = creat(1);
node *end;
node *now = head;
int n, m, i, j;//n表示有多少個人，m表示報到幾就自殺，
scanf("%d%d", &n, &m);
for(i=2;i<=n;i++)
end = creatnode(head, i);
merge(head, end);
node *qian = end;
for(i=1;i<n;i++)
{
for(j=1;j<m;j++)
{
now = now->next;
qian = qian->next;
}
if(i!=(n-1)){
detele(qian, now);
now = qian->next;
}
}
printf("%d", qian->data);
return 0;
}
謝謝觀看！陣列模擬實作和數學推理法在這里！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266289.html
標籤：其他
下一篇：石子合并