首页 > 技术文章 > 每天一道算法题(23)——约瑟夫环问题

engineerLF 2015-07-16 14:43 原文

题目:

        已知n个人(以编号0,1,2...n-1分别表示)围坐在一张圆桌周围。从编号为0的人开始报数1,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。问最后的剩下的人。


思路:

    1.直接使用list模拟约瑟夫环。删除节点

    2.第二,分析之。对于n个数而言,剩下的人是f(n,m)=(f(n-1,m)+m)%n;其中n=1时,f(1,m)=0。


代码

    方法1:

 int josephuse(const int &n,const int &m){
	 if(n<1||m<1)
		 return -1;

	 list<int> number;
	 for(int i=0;i<n;i++)
		 number.push_back(i);

	 list<int>::iterator iter=number.begin();
	 list<int>::iterator next;
	 while(number.size()>1){
		 for(int j=1;j<m;j++){
			 iter++;
			 if(iter==number.end())
				 iter=number.begin();
		 }
		 next= ++iter;
		 if(next==number.end())
				 next=number.begin();
		 
		 iter--;
		 number.erase(iter);
		 iter=next;
	 }

	 return *iter;
 }

    方法2:

 int josephuse(const int &n,const int &m){
	 if(n<1||m<1)
		 return -1;
     int last=0;
	 for(int i=2;i<=n;i++)
		 last=(last+m)%i;

	 return last;
 }






推荐阅读