0%

3.19创新班总结

今天,我们学习了很多内容,虽然有些辛苦,但是我们会坚持不懈的。这次我们学习了动态数组(向量)、栈等。

一:动态数组(vector)

其实,vector就是向量的意思,但是,这不是数学和物理学中的向量,局势是什么意思,我也不同,但它的用处可大了。简单来说,就是需要多大空间就开多大空间,是动态的。

① 头文件:#include

② 定义:vector 数组名

③ 返回最后一个数据元素的值 v.back()

④ 清空向量中的数据 v.clear()

⑤ 判断向量是否为空,空则返回 1 v.empty()

⑥ 返回第一个数据元素的值 v.front()

⑦ 删除最后一个数据元素 v.pop_back()

⑧ 将参数作为数据元素插入到向量末尾 v.push_back(对应类型的数据)

⑨ 返回向量中数据元素个数 v.size()

⑩ 与另一个向量作交换 v.swap()

具体程序将与“栈”知识点结合。

二:栈

栈是一种数据结构,与队列不同,队列是先进先出,而栈是先进后出,递归正是运用栈来实现的。

括号匹配,就是判断一组括号是否合法。基本思路就是:看到左括号就进栈,看到右括号就判断一下,若是与栈顶的左括号相匹配,就出栈,否则就只接输出不合格。这样,与动态数组正好可以无缝结合。

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
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("括号匹配.in");
ofstream fout("括号匹配.out");

void read();
void write();

vector <char> f;
int l[128];
string s;
bool yes;

int main()
{
read();
yes=true;
f.push_back('#');
l['(']=1; l[')']=1;
l['[']=2; l[']']=2;
l['{']=3; l['}']=3;
l['<']=4; l['>']=4;//这样就可以转换成数值之间比较,无需一种一种括号比较

for (int i=0; i!=s.size(); ++i)
{
if ((s[i]=='(') || (s[i]=='[') || (s[i]=='{') || (s[i]=='<'))
f.push_back(s[i]);
else
if (l[s[i]]==l[f.back()]) f.pop_back();
else
{
yes=false;
break;
}
}

write();
return 0;
}

void read()
{
fin>>s;
}

void write()
{
if ((yes) && (f.back()=='#'))
fout<<"Yes!"<<'\n';
else
fout<<"No!"<<'\n';
}

顺便在次附上“运算表达式”的程序(之前编的pas,还未来得及转cpp,以后,再会附上cpp)

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
const
ed=5;

var
s,s1:string;
st:array[0..10000] of real;
st2:array[0..10000] of char;
l:array['!'..'/'] of longint;
top1,top2,len,i,j,code:longint;

procedure calc;
var
a,b,c:real;
ch:char;

begin
a:=st[top1]; dec(top1);
b:=st[top1]; dec(top1);
ch:=st2[top2-1]; st2[top2-1]:=st2[top2]; dec(top2);

case ch of
'+':c:=b+a;
'-':c:=b-a;
'*':c:=b*a;
'/':c:=b/a;
end;

inc(top1); st[top1]:=c;
end;

procedure main;
begin
top1:=0; top2:=0;
fillchar(st,sizeof(st),0);
fillchar(st2,sizeof(st2),' ');
s:='';

readln(s);
len:=length(s);
l['+']:=2; l['-']:=2;
l['*']:=1; l['/']:=1;
l['(']:=3;

i:=1;
while i<=len do
begin
if (s[i] in ['0'..'9']) or (s[i]='.') then
begin
j:=i+1; s1:=s[i];
while ((s[j] in ['0'..'9']) or (s[j]='.')) and (j<=len) do
begin
s1:=s1+s[j];
inc(j);
end;

i:=j-1;
inc(top1);
val(s1,st[top1],code);
end;

if (s[i]='+') or (s[i]='-') or (s[i]='*') or (s[i]='/') then
begin
inc(top2);
st2[top2]:=s[i];
while (top2>1) and (l[st2[top2]]>=l[st2[top2-1]]) do calc;
end;

if (s[i]='(') and (s[i-1] in ['0'..'9']) then
begin
inc(top2);
st2[top2]:='*';
while (top2>1) and (l[st2[top2]]>=l[st2[top2-1]]) do calc;
end;

if s[i]='(' then
begin
inc(top2);
st2[top2]:=s[i];
end;

if s[i]=')' then
begin
inc(top2);
st2[top2]:=s[i];
while (top2>1) and (st2[top2-1]<>'(') do calc;
dec(top2,2);
end;

inc(i);
end;

inc(top2);
st2[top2]:=')';

while (top2>1) do calc;

writeln(st[top1]:0:ed)
end;

BEGIN
writeln('Calc Module Over!');
writeln('ed=',ed);

while 1=1 do
begin
write('Please input:');
main;
writeln('Over! Next!');
end;
END.

三:递归的记忆化

在递归过程中,经常会出现超时,超空间的情况。我们发现,假设是int f(int x)的函数,x经常会出现多次,那么,我们就可以用一个数组储存每一次,计算过x后的f(x)的值。这样,我们就可以大大的减少时间复杂度。

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
#include <fstream>
using namespace std;

ifstream fin("递归记忆化.in");
ofstream fout("递归记忆化.out");

long long fac(int k);
int n;
long long a[1002];

int main()
{
fin>>n;

fout<<fac(n)<<endl;
return 0;
}

long long fac(int k)
{
long long ans;
if(k==0||k==1) return 1;
if(a[k]!=0) return a[k];//记忆化过程①
else ans=fac(k-1)+fac(k-2);
a[k]=ans; //记忆化过程②
return ans;
}

四:二叉树

二叉树,就是一个根结点,连接两个结点,分别是左结点和右结点,一次类推,形成一个全新的数据结构。

二叉树还有几个特点,就是:

① 有n个点,就有n-1条边

② 绝对无环

③ 绝对连通

④ 最多有2n-1(n层)

再次,不得不提的是,二叉树的左序遍历,中序遍历,后序遍历。

① 左序遍历,就是先遍历左子树,遍历根,再遍历右子树,一次递归下去。

② 中序遍历,就是先遍历根,遍历左子树,再遍历右子树,一次递归下去。

③ 右序遍历,就是先遍历右子树,遍历根,再遍历左子树,一次递归下去。

五:卡特兰数

卡特兰数,就是 ,再许多问题上都很有用。

六:错排问题

题目如下:有n个信封,n封信,如果这些信封全都装错,那么一共会有多少种情况?

```c++
#include
using namespace std;

ifstream fin(“错牌问题.in”);
ofstream fout(“错牌问题.out”);

void read();
void write();

long long f[1000];
int n;

int main()
{
read();

f[0]=0; f[1]=1;
for (int i=2; i!=n; ++i) f[i]=i*(f[i-1]+f[i-2]);

write();
return 0;

}

void read()
{
fin>>n;
}

void write()
{
for (int i=0; i!=n; ++i) fout<<f[i]<<” “;
fout<<’\n’;
}

Thank you so much.