华为招聘机试整理15：约瑟夫环

liyao20060101

华为招聘机试整理15：约瑟夫环
　　
题目：约瑟夫环

约瑟夫环是一个数学的应用问题：已知n个人（以编号1。2。3...n分别表示）围坐在一张圆桌周围。从编号为k的人開始报数，数到m的那个人出列；他的下一个人又从1開始报数，数到m的那个人又出列；依此规律反复下去。直到圆桌周围的人所有出列。

题目分析：

这道题主要是想考察链表的知识。

算法思路一：用环形链表模拟圆圈

我们这里採用模板库中的std::list来模拟一个环形链表，因为std::list本身不是一个环形结构，所以我们每次迭代器iterator扫描到链表末尾的时候，我们要记得把迭代器移到链表的头部。这样就相当于依照顺序在一个圆圈中遍历了。
　　

算法思路二：利用观察数学规律分析剩下数字的规律还循环或者递归
　　
=========================================================================

參考代码:

//约瑟夫环.cpp
//2014.7.11 hepanhui
#include <iostream>
#include <list>
using namespace std;
/*算法思路1：
int Josephus(unsigned int n,unsigned int m)
{
if(n < 1 || m < 1)
return -1;
unsigned int i = 0;
list<int> numbers;
//初始化链表
for(i = 0; i < n; i++)
numbers.push_back(i);
list<int>::iterator current = numbers.begin();
while(numbers.size() > 1)
{
for(i = 1; i < m; ++i)
{
current++;
if(current == numbers.end())
current = numbers.begin();
}
list<int>::iterator next = ++current;
if(next == numbers.end())
next = numbers.begin();
current--;
cout << *(current) << endl;
numbers.erase(current);
current = next;
}
return *(current);
}  */
int Josephus(unsigned int n, unsigned 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;
}
int main()
{
unsigned int n,m;
cin >> n >> m;
cout << Josephus(n,m) << endl;
return 0;
}

　　
调试中易犯的错误：

思路一的代码还有点问题，提示list iterator not incrementable错误。
　　找到错误了，
current = numbers.begin();笔误写成==了。