约瑟夫环（递归） 中山职业技术学院 主讲：陈帼鸾 1
假设已知9人游戏，那个位置会赢，那我 是不是就能推出10人游戏赢的位置了？ 其实就是寻找（新位置）和（旧位置） 的关系 不难发现： 约瑟夫环 10人游戏 10人游戏 假设n=10人，报数m=3 假设已知9人游戏，那个位置会赢，那我 是不是就能推出10人游戏赢的位置了？ 1 0 1 2 3 4 5 6 7 8 9 2 第一轮结束后，序列变为 9 1 3 3 4 其实就是寻找（新位置）和（旧位置） 的关系 0 1 3 4 5 6 7 8 9 8 2 1 5 9人游戏 由于第二轮报数是从3开始，假设我们希望 永远都是0位置先报数，因此可以3为首，形成下方序列 不难发现： （（新位置）+m）%n=（旧位置） 6 3 4 5 6 7 8 9 0 1 3 7 旧位置 9 7 9人游戏 8 +3 ? 对应新位置 4 6 0 1 2 3 4 5 6 7 8 5 新位置
0 (n=1) f(n,m)= (f(n-1,m)+m)%n n>1 约瑟夫环 以n=5,m=3模拟 假设n=10人，报数m=3 int f(int n,int m) { int s; if(n==1) s=0; else s=(f(n-1,m)+m)%n; return s; } int main() int n,m; cin>>n>>m; cout<<f(n,m)<<endl; return 0; f(5,3) 3 4 5 6 7 8 9 0 1 旧位置 3 ( f(4,3) +3)%5 （新位置+m）%n 对应位置 0 1 2 3 4 5 6 7 8 f(4,3) 新位置 f(1,3)=0 ( f(3,3) +3)%4 得出递归表达式： ( f(1,3) +3)%2 0 (n=1) f(3,3) 1 f(n,m)= 1 f(2,3) (f(n-1,m)+m)%n n>1 ( f(2,3) +3)%3
将n阶的问题转化为比n阶小的问题，转化以后的问题与原来的问题的解法是相同的。 (2)寻找一个明确的递归结束条件，称为递归出口。 编写递归程序的关键 (1)构造递归表达式. 将n阶的问题转化为比n阶小的问题，转化以后的问题与原来的问题的解法是相同的。 (2)寻找一个明确的递归结束条件，称为递归出口。 约瑟夫问题 的递归出口是n=1。n从大越变越小，总会结束的。
约瑟夫问题的升级（作业） M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。给定m和最后一个出圈者的编号，求最小的N？ 约瑟夫环问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，从第一人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去直到所有人全部出列为止。试设计程序实现之。 扫一扫