NOIP实用算法中国计算机学会编.docx
- 文档编号:17900953
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:66
- 大小:51.56KB
NOIP实用算法中国计算机学会编.docx
《NOIP实用算法中国计算机学会编.docx》由会员分享,可在线阅读,更多相关《NOIP实用算法中国计算机学会编.docx(66页珍藏版)》请在冰点文库上搜索。
NOIP实用算法中国计算机学会编
2017-2018NOIP实用算法
中国计算机学会2017
1.模拟方法..........................................................................................................................................................3
a.用数学量和图形描述问题........................................................................................................................3
b.模拟计算过程..........................................................................................................................................3
c.模拟时的优化..........................................................................................................................................3
d.高精度计算算法......................................................................................................................................4
习题...............................................................................................................................................................5
2.排序算法与算法时空复杂度...........................................................................................................................6
a.简单排序算法..........................................................................................................................................6
b.快速排序、堆排序..................................................................................................................................6
c.算法时空复杂度......................................................................................................................................7
d.时空的简单优化方法...............................................................................................................................8
e.线性时间排序..........................................................................................................................................8
f.归并排序..................................................................................................................................................9
g.合理选用排序算法..................................................................................................................................9
习题...............................................................................................................................................................9
3.搜索................................................................................................................................................................10
a.复杂的模拟问题与利用相似性..............................................................................................................10
b.函数的递归调用....................................................................................................................................10
c.栈与深度优先搜索.................................................................................................................................11
d.深度优先搜索的优化.............................................................................................................................12
e.队列与广度优先搜索.............................................................................................................................12
f.广度优先搜索的优化.............................................................................................................................12
习题.............................................................................................................................................................13
4.贪心方法........................................................................................................................................................14
a.工程计划模型........................................................................................................................................14
b.部分背包与每步最优.............................................................................................................................14
c.构造贪心算法........................................................................................................................................15
习题.............................................................................................................................................................15
5.动态规划........................................................................................................................................................16
a.另一种形式的工程计划..........................................................................................................................16
b.记忆化搜索............................................................................................................................................16
c.数字三角形:
递推地思考问题..............................................................................................................17
d.石子合并:
状态的确定..........................................................................................................................17
e.街道问题:
状态量维数的确定与无后效性..........................................................................................18
f.0-1背包:
巧妙地选取状态量.............................................................................................................19
g.Bitonic旅行:
最佳的状态转化方式................................................................................................20
h.最长非降子序列模型.............................................................................................................................20
i.构造动态规划算法................................................................................................................................21
j.动态规划、递推、广度优先搜索的区别与转化..................................................................................21
习题.............................................................................................................................................................21
6.常用数学方法................................................................................................................................................22
2
a.排列组合................................................................................................................................................22
b.递推与通项的选用................................................................................................................................23
7.分治................................................................................................................................................................26
a.子问题与母问题的相似性......................................................................................................................26
b.二分查找................................................................................................................................................26
c.分析算式................................................................................................................................................26
d.最长非降子序列的二分法......................................................................................................................29
8.图论思想........................................................................................................................................................30
a.图论基础................................................................................................................................................30
b.图的表示方法........................................................................................................................................30
c.经典图论算法........................................................................................................................................30
d.构造图论模型........................................................................................................................................32
习题.............................................................................................................................................................33
附件:
关键路径算法、篝火晚会问题解法源文件...................................................................................33
3
1.模拟方法
a.用数学量和图形描述问题
计算机处理的是数学量。
若要用计算机解决实际问题,需要把实际问题抽象为数学量,或者数字。
比如,
记事本把文字按ASCII码表转换为数字储存起来,极品飞车把赛车的性能表示为数字,来权衡赛车的
好坏。
一个漂亮的算法,需要用数学量表示出来。
任务:
现有两个软件工程的制作任务,你的团队可以接手其中任意一个。
现要在两个中选择一个,需要
考虑制作成本,制作成功的可能性,可获得经济收益的多少,对你的团队知名度的影响等等因素。
你
如何量化地分析和解决这个问题?
提示:
需要把每一项都转化为数值,必要时加入权值、计算期望。
如果只考虑以上四个因素,可以得到
以下数学式
综合收益=制作成功的概率*[(可获得经济收益-制作成本)*经济效益的权值+团队知名度的影响*社会
效益的权值]
其中概率和两个权值是需要估计的值。
有时,我们需要用更直观的图形来描述实际问题。
图论就是一个绝佳的方法。
图是一种表示离散量间关系的形式,它也是一种思想,常被用于建模。
同时,
前人也为我们提供了很多现成的图论算法,能够解决很多常见问题,这些将在之后被提到。
矩阵也是一种常见的方法。
有时矩阵被表示成三角形的形式,比如“杨辉三角”。
矩阵常常和数学有关,
在计算机计算时常常利用矩阵的递推式。
这也将在后面被提到。
b.模拟计算过程
模拟方法是最常见、最直接的算法构建方法。
任务:
编程实现欧几里得算法(辗转相除法,求两个数的最大公约数gcd(a,b))
提示:
欧几里得算法原理:
gcd(a,b)=gcd(b,amodb)
欧几里得算法的图形描述——
|16863||16863|2
|42|
1.写下两个数2.将两数相除,余数写在较大的数下面
|16863|2|16863|2
1|4221|1|4221|2——整除
3.将每列最下面的数相除,余数写在被除数下面4.重复步骤3直至整除,此时最后写下的余数即为
开始时两数的最大公约数
这是一个简单的模拟算法,实际过程中,量间的关系往往比这复杂得多,因而,模拟算法可以是很复杂
的。
有些模拟算法还涉及到图形和其他复杂的数据结构,这需要我们熟练地运用语言,巧妙地把其他关系转
化为数学量间关系。
c.模拟时的优化
如果处理不当,模拟方法写出的程序会非常长。
这要求我们在模拟是将相似的步骤合为一体,适时利用
函数简化程序。
以上面的欧几里得算法为例:
4
/*实现时,若将左边一列数最下面的记为L[1000]、右边一列数记为R[1000],显然是不明智的,因
为只有每列最后一个数会在以后的计算中用到*/
/*实现方法一:
及每一列最后一个数分别为L、R。
输入即可是L、R,返回gcd(L,R)*/
intEuclid_1(intL,intR)
{
for(;;)
{
L=L%R;
if(L==0)returnR;
R=R%L;
if(R==0)returnL;
}
}
/*我们发现有两步是相似的。
因而我们可以把它简化为实现方法二*/
intEuclid_2(intL,intR)
{
intt;
for(;;)
{
t=R;R=L%R;L=t;
if(R==0)returnL;
}
}
/*甚至我们可以写成递归形式。
以下是实现方法三*/
intEuclid_3(intL,intR)
{
if(L%R==0)returnR;
elsereturnEuclid_3(R,L%R);
}
这个实例主要体现模拟算法的简化过程。
虽然在这样小的程序段中,这样的简化作用不大,但遇到复杂
的模拟问题,这种利用相似性的简化便非常有用了。
应当重视这样的代码优化。
d.高精度计算算法
竞赛中经常会用上一些很大的数,超出长整型的数值范围。
这时我们需要使用高精度计算算法。
这种算
法可以把数值范围增加到我们想要的程度。
高精度函数往往包括加、减、乘、输入、输出五种。
实现高精度计算时,常常使用模拟算法——模拟小学竖式运算。
我们把一个高精度数表示为一个数组H[],
数组中的某一个数相当于高精度数的某一位。
要注意的是,输出时往往要求以十进制形式输出。
因而,高精度数每一位都应便于直接输出。
这样,每
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 实用 算法 中国计算机 学会