约瑟夫环

发表于 更新于 分类于 ， 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

约瑟夫环：

N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。

本文介绍约瑟夫环的一些做法。

链表模拟该过程

使用环形链表，指针不断向后指，指到后将该节点删除。

时间复杂度\(\mathcal{O}(N)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N=110;
int l[N],r[N];
int n,m;

void link(int L,int R){
	l[R]=L;r[L]=R;
}

int main(){
	scanf("%d%d",&n,&m);	
	for(int i=1;i<n;i++)
		link(i,i+1);
	link(n,1);
	int p=n;
	while(n--){
		int t=m;
		while(t--) p=r[p];
		int L=l[p],R=r[p];
		link(L,R); 
		cout << p << " ";
	}
	return 0;
}

优化：动态规划

设\(f(N,M)\)的值即为答案，那么有如下递推公式： \[ f(N,M)=(f(N−1,M)+M) \% N \] 从N-1到N多了一个人，带来的影响是报数多报了M次

Note( Bootstrap Callout )

设置

使用 Usage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
```



{% codeblock 创建note lang:html [additional options] %}
{% note [class] [no-icon] [summary] %}
Any content (support inline tags too).
{% endnote %}
{% endcodeblock %}



{% note info no-icon This is a summary %}
Any content (support inline tags too).
{% endnote %}





## 代码块 Code Block

```html
{% codeblock [title] [lang:language] [url] [link text] [additional options] %}
code snippet
{% endcodeblock %}