C語言如何解決約瑟夫環(huán)問題
更新時間：2024年12月17日 09:39:51 作者：happy life 2022
文章總結(jié)了四種解決特定問題的方法,包括單循環(huán)鏈表法、循環(huán)數(shù)組法、遞歸法和迭代法,并分享了個人經(jīng)驗
題目
解答
法一：單循環(huán)鏈表
#include<stdio.h>
#include<stdlib.h>
//定義單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)
typedef struct CNode{
int data;
struct CNode *next;
}CNode;
typedef CNode *CLinkList;
//初始化一個指向頭節(jié)點的指針，使頭指針->next=頭指針，頭指針->data不做處理
void InitList_L(CLinkList *L){
(*L) = (CLinkList)malloc(sizeof(CNode));
if(!(*L))
exit(-2);
(*L)->next = *L;
}
//頭插法建立單循環(huán)鏈表
int CreateList_HL(CLinkList *L,int s[],int n){ //二級指針
int i;
CLinkList p;
*L = (CLinkList)malloc(sizeof(CNode));
if(!(*L))
exit(-2);
(*L)->next = *L; //只有一個頭節(jié)點head，就讓next指向自己
for(i=0; i<n; i++){
p = (CLinkList)malloc(sizeof(CNode));
if(!p)
exit(-2);
p->data = s[i]; //錄入數(shù)據(jù)
p->next = (*L)->next; //將頭指針所指向的下一個結(jié)點的地址，賦給新創(chuàng)建結(jié)點的next
(*L)->next = p; //將新創(chuàng)建的結(jié)點的地址賦給頭指針的下一個結(jié)點
}
return 1;
}
//尾插法建立單循環(huán)鏈表
int CreateList_TL(CLinkList *L,int s[],int n){
int i;
CLinkList p, q;
*L = (CLinkList)malloc(sizeof(CNode));
if(!(*L))
exit(-2);
(*L)->next = *L; //只有一個頭節(jié)點head，就讓next指向自己
for(i=0,q=*L; i<n; i++){
p = (CLinkList)malloc(sizeof(CNode));
if(!p)
exit(-2);
p->data = s[i]; //錄入數(shù)據(jù)
q->next = p;
q = q->next;
}
q->next = *L; //最后一個結(jié)點指向head
return 1;
}
//求單循環(huán)鏈表的長度
int ListLength(CLinkList L){
CLinkList p;
int count;
if(L){
count = 0;
p = L; //p指向頭結(jié)點
while(p->next!=L){ //p沒到表頭
count++;
p = p->next;
}
}
return count;
}
//得到指向單循環(huán)鏈表第i個元素的指針
CLinkList GetElemPtr(CLinkList L, int i){
int count;
CLinkList p;
if(L&&i>0){
count = 1;
p = L->next;
while(p!=L && count<i){
count++;
p = p->next;
}
if(p!=L) //L為頭指針
return p;
}
return NULL;
}
//單循環(huán)鏈表第i個位置插入元素e
int ListInsert(CLinkList L, int i, int e){
CLinkList p, s;
int j;
if(i<1 || i>ListLength(L)+1) //插入位置不合理
return 0;
p = L;
j = 0;
while(j<i-1){ //尋找第i-1個結(jié)點
p = p->next;
++j;
}
s = (CLinkList)malloc(sizeof(CNode));
if(!s)
exit(-2);
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
//單循環(huán)鏈表第i個位置刪除元素e
int ListDelete(CLinkList L, int i, int *e){
CLinkList pre, p;
int j;
if(i<1 || i>ListLength(L)) //刪除位置不合理
return 0;
pre = L;
j = 1;
while(pre->next && j<i){ //尋找第i個結(jié)點，并令pre指向其前驅(qū)
pre = pre->next;
++j;
}
p = pre->next;
pre->next = p->next;
*e = p->data;
free(p);
p=NULL;
return 1;
}
//遍歷單循環(huán)鏈表
void ListTraverse(CLinkList L){
CLinkList p;
p = L->next; //p指向頭結(jié)點，正向訪問鏈表
while(p!=L){
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
//判斷單循環(huán)鏈表是否為空
int ListEmpty(CLinkList L){
if(L!=NULL && L->next==L) //單循環(huán)鏈表存在并且只有頭結(jié)點
return 1;
else
return 0;
}
/*
用單循環(huán)鏈表解決約瑟夫環(huán)問題(帶頭結(jié)點)
這里的單循環(huán)鏈表使用了帶頭結(jié)點的，方便找到表頭的位置，但是由于頭結(jié)點不存儲元素，因此需要跳過頭結(jié)點
鏈表插入刪除都比較方便，不需要移動大量元素，只需要移動指針即可，適合這一類問題
*/
void Algo(CLinkList L,int k,int m){ //從編號為k的人開始數(shù)，數(shù)到m的那個人出隊列
int count,i,j; //count表示每次從1開始數(shù)，i用來找編號為k的結(jié)點的前驅(qū)
CLinkList pre,p;
pre=L;
count=1,i=1,j=1;
/*尋找第k個結(jié)點，并令pre指向其前驅(qū)*/
while(i<k){
if(pre->next==L) //跳過頭結(jié)點
pre=pre->next->next;
else
pre = pre->next;
++i;
}
while(L->next!=L){ //如果單循環(huán)鏈表不為空
if(count==m){
/*下一個結(jié)點不是頭結(jié)點，直接刪除*/
if(pre->next!=L){
p=pre->next;
printf("第%d次出環(huán)的元素是%d\n",j++,p->data);
pre->next=p->next;
free(p);
p=NULL;
count=1;
}
/*下一個結(jié)點是頭結(jié)點，下下個結(jié)點不是頭結(jié)點，跳過頭結(jié)點，刪除下下個結(jié)點（頭結(jié)點不保存數(shù)據(jù)，因此不參與運算）*/
else if(pre->next->next!=L){
p=pre->next->next;
printf("第%d次出環(huán)的元素是%d\n",j++,p->data);
pre->next->next=p->next;
free(p);
p=NULL;
count=1;
}
/*下一個結(jié)點是頭結(jié)點，下下個結(jié)點也是頭結(jié)點，說明單循環(huán)鏈表已經(jīng)為空了,只剩下頭結(jié)點，因此跳出循環(huán)*/
else
break;
}
count++; //count代表要刪除的結(jié)點數(shù)的數(shù)，始終在pre指向的結(jié)點之前
if(pre->next==L) //跳過頭結(jié)點
pre=pre->next->next; //pre指向要刪除結(jié)點的前一個結(jié)點
else
pre = pre->next; //pre指向要刪除結(jié)點的前一個結(jié)點
}
}
void main(){
CLinkList L;
int n=5,s[5]={1,2,3,4,5}; //假設(shè)5個人圍坐一圈
int k=3,m=2; //第一次從編號為k的人開始數(shù)，數(shù)到m的那個人出隊列
CreateList_TL(&L,s,n); //頭插法建立單循環(huán)鏈表
ListTraverse(L); //遍歷原始隊列
printf("假設(shè)第一次從編號為%d的人開始數(shù)，數(shù)到%d的那個人出環(huán)\n",k,m);
Algo(L,k,m); //用單循環(huán)鏈表解決約瑟夫環(huán)問題(帶頭結(jié)點)
}法二：循環(huán)數(shù)組
/*
用循環(huán)數(shù)組解決約瑟夫環(huán)問題
解決問題的難點有兩個:
1、如何求下一個的人的位置：在循環(huán)數(shù)組中向后移動采用：(k+l)%n
2、此人出圈后對這個人的位置如何處理：先將出圈人的位置打印輸出，然后將其位置元素設(shè)置為0，表示它已出圈，以后見到它就直接跳過去
*/
void Algo2(int s[],int n,int k0,int m){ //開始一共有n個人，從第k0個人開始數(shù)，數(shù)到m的那個人出隊列
int i,j,k=k0-1; //元素訪問的下標為 k，初始時從第k0個人開始數(shù)
for(i=0;i<n;i++){ //總共循環(huán)n次，每循環(huán)一次，出隊一個元素，k在循環(huán)中會不斷的運動
j=1; //j表示數(shù)的數(shù)，初始為1
while(j<m){ //如果還沒有數(shù)到m
while(s[k]==0) //如果s[k]為0，證明它已經(jīng)出圈了，則跳過它
k=(k+1)%n;
j++; //數(shù)下一個數(shù)
k=(k+1)%n; //數(shù)組下標向后走一步
}
while(s[k]==0) //如果數(shù)到m發(fā)現(xiàn)它出圈了，則跳過它，找到第一個沒出圈的數(shù)
k=(k+1)%n;
printf("第%d次出環(huán)的元素是%d\n",i+1,s[k]); //先將出圈人的位置打印輸出
s[k]=0; //然后將其位置元素設(shè)置為0，表示它已經(jīng)出圈
}
}
void main(){
int n=5,s[5]={1,2,3,4,5}; //假設(shè)5個人圍坐一圈
int k=3,m=2; //第一次從編號為k的人開始數(shù)，數(shù)到m的那個人出隊列
printf("假設(shè)第一次從編號為%d的人開始數(shù)，數(shù)到%d的那個人出環(huán)\n",k,m);
Algo2(s,n,k,m); //用循環(huán)數(shù)組解決約瑟夫環(huán)問題
}法三：遞歸
/*
用遞歸解決約瑟夫環(huán)問題
n指的是總?cè)藬?shù)，m指的是每次最大報到的數(shù)值，i是第i次，該函數(shù)每次可以求出第i次扔海里的人的編號
*/
int Algo3(int n,int m,int i){
if(i==1)
return (n+m-1)%n;
else
return (Algo3(n-1,m,i-1)+m)%n;
}
void main(){
int n=5; //假設(shè)5個人圍坐一圈
int m=2; //數(shù)到2的那個人出環(huán)
printf("假設(shè)第一次從編號為1的人開始數(shù)，數(shù)到%d的那個人出環(huán)\n",m);
for(int i=1;i<=n;i++)
printf("第%d次出環(huán)的元素是%d\n",i,Algo3(n,m,i)+1); //因為求出的結(jié)果是數(shù)組中的下標，最終的編號還要加1
}法四：迭代
/*
用迭代解決約瑟夫環(huán)問題
遞推公式：
f(N,M)=(f(N?1,M)+M)%N
f(N,M)表示，N個人報數(shù)，每報到M時殺掉那個人，最終勝利者的編號
f(N?1,M)表示，N-1個人報數(shù)，每報到M時殺掉那個人，最終勝利者的編號
*/
int Algo4(int n,int m){
int i,p=0;
for(i=2;i<=n;i++){
p=(p+m)%i;
}
return p+1; //因為求出的結(jié)果是數(shù)組中的下標，最終的編號還要加1
}
void main(){
int n=5; //假設(shè)5個人圍坐一圈
int m=2; //數(shù)到2的那個人出環(huán)
printf("假設(shè)第一次從編號為1的人開始數(shù)，最后出環(huán)的是：%d\n",Algo4(n,m));
}總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
C++用new創(chuàng)建對象和不用new創(chuàng)建對象的區(qū)別解析
在C++用new創(chuàng)建對象和不用new創(chuàng)建對象是有區(qū)別的，不知你是否清楚的了解它們到底有什么樣的區(qū)別呢？下面小編就用示例來告訴大家吧，需要的朋友可以過來參考下2013-07-07
這篇文章主要介紹了C++中的數(shù)據(jù)內(nèi)存分布，主要從動態(tài)內(nèi)存管理方式，內(nèi)存泄漏等方面介紹的，文中也有相關(guān)的示例代碼,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了C++ 數(shù)據(jù)類型的相關(guān)資料，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2020-08-08
這篇文章主要內(nèi)容是6個默認成員函數(shù)之一的拷貝構(gòu)造函數(shù)的認識與學習，讓同學們充分理解淺拷貝與深拷貝，感興趣的小伙伴可以參考閱讀2023-04-04
這篇文章主要為大家詳細介紹了OpenGL實現(xiàn)中點劃線法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了使用mmap實現(xiàn)多進程對大文件拷貝，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
C語言的數(shù)組學習入門之對數(shù)組初始化的操作
這篇文章主要介紹了C語言的數(shù)組學習入門之數(shù)組初始化的操作,是C語言入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C++多線程編程時的數(shù)據(jù)保護,作者針對C++11版本中的新特性做出了一些解說,需要的朋友可以參考下2015-07-07
共同體的定義類似結(jié)構(gòu)體，不過共同體的所有成員都在同一段內(nèi)存中存放，起始地址一樣，并且同一時刻只能使用其中的一個成員變量2013-08-08
這篇文章主要為大家詳細介紹了QT實現(xiàn)簡單打地鼠游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12