C語言如何解決約瑟夫環(huán)問題
更新時(shí)間：2024年12月17日 09:39:51 作者：happy life 2022
文章總結(jié)了四種解決特定問題的方法,包括單循環(huán)鏈表法、循環(huán)數(shù)組法、遞歸法和迭代法,并分享了個(gè)人經(jīng)驗(yàn)
題目
解答
法一：單循環(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)鏈表的長度
int ListLength(CLinkList L){
CLinkList p;
int count;
if(L){
count = 0;
p = L; //p指向頭結(jié)點(diǎn)
while(p->next!=L){ //p沒到表頭
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)，正向訪問鏈表
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)問題(帶頭結(jié)點(diǎn))
這里的單循環(huán)鏈表使用了帶頭結(jié)點(diǎn)的，方便找到表頭的位置，但是由于頭結(jié)點(diǎn)不存儲(chǔ)元素，因此需要跳過頭結(jié)點(diǎn)
鏈表插入刪除都比較方便，不需要移動(dòng)大量元素，只需要移動(dòng)指針即可，適合這一類問題
*/
void Algo(CLinkList L,int k,int m){ //從編號(hào)為k的人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
int count,i,j; //count表示每次從1開始數(shù)，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) //跳過頭結(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)，跳過頭結(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)，說明單循環(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) //跳過頭結(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的人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
CreateList_TL(&L,s,n); //頭插法建立單循環(huán)鏈表
ListTraverse(L); //遍歷原始隊(duì)列
printf("假設(shè)第一次從編號(hào)為%d的人開始數(shù)，數(shù)到%d的那個(gè)人出環(huán)\n",k,m);
Algo(L,k,m); //用單循環(huán)鏈表解決約瑟夫環(huán)問題(帶頭結(jié)點(diǎn))
}法二：循環(huán)數(shù)組
/*
用循環(huán)數(shù)組解決約瑟夫環(huán)問題
解決問題的難點(diǎn)有兩個(gè):
1、如何求下一個(gè)的人的位置：在循環(huán)數(shù)組中向后移動(dòng)采用：(k+l)%n
2、此人出圈后對(duì)這個(gè)人的位置如何處理：先將出圈人的位置打印輸出，然后將其位置元素設(shè)置為0，表示它已出圈，以后見到它就直接跳過去
*/
void Algo2(int s[],int n,int k0,int m){ //開始一共有n個(gè)人，從第k0個(gè)人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
int i,j,k=k0-1; //元素訪問的下標(biāo)為 k，初始時(shí)從第k0個(gè)人開始數(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){ //如果還沒有數(shù)到m
while(s[k]==0) //如果s[k]為0，證明它已經(jīng)出圈了，則跳過它
k=(k+1)%n;
j++; //數(shù)下一個(gè)數(shù)
k=(k+1)%n; //數(shù)組下標(biāo)向后走一步
}
while(s[k]==0) //如果數(shù)到m發(fā)現(xiàn)它出圈了，則跳過它，找到第一個(gè)沒出圈的數(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的人開始數(shù)，數(shù)到m的那個(gè)人出隊(duì)列
printf("假設(shè)第一次從編號(hào)為%d的人開始數(shù)，數(shù)到%d的那個(gè)人出環(huán)\n",k,m);
Algo2(s,n,k,m); //用循環(huán)數(shù)組解決約瑟夫環(huán)問題
}法三：遞歸
/*
用遞歸解決約瑟夫環(huá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的人開始數(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)問題
遞推公式：
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的人開始數(shù)，最后出環(huán)的是：%d\n",Algo4(n,m));
}總結(jié)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
c#中實(shí)現(xiàn)退出程序后自動(dòng)重新啟動(dòng)程序的方法
下面小編就為大家?guī)硪黄猚#中實(shí)現(xiàn)退出程序后自動(dòng)重新啟動(dòng)程序的方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-01-01
Ubuntu16.04下配置VScode的C/C++開發(fā)環(huán)境
這篇文章主要介紹了Ubuntu16.04下配置VScode的C/C++開發(fā)環(huán)境的教程，本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03
C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解
單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問要通過順序讀取從頭部開始。本文將為大家詳細(xì)講講單向鏈表的實(shí)現(xiàn)與使用，需要的可以參考一下2022-08-08
今天小編就為大家分享一篇關(guān)于關(guān)于C++動(dòng)態(tài)分配內(nèi)存的介紹，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2021-08-08
C#如何調(diào)用原生C++ COM對(duì)象詳解
這篇文章主要給大家介紹了C#如何調(diào)用原生C++ COM對(duì)象，在C++中實(shí)現(xiàn)C#的接口。文中通過示例代碼介紹的很詳細(xì)，相信對(duì)大家的理解和學(xué)習(xí)會(huì)有一定的參考借鑒價(jià)值，有需要的朋友們下面來一起看看吧。2016-12-12
這篇文章主要為大家詳細(xì)介紹了日歷拼圖C++的解法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要為大家詳細(xì)介紹了C語言的字符函數(shù)和字符串函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
詳解C語言中free()函數(shù)與getpagesize()函數(shù)的使用
這篇文章主要介紹了詳解C語言中free()函數(shù)與getpagesize()函數(shù)的使用,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)消消樂游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
我們知道聲明的所有變量在內(nèi)存中都有一個(gè)特定的地址。聲明一個(gè)指針變量來指向內(nèi)存中的這些地址，這篇文章主要介紹了C++中指針和內(nèi)存分配，需要的朋友參考下吧2021-06-06