CSP算法和数据结构一本通NOIP信息学奥赛C++编程培训PPT习题源码

信息学奥赛一本通

1、算法部分 习题源码

2、数据结构习题源码

3、授课PPT课件

4、编程及评测软件

5、必掌握知识汇总

6、第五版扫描PDF

主目录清单

1. 算法部分 习题源码

2. 数据结构 习题源码

3. 教程ppt课件(第五版)

4. 编程及评测软件

5. 必学知识pdf文档

第1章 高精度计算

第2章 数据排序

第3章 递推算法

第4章 递归算法

第5章 搜索与回溯算法

第6章 贪心算法

第7章 分治算法

第8章 广度优先搜索

第9章 动态规划

1.走楼梯

2.兔子繁殖

3.平面分割

4.骨牌铺法

5.虫食算

6.极值问题

7.火车站(NOIP1998)

例3.1 数的划分

例3.4 昆虫繁殖

例3.5 位数问题

例3.6 过河卒(NOIP2002)

例3.7 饥饿的牛

第1章 栈

第2章 队列

第3章 树

第4章 图论算法

1. 表达式括号匹配

2. 括弧匹配检验

3. 符号串匹配问题

4. 计算

5. 车厝调度

6. 中缀表达式值

例2-4 细胞

例2-5 最少步数

1. 选择排序

(1)基本思想: 每一轮从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在待排序的数据序列的最前, 直到全部待排序的数据元素排序完。

(2)排序过程:

【示例】:

初始关键字[49 38 65 97 76 13 27 49]

第一轮排序后 13 [38 65 97 76 49 27 49]

第二轮排序后 13 27 [65 97 76 49 38 49]

第三轮排序后 13 27 38 [97 76 49 65 49]

第四轮排序后 13 27 38 49 [76 49 65 97]

第五轮排序后 13 27 38 49 49 [97 65 76]

第六轮排序后 13 27 38 49 49 65 [97 76]

第七轮排序后 13 27 38 49 49 65 76 [97]

最后排序结果 13 27 38 49 49 65 76 97

—

# include

using namespace std;

const int MAXN=10001;

int main()

{

int n,k,i,j;

float temp,a[MAXN];

cin>>n;

for (i=0;i<n;i++)

cin>>a[i]; //输入n个数

for (i=0;i<n;i++)

{

k=i;

for (j=i+1;j<n;j++) //在当前无序区a[i..n]中选最小的元素a[k]

if (a[j]<a[k]) k=j;

if (k!=i)

{

temp=a[i];a[i]=a[k];a[k]=temp;

//交换a[i]和a[k], 将当前最小值放到a[i]位置

}

for (i=0;i<n;i++)

cout<<a[i]<<", ";

return 0;

}

—

第一轮排序: 5 3 4 1 2 6

3 5 4 1 2 6

3 4 5 1 2 6

3 4 1 5 2 6

3 4 1 2 5 6

第二轮结束, 5固定下来

第三轮排序: 3 4 1 2 5 6

3 1 4 2 5 6

3 1 2 4 5 6

第三轮结束, 4固定下来

第四轮排序: 1 2 3 4 5 6

1 2 3 4 5 6

第四轮结束, 3固定下来

第五轮排序: 1 2 3 4 5 6

1 2 3 4 5 6

第五轮结束, 2固定下来

五轮结束后, 6个整数就已经排序完成。排序过程中, 大数慢慢的往后, 相当于气泡上升, 所以叫冒泡排序。

—

归纳上述排序过程, 具体实现步骤如下:

①读入数据存放在a数组中。

②比较相邻的前后两个数据, 如果前面数据大于后面的数据, 就将两个数据交换。

③对数组的第0个数据到n-1个数据进行一次历遍后, 最大的一个数据就“冒”到数组第n-1个位置。

④n=n-1, 如果n不为0就重复前面二步, 否则排序完成。

程序实现方法: 用两层循环完成算法, 外层循环i控制每轮要进行多少次的比较, 第1轮比较n-1次, 第2轮比较n-2次, ……, 最后一轮比较1次。内层循环j控制每轮i次比较相邻两个元素是否道序, 若道序就交换这两个元素

PPT课件预览：