华为招聘机试整理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();笔误写成==了。