YTU数据结构作业三

d5cd8caa-c303-4201-8613-4fa5beedf8a9

1.约瑟夫环

题意解释&思路

围成一个圆圈，第 m 个拱出去，之后继续，直到最后剩下一个数字，求这个数字是几？

之前用数组模拟环，现在用链表模拟环，循环m-1次，从头拿出来看看，再放回尾部，到了第 m 次，扔掉不管了。一直等到链表只剩下一个的时候结束。

#include
using namespace std;
const int N=1e6+10;
int n,m;
int main()
{
	list<int> q;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		q.push_back(i);
	}
	int ret=0;
	while(1)
	{
		if(q.size()==1)break;
		for(int i=1;i<m;i++)
		{
			ret=q.front();
			q.pop_front();
			q.push_back(ret);
		}
		q.pop_front();
	}
	cout<<q.front();
	return 0;
}
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

2.火车出站

题意&思路

给你 n 辆车，按照栈的规则，求出出栈的序列有多少种？

相比来说是模拟题，更不如来说是数学推理题，根据计数原理的乘法原理可知，所有的情况为第一种可能的情况乘第二种可能的情况。
$$F(n)=F(0)\ast F(n-1)+F(1)\ast F(n-2)+F(2)\ast F(n-3)+\dots +F(n-1)\ast F(n-n);（其中n>=1，F(0)=1）$$

代码就比较简单了

3.查找最小的k个元素

略

4.括号匹配

题意&思路

遇到左括号分别给标记，遇到右括号看最后的标记的是否能匹配，不能则NO