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