0%

1月18号创新班总结

今天是1月18号,也是放寒假的第一天。虽然有些不情愿,但是,学习信息学的热情是阻挡不了我的。

今天早上学习的呢,主要试一下几个方面:

一、选择插入排序

选择插入排序的思想主要是:有N个数,a1,a2..ai-1,ai,ai+1..an,那么,我们可以看成两个区域,一个是有序的,一个是无序的,[]<a1,a2..ai-1,ai,ai+1..an>([]是有序的,<>是无序的),那么,假设数列变成[a1,a2..ai-1],<ai,ai+2..an>,那么,要想让ai从无序区道有序区,需要在有序区找一个空位,那么,我们需要扫描一遍,当ap<ai<aq或ap>ai>aq时,ap,aq为所扫描空位的两边的数据,那么数据向后移一位,ai就从无序区到了有序区,如此类推……

源程序(借用老师)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int a[100], n;

int main()
{
cin >>n ;
for (int i=0; i<n; i++)
cin >> a[i];//读入
for (int i=0; i<n; i++)
{
int j,tmp;
tmp= a[i];//tem暂存ai值,因为在后面数据要后移
for (j=i; j!=0 && a[j-1]<tmp ; j--)//1.j!=0当j等于0是应退出,否则越界;2.a[j-1]<tmp从大到小,只要小于ai就继续
a[j]=a[j-1];//后移
a[j] = tmp;
}

for (int i=0; i<n; i++)
cout << a[i]<<" ";//输出
cout<<endl;
return 0;
}

二、函数与过程(子函数)

简单地说,子程序的格式是:类型 函数名 (类型+参数……);

当类型是int或double等非空类型的子程序就是函数,是可以返回一个数值的;二若是空类型时(void)是,并不返回,所以这就是过程。

其实,调用函数与过程,基本结构与pascal是一样的,但是,子程序定义头的格式有些不同。

PS:在c++里,子程序可以定义在主程序下方,而且,我们也习惯这么做,因为,我们西归先看主程序,看到有子程序名才会向下看,而不会马上就看子程序。

具体如下:

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
类型 函数名 (类型+参数……);
{
语句;
}

如:(1)函数
int fac(int k);
{
……

return tmp;
}

int main()
{
……
ans=fac(n);
……
}

(2)过程
void try(int x,y);
{
……
}

int main()
{
……
try(1,1);
……
}

三、递归

学习了子程序,我们知道了在主程序调用子程序,可以使程序实现模块化,但是,如果是在子程序里调用自己本身呢?

那么,这一种情况就叫做递归。我们可以用一道题来解释和应用。

我们知道,n!是指n的阶乘,既n!=1234…*n,那么,我们知道n,求n!

那么我们知道, n!=1234n,换句话说,n!= 1234n-1n=(1234n-1)n=(n-1)!n。现在我们很直观的看到,n!= (n-1)!*n。我们以5!为例,

∵5!=54!,4!=43!,3!=32!,2!=21!,1!=1

∴2!=21!=21=2,3!=32!=32=6,4!=43!=46=24,5!=54!=524=120

∴5!=120

这样实现起来非常简单,源程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

int fac(int k);

int main()
{
int n;
cin>>n;
cout<<fac(n)<<endl;
return 0;
}

int fac(int k)
{
if (k==1) return 1;//边界,1!=1
int tmp;
tmp=k*fac(k-1);//n!=(n-1)!*n
return tmp;
}

四、求下一个全排列

下一个全排列,也就是说,一个数列,如何移动,是使这个数列比它大但又和她的差最小。

比如说,(8,9,5,7,6,4,3,2,1,0),我们发现,只要将6放入5的位置,然后之后的数字从小到大排列,既(8,9,6,1,2,3,4,5,7)。因此,我们可以认为,只要扫描,从小到大数列后的第一个数字,在后面找到比它大但又差最小的数字放入这个数字的位置,然后包括原来的数字在内的后面数字从小到大排列,即可。

五、排队等水

有n个人打水,每个人有一定打水时间,问怎样排队使总等待时间最短。

我们知道,知道让等待时间从小到大排即可,但为什么呢?我们可以选择其中两个人,ap和aq,ap的等待时间小于aq的等待时间,若ap和aq调换,发现这并不是最优解,所以让等待时间从小到大排为最优解。

Thank you so much.