題目鏈接如下：
tOpenJudge - 1748:約瑟夫問題

創(chuàng)新互聯(lián)長期為1000多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為黃驊企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計、做網(wǎng)站，黃驊網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

---

問題描述：

約瑟夫問題：有ｎ只猴子，按順時針方向圍成一圈選大王（編號從１到ｎ），從第１號開始報數(shù)，一直數(shù)到ｍ，數(shù)到ｍ的猴子退出圈外，剩下的猴子再接著從1開始報數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時，這個猴子就是猴王，編程求輸入ｎ，ｍ后，輸出最后猴王的編號。

輸入輸出要求：

輸入：需能同時輸入多組數(shù)據(jù)，以0 0結(jié)尾標志著結(jié)束。

樣例輸入：6 2? 12 4? 8 3? 0 0

樣例輸出：5 1 7

解決思路：

1.由于猴子圍成了一個圈，故此處使用循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，將每只猴子看作是一個結(jié)點，用序號表示。

//建立結(jié)點數(shù)據(jù)結(jié)構(gòu) 
typedef struct node
{
	int data;
	struct node *next;
}Node,*Link;

for(i=0;idata = i+1;
	tail->next = p;
	p->next = head->next;
	tail = p;
}

2.當猴子報數(shù)為m時，將該猴子所表示的結(jié)點刪除，并將下一個結(jié)點（猴子）標號為1，看作是下一趟報數(shù)的起點。

if(i==m)
{
	q->next = p->next;
	free(p);
	p = q->next;
	i = 1;//第二趟報數(shù) 
}

3.如果不是m號猴子，不改變結(jié)點，指針指向下一結(jié)點。

代碼實現(xiàn)：

#include#include#include//建立結(jié)點數(shù)據(jù)結(jié)構(gòu) 
typedef struct node
{
	int data;
	struct node *next;
}Node,*Link;

int main()
{
	int n,m,count,i;
	//定義頭結(jié)點head 
	Link head,tail,p,q;
	head = (Link)malloc(sizeof(Node));
	head->next = NULL;
	
	while(1)
	{
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)//結(jié)束條件 
		{
			free(head);
			break;
		}
		else
		{
			tail = head;
			for(i=0;idata = i+1;
				tail->next = p;
				p->next = head->next;
				tail = p;
			}
			p = head->next;//p指向第一個結(jié)點 
			q = tail;//q指向最后一個結(jié)點

            i = 1;
			while(p!=q)//出列 
			{
				if(i==m)
				{
					q->next = p->next;
					free(p);
					p = q->next;
					i = 1;//第二趟報數(shù) 
				}
				else//q指針在p指針之前，如果兩個指針重合，說明只剩下一個結(jié)點 
				{
				    q = p;
					p = p->next;
					i++;	
				} 
			}
			printf("%d\n",p->data);
			free(p); 	 
		}
	}
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：C語言數(shù)據(jù)結(jié)構(gòu)——用鏈表處理約瑟夫問題-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://vcdvsql.cn/article16/cecedg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、ChatGPT、網(wǎng)站策劃、標簽優(yōu)化、軟件開發(fā)、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)