iOS算法系列（一）- 约瑟夫环

前言

在开始正题之前要感叹一句：一定要好好学算法，虽然就封装的角度来说，完全可以把前人的算法封装成工具类或分类直接拿来用，但是我们还是很有必要明白其中的原委。不做敲代码的程序猿，只做有灵魂的攻城狮！

废话不多说，开始正题！

约瑟夫环

问题描述：有m个人,围成一个环，编号为 0、1、2、3、、、m-1，从第k个人开始循环报数，假设数到n的那个人出列，然后从下一个人继续数数，数到n出列，以此循环，按顺序输出所有被选出人的编号。

分析如下：
设m为人的个数，n为要数的数，k为从第几个人开始数
首先定义一个存储m个人的数组array，方便遍历时输出
设index为选中人的编号，假设从第一个人开始数那index = -1（因为数组的编号是从0开始的），那么从第k个人开始index = -1+(k-1)
那么数到第n个人的编号就是index = (index+n)%array.count（解释：如果index+n<array.count，那么(index+n)%array.count=index+n，也就是1%2=1，如果还不懂请重温计算机原理）
然后将对应index的元素移除，index--回到上一位重新开始数，当array.count==0时循环结束

直接上代码：

/**
 *  约瑟夫环
 *  @param m  总人数
 *  @param n  报数的长度
 *  @param k  开始位置
 */
- (void)josephCircle:(NSInteger)m length:(NSInteger)n index:(NSInteger)k {
    // 定义一个数组存放m个人
    NSMutableArray *array = [NSMutableArray array];
    for (int i=0; i<n; i++) {
        [array addObject:@(i+1)];
    }
    // 设置index为开始数数的位置
    NSInteger index = -1+(k-1);
    // 当array大于0一直循环
    while (array.count>0) {
        // 取到数到n个人的index
        index = (index+n)%array.count;
        // 打印对应index的编号
        NSLog(@"%zd",[array[index] integerValue]);
        // 将对应index移除
        [array removeObjectAtIndex:index--];
    }
}