约瑟夫环问题-C++编程实现

╰+攻爆jí腚メ 2021-09-10 09:42 345阅读 0赞

原题：一组人（n）个，围成一圈，从某人开始数到滴三个的人出列，在接着从下一个人开始数，最终输出最终出列的人（约瑟夫环是一个数学的应用问题：已知n个人（以编号1,2,3,...,n）分别表示）围坐在一张圆桌周围。从编号k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列：依此规律重复下去，知道圆桌周围的人全都出列。

<pre name="code" class="cpp">#include <iostream>
    #include <list>
    #include <vector>
    #include <algorithm>
    using namespace std;
    vector<int> yuesefeng(int n,int m);
    void main()
    {
    	int n,m;
    	cin>>n>>m;
    	vector<int> out;
    	out=yuesefeng(n,m);
    	int i,len=out.size();
    	for(i=0;i<len;i++)
    		cout<<out[i]<<" ";
    	system("pause");
    }
    vector<int> yuesefeng(int n,int m)//n代表初始人数，m代表初始号码
    {
    	vector<int> out;
    	list<int> in;
    	list<int>::iterator pos;
    	int i;
    	for(i=1;i<=n;i++)
    		in.push_back(i);
    	pos=in.begin();
    	int kk=m;
        while(in.size()!=0)
    	{	
    		if(kk!=1)
    		  {
    			  pos++;
    			  kk--;
    		   if(pos==in.end())//注意要判断是否到尾部了，到尾部就指向头部
    			pos=in.begin();
    		   }
    		else
    		{
    			out.push_back(*pos);//到数了，点到的人保存到输出
    			pos=in.erase(pos);///将此人从列表中删除，注意erase返回的是下个人的指针
    			if(pos==in.end())
    				pos=in.begin();
    		}	    
    	}
    	return out;
    }

法二，自己建立循环链表来实现：

/*
    
     程序：约瑟夫死亡环
    
     功能：用户输入N,S,D值，从S至N至1开始顺序循环数数，每数到D输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
    
     时间：2015.1.10
    
     创建人：Evankaka
    
    */
    
    #include <iostream>
    
    using namespace std;
    
    // 链表节点
    
    typedef struct _RingNode
    
    {
    
        int pos;  // 位置
    
        struct _RingNode *next;
    
    }RingNode, *RingNodePtr;
    
    
    
    // 创建约瑟夫环，pHead:链表头指针，count:链表元素个数
    
    void CreateRing(RingNodePtr pHead, int count)
    
    {
    
        RingNodePtr pCurr = NULL, pPrev = NULL;
    
        int i = 1;
    
        pPrev = pHead;
    
        while(--count > 0)
    
        {
    
            pCurr = (RingNodePtr)malloc(sizeof(RingNode));
    
            i++;
    
            pCurr->pos = i;
    
            pPrev->next = pCurr;
    
            pPrev = pCurr;
    
        }
    
        pCurr->next = pHead;  // 构成环状链表
    
    }
    
    
    
    void PrintRing(RingNodePtr pHead)
    
    {
    
        RingNodePtr pCurr;
    
       cout<<pHead->pos;
    
        pCurr = pHead->next;
    
        while(pCurr != NULL)
    
        {
    
            if(pCurr->pos == 1)
    
                break;
    
           cout<<pCurr->pos;
    
            pCurr = pCurr->next;
    
        }
    
    }
    
    
    
    void KickFromRing(RingNodePtr pHead, int m)
    
    {
    
    	while(pHead==NULL)
    
    		return;
    
        RingNodePtr pCurr, pPrev;
    
        int i = 1;    // 计数
    
        pCurr = pPrev = pHead;
    
        while(pCurr != NULL)
    
        {
    
            if (i == m)
    
            {
    
                // 踢出环
    
                cout<<pCurr->pos<<" ";    // 显示出圈循序
    
                pPrev->next = pCurr->next;
    
                free(pCurr);
    
                pCurr = pPrev->next;
    
                i = 1;	
    
            }
    
            pPrev = pCurr;
    
            pCurr = pCurr->next;
    
            if (pPrev == pCurr)
    
            {
    
                // 最后一个
    
                cout<< pCurr->pos;    // 显示出圈循序
    
                free(pCurr);
    
                break;
    
            }
    
            i++;
    
        }
    
    }
    
    
    
    int main()
    
    {
    
        int d = 0, n = 0,s=0;
    
        RingNodePtr pHead = NULL;
    
       cout<<"---------------Josephus Ring---------------\n";
    
        cout<<"n(总共人数) = ";
    
        cin>>n;
    
        cout<<"d(出去人的编号) = ";
    
        cin>>d;
    
    	cout<<"s(第一次开始计数的位置) = ";
    
    	cin>>s;
    
        if(n <= 0 || d <= 0|| s<=0)
    
        {
    
           cout<<"Input Error\n";
    
            system("pause");
    
            return 0;
    
        }
    
        // 建立链表
    
        pHead = (RingNodePtr)malloc(sizeof(RingNode));
    
        pHead->pos = 1;
    
        pHead->next = NULL;
    
        CreateRing(pHead, n);
    
       // PrintRing(pHead);
    
        // 开始出圈
    
       cout<<"死亡顺序: ";
    
    	//更改下表头开始计数的位置
    
    	while(s--!=1)
    
    		pHead=pHead->next;
    
        KickFromRing(pHead,d);    
    
        cout<<"\n";
    
        system("pause");
    
        return 0;
    
    }