0%

1月18号创新班总结2

1月24号的课程,我请假了半天,但是没有关系,因为老师为我们留下了视频,我们可以看视频回顾,即可以复习又可以留念,一举两得。而且,我还需要加倍地学习,我不能辜负老师对我们的期望。下面是今天学习的几个知识:

一:关于全排列的几个问题

还是那一个问题,求下一个全排列。

我们从两个例子可以发现,我们要的到下一个全排列,我们要做到以下几个步骤:

  1. 从左向右扫描,找到一个向上的序列,因为我们所需的那一个数列是要比他大的,若是从大到小,只要大的和小的交换即可,所以不妥。这样就可以找到需要改变的哪一个数位。如1,{5,4}就是我们找到的向上的数列;

  2. 找到这一个上升的数列突然下降的哪一个数,与哪一个向上的数列的最右端的那一个数进行交换,然后整一个数列(由于数字交换了,也许不是上升的了)进行排序即可。如1,{5,4}的突然下降的数字是3,而数列的右端是4,交换,数列排序,变成{2,1,4,3,5}。

源程序如下(借用老师):

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
58
59
60
#include <iostream>
#include <algorithm>
using namespace std;

int a[1001],n;
void read();
void write();
void work();
int find_p();
int find_q( int x);

int main()//要习惯在主程序前先写子程序名
{
read();
// work();
// write();
next_permutation(a+0, a+n);
write();
return 0;
}

void work()
{
int p=find_p();//找到向上的数列后突然向下的那一个数
int q=find_q(a[p]);//找到与p进行交换的数

//cout <<p <<" "<<q<<endl;//这是用来调试的办法,我们可以尝试这样输出来在c++调试

swap(a[p],a[q]);
for (p++,q=n-1; p<q ; ++p, --q)
swap(a[p],a[q]);//进行交换
}

int find_p()
{
int i=n-1;
for (; i>0 && a[i]<a[i-1] ; i--);
if (i==0) { cout<<"ERROR!"; exit(0); }
return i-1;
}

int find_q(int x)
{
int i=n-1;
for (; a[i]<x ; i--);
return i;
}

void read()
{
cin >>n;
for (int i=0; i!=n; ++i) cin>> a[i];
}

void write()
{
for (int i=0; i!=n; ++i)
cout << a[i]<<" ";
cout<<endl;
}

还有一个问题,给定一个全排列求第几个。

该怎么办呢?比如说{2,4,3,1},一个个数下来,是第11个。但是,如果是更大的数,就不可以一个个数了,那该怎么办呢?

我们知道,全排列为n的数目一共有n!个。比如4,就有4!=24个。那么,开头为1的数列有6=(4-1)!=3!,2有6个,3有6个,4也有6个。而且,开头为1,第二位为1有2=(4-2)!=2!,2有2个,3有2个,4也有2个。

因此,对于一个全排列n,我们可以确定第一位的数字,然后ans+=(n-i)!*k,ans是累加答案,i是第几位,k是指数字的前几位,我们可以用布尔数组f来储存什么数字有什么数字没有,再看看a[i]这个数字在f中非真的排列位置,即为k。

二:浅谈分治

简单来说,就是要解决一个大问题,我们可以把这几个问题分解成几个小问题,按如此规律解决,最终解决大问题。

比如说快排,就是分治法。

快排的思想,就是说:有那么一个数列去中间数mid,然后使min左边的数都小于min,右边的数都大于min,然后,我们再将{1-min}{min+1-n}这么做即可。那么,我们可以发现左边的数都小于右边的数,也就排好了序。

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
#include <iostream>
//#include <alrigothm>
using namespace std;

int a[1000000],n,x,y;
void read();
void write();
void qqsort(int l,int r);

int main()
{
read();
qqsort(0,n-1);
write();
return 0;
}

void read()
{
cin >>n;
for (int i=0; i!=n; ++i) cin>> a[i];
}

void write()
{
for (int i=0; i!=n; ++i)
cout << a[i]<<" ";
cout<<endl;
}

void qqsort(int l, int r)
{
if (l>=r) return;
int mid=a[(l+r)/2];//找中间点mid
int i=l,j=r;
for ( ;i<=j;i++,j--)//每次i加1,j减1
{
for ( ;a[i]<mid;i++);//找到比他小的

for ( ;a[j]>mid;j--);//找到比他大的的

if (i<=j) swap(a[i],a[j]);//交换
}

qqsort(l,j); qqsort(i,r);
}

三:自顶向下编程工程

自顶向下就是指先写结构再写细节。比如说,我们编程时,压板都是先写子程序的名称再写主程序的内容,在主程序里调用子程序写名,最后编写子程序。主程序是结构,子程序是细节。所以这就是自顶向下的编程工程方法。

四:学习方法

老师向我们讲了一个学生的例子,他尽管不怎么喜欢做作业,但是,他认为作业太简单了。其次,他还有一个习惯,就是他很喜欢做笔记,记录在信息学的点点滴滴。因此,也就造就了这一个“世界第一”。因此,我要向他好好学习。

Thank you so much.