约瑟夫环问题

2020-07-08

算法

字数统计: 180 | 阅读时长≈ 1 分钟

约瑟夫环问题都很熟悉了，这里也就不多赘述了。

主要是来记录一下，约瑟夫环的一些解法。

这里我就不详细写推理的过程了。。（其实我也不会。。

网上应该一搜一大片。

1、迭代

int cir(int n,int m)
{
	int p=0;
	for(int i=2;i<=n;i++)
	{
		p=(p+m)%i;
	}
	return p+1;
}

2、公式

我不知道这个公式是哪个鬼才想出来的。。

我在网上都没有找到。

int S(int n)
{
    if(n==1)
      return 1;
    else if(n&1)	return S((n-1)/2)*2+1;
    else	return S(n/2)*2-1;
}

用这个可以过掉1e9的题。。

上面那个会TLE。