约瑟夫环问题[已解决]
对约瑟夫环的递归方程的疑问。
能理解到重新编号这一点，但是相对的递推f(n) = (f(n - 1) + k) % n这点没有理解，感觉内在联系不是很明显。
=================================================================================
2015. 8. 13 更新：
起因是这道题目：[UVA 1394] And Then There Was One
f(1)代表的是最终剩下的那一个人的编号，毫无疑问，这个编号肯定是0。然后根据这个最终编号，由递推式反着进行求解，每次向上求解，得到这个编号在剩2个人中的编号是多少，接着是剩3个人时的编号是多少......一直递推到剩n个人时的编号。这个编号就是最初处理过的编号（即：以m位置作为0位置的编号）。然后重新解析一次，就能够得到正确答案了。
至于这个解析式：我个人觉得就是个找规律的过程，规律就是 (f(n - 1) + k)的时候要对n取模XD
【约瑟夫环问题[已解决]】
#include
using namespace std;
int main()
{
int n, k, m;
while (cin >> n >> k >> m && (n||k||m))
{
int last = 0;
for (int i = 2;
i < n;
++i)
{
last = (last + k) % i;
}
cout << (last + m) % n + 1 << '\n';
}
return 0;
}
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- jhipster|jhipster 升级无效问题
- 人生感悟记＃环境仪器宋庆国成长记＃072
- “精神病患者”的角度问题
- 爱琐搭配（喜欢复古、冷淡，像这种双环设计的气质耳环）
- 六步搭建ES6语法环境
- 解决SpringBoot引用别的模块无法注入的问题
- Hive常见问题汇总
- 姚老师互动问答会|姚老师互动问答会 # 问题001（如何更有智慧的和身边人分享金刚智慧（））
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题