0%

3.2创新班总结

一:约瑟夫问题

约瑟夫问题,简单来说,就是有N个人,从一号开始,1,2,…,m,1,2,…,m,每报号m的人就被淘汰,那么,最后的那个人是谁呢?

我们可以建立一个数组,标记每一个人连接的下一个是谁。然后不断循环,一旦数到m时,这个人的前一个就连到这个人的后一个,直到这个人连接的是自己,那么,我们就知道了最后剩下的那个人是谁了。

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
27
28
29
30
31
32
33
#include <fstream>
using namespace std;

ifstream fin("约瑟夫问题.in");
ofstream fout("约瑟夫问题.out");

void read();
void write();
void work();

int n,m,p;
int a[100000];

int main()
{
fin>>n>>m;
for(int i=1;i<=n;i++) a[i]=i+1;
a[n]=1;
p=n;
work();
return 0;
}

void work()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++) p=a[p];
if(i==n) fout<<"real ans:";
fout<<a[p]<<endl;
a[p]=a[a[p]];
}
}

二:归并排序

归并排序,就是“归”和“并”。我们将这一个无序数组不断二分,然后将这二分后的有序数组段两两合并。

二分,就是不断递归,但如何合并呢?假设[1,3,5,8]和[2,4,6,7]进行合并。我们先看[1]和[2],明显[1]更小,然后我们再看[3]和[2],明显[2]更小,[3]和[4]比较,[4]小些……以此类推。最后,我们可以得出[1,2,3,4,5,6,7,8]。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;

void mergesort(int l,int r);
void merge(int l,int r,int mid);
void swap(int &x,int &y);

int t;
int a[10000005],b[10000005];

int main()
{
cin>>a[0];
for(int i=1;i<=a[0];i++) cin>>a[i];

mergesort(1,a[0]);

for(int i=1;i<=a[0];i++) cout<<a[i]<<" ";
system("pause");
return 0;
}

void merge(int l,int r,int mid)
{
int i=l,j=mid+1,p=l;
for(;p<=r;p++)
{
if((i<=mid)&&((j>r)||(a[i]>a[j])))
{
b[p]=a[i];
i++;
}
else
{
b[p]=a[j];
j++;
}
}

for(int k=l;k<=r;k++)
{
a[k]=b[k];
b[k]=0;
}
}

void mergesort(int l,int r)
{
int mid;
if(r!=l)
{
mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
merge(l,r,mid);
}
}

三:宽度搜索

宽度搜索,其实还有一个名称,叫做“灌水法”。其实在此,我们要引出一个叫队列的数据类型。队列犹如一个数组,先进那么就现出,后进就后出。假设有一个点a1,它连接b1,b2,那么我们就让b1,b2进队列,然后让b1出列,b1连接着c1,c2,那么c1,c2入队列。此时队列为b2,c1,c2。b2出列,b2连接c3,c4,那么让c3,c4入队列,以此类推……

四:拓扑排序

图,也是一个数据类型,有许多点,每个点之间都有连线。没有方向的叫做无向图,而有方向的就是有向图。

那么,对于一个有向图,我们可不可以对每一个点进行排序呢?其实这叫做拓扑排序。对于每一个点来说,有几条线连着它,就说它有几个度。那么,几条线指着它,就有几个入度;射出几条线条,就有几个出度。每一个入度为零的,就排在前面,然后撤去射出线条,在判断,放在后面,以此类推……

Thank you so much.