约瑟夫环算法

 1 <?php
 2 /**
 3 约瑟夫环：递归算法
 4 假设下标从0开始，0，1，2 .. m-1共m个人，从1开始报数，报到k则此人从环出退出，问最后剩下的一个人的编号是多少？
 5 现在假设m=10
 6 0 1 2 3  4 5 6 7 8 9    k=3
 7 
 8 第一个人出列后的序列为：出列人：2
 9 0 1 3 4 5 6 7 8 9
10 即:
11 3 4 5 6 7 8 9 0 1（*）
12 我们把该式转化为:
13 0 1 2 3 4 5 6 7 8 (**)
14 则你会发现: （(**)+3）%10则转化为(*)式了
15 
16 第二个出列人2，其实就是转化前的（2+3）%10=5;
17 
18 也就是说，我们求出9个人中第1次出环的编号，最后进行上面的转换就能得到10个人第2次出环的编号了
19 10个人第三次出环的编号，其实就是9个人第二次出还的编号，也就是8个人第一次出环的编号
20 依次类推，每次出环的编号都是2，即 （m+k-1）%m；其实也就是未转化前的（2+k）%m；
21 设f(m,k,i)为m个人的环，报数为k，第i个人出环的编号，则f(10,3,10)是我们要的结果
22 当i=1时，  f(m,k,i) = (m+k-1)%m
23 当i!=1时，  f(m,k,i)= ( f(m-1,k,i-1)+k )%m
24 */
25 function josephus($m,$k,$i){
26     if (1==$i){
27         return ($m+$k-1)%$m;
28     }else{
29         return (josephus($m-1,$k,$i-1)+$k)%$m;
30     }
31 }
32 for($i=1;$i<11;$i++){
33     echo "10个人第 $i 次出环的是".josephus(10,3,$i).'号</br>';
34 }