首页 > 代码库 > 约瑟夫环问题
约瑟夫环问题
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌剩下最后一个人，求这个人的编号。
这是一个经典的算法题，拿到手上，先想到的是模拟报数过程，实现如下（是在cocos2dx环境下，代码中的ccarray可以换成c数组）：
int josephus(int n, int m, int k){ CCArray *array = CCArray::create(); for (int i = 0; i < n; i ++) { array->addObject(CXNumber::create(i + 1)); } int index = k - 1; while (true) { for (int i = 0; i < m; i ++) { if (array->count() == 1) { return ((CXNumber *) array->objectAtIndex(0))->getIntValue(); } if (i == m - 1) { bool changeIndex = (index == array->count() - 1); array->removeObjectAtIndex(index); if (changeIndex) { index = 0; } } else { index ++; if (index == array->count()) { index = 0; } } } }}
后来网上搜了一下，看到一个 http://blog.csdn.net/dengyaolongacmblog/article/details/39208675 的实现，恍然大悟，又写了个基于数学归纳的实现，复杂度大大降低，从O(m^n)到O(n), 实现如下：
int anotherJosephus(int n, int m, int k){ CCArray *array = CCArray::create(); for (int i = 0; i < n; i ++) { array->addObject(CXNumber::create(i + 1)); } int index = k - 1; for (int i = 0; i < n - 1; i ++) { index = (index + m) % array->count(); //数学归纳得出要被淘汰的index index --; if (index < 0) { index = array->count() - 1; } array->removeObjectAtIndex(index); } return ((CXNumber *) array->objectAtIndex(0))->getIntValue();}
以上两种代码，都已测试过
如有问题，欢迎指正
约瑟夫环问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。