C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)——用鏈表處理約瑟夫問(wèn)題-創(chuàng)新互聯(lián)

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

問(wèn)題描述：

約瑟夫問(wèn)題：有ｎ只猴子，按順時(shí)針?lè)较驀梢蝗x大王（編號(hào)從１到ｎ），從第１號(hào)開(kāi)始報(bào)數(shù)，一直數(shù)到ｍ，數(shù)到ｍ的猴子退出圈外，剩下的猴子再接著從1開(kāi)始報(bào)數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時(shí)，這個(gè)猴子就是猴王，編程求輸入ｎ，ｍ后，輸出最后猴王的編號(hào)。

輸入輸出要求：

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

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

樣例輸出：5 1 7

解決思路：

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

//建立結(jié)點(diǎn)數(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.當(dāng)猴子報(bào)數(shù)為m時(shí)，將該猴子所表示的結(jié)點(diǎn)刪除，并將下一個(gè)結(jié)點(diǎn)（猴子）標(biāo)號(hào)為1，看作是下一趟報(bào)數(shù)的起點(diǎn)。

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

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

代碼實(shí)現(xiàn)：

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

int main()
{
	int n,m,count,i;
	//定義頭結(jié)點(diǎn)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指向第一個(gè)結(jié)點(diǎn) 
			q = tail;//q指向最后一個(gè)結(jié)點(diǎn)

            i = 1;
			while(p!=q)//出列 
			{
				if(i==m)
				{
					q->next = p->next;
					free(p);
					p = q->next;
					i = 1;//第二趟報(bào)數(shù) 
				}
				else//q指針在p指針之前，如果兩個(gè)指針重合，說(shuō)明只剩下一個(gè)結(jié)點(diǎn) 
				{
				    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海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

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

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

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

猜你還喜歡下面的內(nèi)容