信息学竞赛初赛信息学竞赛初赛 复习二.ppt

奥赛辅导讲座二一 算法及算法的特点 算法概念 计算机对问题的求解过程是通过一系列命令来完成的 这种为了完成某个任务而编写的命令的有序集合 我们称之为程序 在设计程序过程中需要考虑对问题求解的方法和步骤 对问题求解的过程和步骤 我们称之为算法 算法的优劣将影响程序运行的效率和执行的结果 算法的特点 确定性 有穷性 可行性 输入 输出3算法的评估 算法的评估 算法的复杂性 1 时间复杂性 牵涉方面比较多 有机器 有语言 问题解决的规模等 若在相同条件下 则取决于算法的优劣 例如 一般用乘法计算t n o n3 forx 1tondofory 1tondobeginc x y 0 fork 1tondoc x y c x y a x k b k y end 算法中基本操作重复执行的次数是问题规模n的某个函数f n 时间度量t n o f n 时间取决于n和f n 时间复杂性 o 1 o logn o n o nlogn o n2 o n3 o 2n 指数级所花费的时间最长 2 空间复杂性 s n o f n 空间复杂性 所占用内存空间的多少 一般指所用的变量数 若用递归程序设计 则当递归调用层次太多 也会造成栈溢出 例题 h数的算法问题 h数是指除1以外 最多只有2 3 5 7四种因子 如630即为h数 而22不是 要求对键盘输入的自然数n 求出第n个h数 如n 30应输出49 规定要求的h数不超出长整型数的范围 算法分析 1 输入n 2 置第一个h数 h 1 order 1 3 如果order n则输出第n个h数 转7 并结束 否则转 4 4 h h 1 k h 5 将k遍除2 3 5 7四种因子 6 如果k 1则order order 1 即第order个h数 7 输出h数 结束 programex3 1 constmark array 1 4 ofinteger 2 3 5 7 vari h k n order longint beginwrite inputn readln n h 1 order 1 whileorder ndobeginh h 1 k h fori 1to4dowhilekmodmark i 0dok kdivmark i ifk 1thenbeginorder order 1 write h 5 end end writeln theno n hnumberis h end 这样的算法 数据不大时 能够忍受时间的冗长 但数据很大时 等待时间较长 改进算法 利用数学原理 找出规律 构造算法 1 发现h数的因子只有4种 可以考虑从因子出发 由小到大生成h数 2 每生成一个h数 其2 3 5 7倍也是h数 将它存放在一个线性表中 数组 可以用4个线性表表示 每次将4个表中第一个最小数取出 3 在生成表的过程中 删除重复出现的数 4 如果用4个线性表 会出现内存溢出问题 方法2programex3 1 2 constmaxn 5910 mark array 1 4 ofinteger 2 3 5 7 vari j n min longint p array 1 4 oflongint h array 1 maxn oflongint beginwrite inputn maxn readln n h 1 1 fori 1to4dop i 1 fori 2tondobeginmin h p 1 mark 1 forj 2to4doifh p j mark j minthenmin h p j mark j h i min forj 1to4doifh p j mark j minthenp j p j 1 end writeln theno n hnumberis h n end 说明 长整型是32位二进制数来表示的 即要4个字节存放 pascal允许使用的存储空间64kb 最多16000多个长整型 而该问题的空间复杂性为o n 当n太大时溢出 该题来自于acm大学生程序设计竞赛题 第一种算法时间复杂性超过o n n 第二种空间复杂性o n 二 根据题意 写出问题的算法 1p32 p632排序算法 从小到大排列 1 选择排序 枚举排序 算法思想 输入n个数 从循环完成剩余的数中找最小数 放在a i 中 开始从n个 再次从n 1个 ifa i a j thenk j ifkithen交换a i 与a j 重复n 1 则n个数从小到大排序 2 冒泡法排序 交换排序 算法思想 输入n个数 存入a数组 将相邻的两个数进行比较 将小数放在前一个位置 大数放在后一个位置ifa j a j 1 then交换a j 与a j 1 重复n 1次 完成排序任务以上时间复杂性均为o n2 3 快速排序 划分排序 算法思想 改进的冒泡法 选择一个数 设中间位置的数 通过从两端向中间进行比较和交换 将小于中间的数放在前面 将大于中间的数放在该数之后 快速排序算法 1 设有n个数 存放在s数组中 2 在s 1 n 中任取一个元素作为比较基准 例如取t s 1 其目的是定出t应在排序结果中的位置k 并将排序的元素交换成 s 1 k 1 s k s k 1 n 即s 1 k 1 中的元素皆小于等于s k s k 1 n 中的元素皆大于等于s k 3 利用分治策略 即大化小的策略 可进一步对s 1 k 1 和s k 1 n 两组数据再进行快速排序直到分组对象只有一个数据为止 4 具体实现的过程可描述如下 设n 10 排序数据为 下标12345678910 45361853723048931536 i j 36361853723048931545 i j 36361853723048931545 i j 36361815723048934553 i j 36361815453048937253 i j 36361815453048937253 i j 36361815453048937253 i j 36361815304548937253 i j 3636181530 45 48937253 i j通过一次排序 将45放在它应有的位置 然后再对两个分表分别再进行快速排序 直到所有数据排序完毕 程序如下 重复n 1 则完成整个排序programkuaisupaixu constm 100 vari m1 h1 integer a array 1 m ofinteger procedurequicsort h t integer varmid i j x integer beginifh tthenbegini h j t x a i j div2 repeatwhilea i xdoj j 1 ifi j end ifj hthenquicsort 1 j ifi tthenquicsort i t end beginwriteln inputm1number readln m1 writeln inputnumber fori 1tom1doread a i quicsort 1 m1 fori 1tom1dowrite a i 5 writeln end 4 插入排序 算法思想 输入n个数存入a数组 将第一个数 a 1 中 从i 当前后一个位置开始 将无序的数与a i 比较 如果比a i 大 则从i位开始向后移动 并将它插入其i位 重复n 1次 完成插入排序 5 希尔排序 不稳定的排序 o nlog2n o n2 算法思想 改进插入排序 输入n个数存入a数组 将n个数分组进行插入排序 分组方法是 d n d ddiv2 重复 直到d 1为止 此排序方法是希尔1959年提出来的 又称缩小增量算法 其基本思想是 1 将大量的插入排序化分为小组的少量数据的插入排序策略 2 发现当n不大时 插入排序的结果是十分令人满意的 设法先取小于n的一个增量d1 将第1 1 d1 1 2d1 个元素作为一组 第2 2 d1 作第二组 第d1 d d1 作为第d1组 在各组之内用插入排序 然后取d2 d1再进行上述过程 直到增量di 1为止 排序前 首先 把10个元素分为5组 每组两个元素 对每组进行插入排序 d1 5 在上一步基础上 重新将10个元素分成2组 每组5个元素 其中将奇数分为一组 偶数分为一组 对每组再进行插入排序 d2 2 25123225433648587665 最后把10个元素看作一组 进行插入排序 其最后结果是 d3 1结果 12252532364348586576希尔排序中的问题是 究竟增量个数是多少 每次增量给定什么值 只知道逐次缩小 直到1 至今尚无十分明确的规则可以依据 只能凭经验来取 该算法是一种不稳定的排序 其时间复杂性约o n1 3 programshellsort constn 10 typearr array 1 n ofinteger vara arr x y integer procedureshell varb arr n1 integer vari d j x integer begind n1div2 whiled 1dobeginfori d 1ton1dobeginx b i j i d while j 0 and x b j dobeginb j d b j j j d end b j d x end d ddiv2 end end beginwriteln inputnnumber forx 1tondoread a x forx 1tondowrite a x 4 writeln shell a n forx 1tondowrite a x 4 writeln end 6 堆排序 改进的选择排序 算法思想 堆的定义 有一系列元素r1 r2 rn 对应的排序码为 s1 s2 sn 若此排序码序列满足如下情况的一种 则称此序列为堆 si s2i和si s2i 1 1 i n 2 si s2i和si s2i 1 1 i n 2 前者为小根堆 后者为大根堆 堆是一棵完全二叉树 堆排序 建堆和利用堆排序数据结构书的201 204页 建堆的过程 筛运算排序过程 建堆算法 procedurecret a n i begin 1 x a i 2 j 2 i 3 whilej ndoa if j n and a j a j 1 doj j 1 b ifx a j then a i a j i j j 2 i elsej n 1 4 a i x end 堆排序的过程 procedureduisort a n begin 1 fori ndiv2 downto1docret a n i 2 fori ndownto2do a 1 a i cret a i 1 1 end 作业 完成所有排序程序的调试任务 比较算法的时间复杂性 排序比较 1 当n较小时 用简单排序方法 稳定 2 当n较大时 用改进型的排序 快速 希尔 堆排序 简单排序的时间复杂性 o n2 改进算法的排序时间复杂性 o nlog2n 快速排序稳定性不好 正序 逆序 归并排序稳定性最好 内存空间允许 希尔 堆排序的稳定性比快速排序好 constn 5 vari j k integer a array 1 2 n 1 2 n ofinteger begink 1 fori 1to2 n 1doifi nthenifodd i