约瑟夫环问题,一段代码求讲解

六月不远 发布于 2013/08/23 11:15
阅读 306
收藏 0

小弟今天看到递归问题中的约瑟夫环时看到了一段代码,不太理解,求解一下。谢谢各位~~

#include <stdio.h>
unsigned flp2(unsigned x) {
  x |= x >>  1;
  x |= x >>  2;
  x |= x >>  4;
  x |= x >>  8;
  x |= x >> 16;
  return x - (x >> 1);
}
int main()
{
  unsigned x;
  printf("Please input the number of people in Josephus Circle: ");
  scanf("%d", &x);
  printf("The ONLY safe position is: %d\n", (x - flp2(x) << 1) + 1);
  return 0;
}


加载中
0
我不说话
我不说话
数学问题,位移方法
六月不远
六月不远
回复 @我不说话 : 恩恩,还是不理解怎么算出来~记得约瑟夫环好像可以和循环移位联系起来
我不说话
我不说话
回复 @六月不远 : 我也是小白,以前用自己的思路写过。比较牛逼的思路,我觉着是用数学归纳法总结的公式。
六月不远
六月不远
能具体点解释吗?比较小白
0
我不说话
我不说话
这是最简洁的java代码
public static int king(int M, int N) {
    // 总人数 M ,数到第 N 个排除。
    int k = 0;
    for (int i = 2; i <= M; i++){
        k = (k + N) % i;
    }
    return ++k;
}
0
中山野鬼
中山野鬼

引用来自“我不说话”的答案

这是最简洁的java代码
public static int king(int M, int N) {
    // 总人数 M ,数到第 N 个排除。
    int k = 0;
    for (int i = 2; i <= M; i++){
        k = (k + N) % i;
    }
    return ++k;
}
楼主的代码如果我没理解错,是针对k = 2的,你的是针对 任意 k的。我刚才瞄了一眼,也没有看出头绪。哈。以前没做过这方面的优化。这需要点时间理解。
六月不远
六月不远
嗯嗯,我贴的这段代码是针对K=2的~
返回顶部
顶部