链表：约瑟夫问题（两种解法）

╰+哭是因爲堅強的太久メ 2022-03-29 03:07 145阅读 0赞

描述

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

输入

每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：  
  
0 0

输出

对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号

样例输入

6 2
    12 4
    8 3
    0 0

样例输出

5
    1
    7

> 解法1：不使用STL

第一遍提交的时候出现了Presentation Error，说明我的答案和参考答案很接近了，可能是由于输出格式与参考答案不一致，下面是出错的代码：

#include<cstdio>
    
    struct node{
    	int num;
    	node *nxt, *pre;//nxt指向结点的后继，pre指向结点的前驱 
    }*head, *tail, *p;
    
    int main()
    {
    	int n,m;
    	while(scanf("%d%d",&n,&m) && n || m)//n为真或者m为真(真即不为0）
    	{
    		head = new node;
    		head->pre = NULL;
    		head->nxt = NULL;
    		head->num = 1;
    		tail = head;
    		
    		for(int i = 2; i <= n; ++i)//新建结点插入 
    		{
    			p = new node;
    			tail->nxt = p;
    			p->pre = tail;
    			p->nxt = NULL;
    			p->num = i;
    			tail = p; 
    		}
    		
    		head->pre = tail;//循环链表，头尾相连 
    		tail->nxt = head;
    		
    		p = head;
    		for(int i = 1; i < n; ++i)//每循环一次删除一个结点，只需要循环n-1次最后就只剩一个结点了，该结点就是我们需要的答案 
    		{
    			for(int j = 1; j < m; ++j)//每经过m-1次就删掉一个结点 
    			{
    				p = p->nxt;	
    			}
    			p->pre->nxt = p->nxt;
    			p->nxt->pre = p->pre; 
    			p = p->nxt;
    		} 
    		printf("%d",p->num);
    	} 
    	return 0;
    }

测试时发现答案是正确的，问题出在最后的printf("%d",p->num);没有加换行。

下面是ac后的代码：

> 解法2：使用STL
> 
> 需要注意的是list<int> a;这个语句每一次输入数据后都需要重新定义一遍，否则a可能会有之前的数据最后导致答案错误。

#include<cstdio>
    #include<list>
    #include<iostream>
    using namespace std;
    
    int main()
    {
    	int n,m;	
    	while(scanf("%d%d",&n,&m), n!= 0 || m != 0)
    	{
    		list<int> a;
    		for(int i = 1; i <= n; ++i)//将数据存入链表 
    		{
    			a.push_back(i);
    		}
    		list<int>::iterator it;
    		it = a.begin();
    		while(a.size() > 1)
    		{
    			for(int i = 1; i < m; ++i)//构建循环链表，当数到第m个数的时候删除 
    			{
    				it++;
    				if(it == a.end())//a.end()是指向最后一个数的下一个数 
    					it = a.begin();
    			}
    			list<int>::iterator nxt = ++it;
    			if(nxt == a.end())
    			{
    				nxt = a.begin();
    			}
    			--it;
    			a.erase(it);//删除第m个数 
    			it = nxt;//指向下一个数 
    		}
    		printf("%d\n",*it);
    	}
    	return 0;
    }

#include<cstdio>
    #include<list>
    #include<iostream>
    using namespace std;
    
    int list1(int n,int m)
    {
    	list<int> a;//放在里面，每一组数据都需要重新构建链表 
    	for(int i = 1; i <= n; ++i)//将数据存入链表 
    	{
    		a.push_back(i);
    	}
    	list<int>::iterator it;
    	it = a.begin();
    	while(a.size() > 1)
    	{
    		for(int i = 1; i < m; ++i)//构建循环链表，当数到第m个数的时候删除 
    		{
    			it++;
    			if(it == a.end())//a.end()是指向最后一个数的下一个数 
    				it = a.begin();
    		}
    		list<int>::iterator nxt = ++it;
    		if(nxt == a.end())
    		{
    			nxt = a.begin();
    		}
    		--it;
    		a.erase(it);//删除第m个数 
    		it = nxt;//指向下一个数 
    	}
    	printf("%d\n",*it);
    }
    int main()
    {
    	int n,m;	
    	while(scanf("%d%d",&n,&m), n!= 0 || m != 0)
    	{
    		list1(n,m);
    	}
    	return 0;
    }