《信息学竞赛初赛信息学竞赛初赛 复习二》由会员分享，可在线阅读，更多相关《信息学竞赛初赛信息学竞赛初赛 复习二（29页珍藏版）》请在金锄头文库上搜索。
1、奥赛辅导讲座二奥赛辅导讲座二一、算法及算法的特点：一、算法及算法的特点：1算法概念：算法概念： 计算机对问题的求解过程是通过一系列命令来完成计算机对问题的求解过程是通过一系列命令来完成的，这种为了完成某个任务而编写的命令的有序集合，的，这种为了完成某个任务而编写的命令的有序集合，我们称之为程序。在设计程序过程中需要考虑对问题我们称之为程序。在设计程序过程中需要考虑对问题求解的方法和步骤，对问题求解的过程和步骤，我们求解的方法和步骤，对问题求解的过程和步骤，我们称之为算法。算法的优劣将影响程序运行的效率和执称之为算法。算法的优劣将影响程序运行的效率和执行的结果。行的结果。 2算法的特点：算法的特
2、点： 确定性、有穷性、可行性、输入、输出确定性、有穷性、可行性、输入、输出3 算法的评估：算法的评估：算法的评估：算法的复杂性算法的评估：算法的复杂性（1）时间复杂性：牵涉方面比较多，有机器、有语言、问）时间复杂性：牵涉方面比较多，有机器、有语言、问题解决的规模等，若在相同条件下，则取决于算法的优劣。题解决的规模等，若在相同条件下，则取决于算法的优劣。 例如：一般用乘法计算例如：一般用乘法计算 T(n)= O( n3 ) for x:=1 to n do for y:=1 to n do begin cx,y := 0 ; for k:=1 to n do cx,y:= cx,y + a x,
3、k * b k, y end; 算法中基本操作重复执行的次数是问题规模算法中基本操作重复执行的次数是问题规模N的某个函数的某个函数 F(n) ， 时间度量时间度量 T(n)= O(f(n) , 时间取决于时间取决于n和和f(n).时间复杂性：时间复杂性： O(1) O(log n) O(n) O(nlog n) O(n2) O(n3) O(2n) 指数级所花费的时间最长指数级所花费的时间最长（2）空间复杂性：）空间复杂性： S(n) = O( f(n) ) 空间复杂性：空间复杂性： 所占用内存空间的多少。一般指所用的所占用内存空间的多少。一般指所用的变量数。若用递归程序设计，则当递归调用层次太
4、多，也变量数。若用递归程序设计，则当递归调用层次太多，也会造成栈溢出。会造成栈溢出。例题：例题： 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
5、数（转数（转7） 并结束并结束 ，否，否则转（则转（4）（4）h:=h+1 ; k: = h ; （5）将将K 遍除遍除2、3、5、7 四种因子四种因子（6）如果）如果 K=1 则则order ：= order +1 （即第即第order 个个H数）数）（7）输出）输出H数，结束。数，结束。program ex3_1 ; const mark: array 1.4 of integer=(2,3,5,7); var i,h,k,n, order : longint ; begin write(input n:) ; readln(n); h:=1 ; order:=1 ; while orde
6、rn do begin h:=h+1 ; k:=h ; for i:=1 to 4 do while k mod marki=0 do k: =k div marki ; if k= 1 then begin order: = order+1 ; write(h:5);end; end; writeln(the no,n,H number is , h); end.这样的算法，数据不大时，能够忍受时间的冗长，但数据这样的算法，数据不大时，能够忍受时间的冗长，但数据很大时，等待时间较长。很大时，等待时间较长。改进算法改进算法: 利用数学原理，找出规律，构造算法利用数学原理，找出规律，构造算法（1
7、）发现）发现H数的因子只有数的因子只有4种，可以考虑从因子出发，由种，可以考虑从因子出发，由小到大生成小到大生成H数。数。（2）每生成一个）每生成一个H数，其数，其2，3，5，7倍也是倍也是H数，将它存数，将它存放在一个线性表中（数组，可以用放在一个线性表中（数组，可以用4个线性表表示），每个线性表表示），每次将次将4个表中第一个最小数取出。个表中第一个最小数取出。（3）在生成表的过程中，删除重复出现的数。）在生成表的过程中，删除重复出现的数。（4）如果用）如果用4个线性表，会出现内存溢出问题个线性表，会出现内存溢出问题方法方法2program ex3_1_2 ; const maxn=591
8、0; mark:array 1.4 of integer=(2,3,5,7); var i,j,n, min:longint ; p : array1.4 of longint ; h: array1.maxn of longInt ; begin write(input n=,maxn,:) ; readln(n); h1:=1 ; for i:=1 to 4 do pi:=1 ; for i:=2 to n do begin min:=hp1*mark1 ; for j:=2 to 4 do if hpj*markj Aj then k:= j if k i then 交换交换 Ai与与A
9、J 重复重复 N-1 ，则则N个数从小到大排序个数从小到大排序（2） 冒泡法排序（交换排序）冒泡法排序（交换排序） 算法思想：算法思想： 输入输入N个数，存入个数，存入A数组数组 ； 将相邻的两个数进行比较，将小数放在前一个位置，大数放在将相邻的两个数进行比较，将小数放在前一个位置，大数放在后一个位置后一个位置 if AJ AJ+1 then 交换交换 AJ与与AJ+1 重复重复 N-1 次次 ，完成排序任务，完成排序任务以上时间复杂性均为以上时间复杂性均为O(N2) （3）快速排序（划分排序）快速排序（划分排序） 算法思想算法思想：改进的冒泡法：改进的冒泡法 选择一个数（设中间位置的数）选择
10、一个数（设中间位置的数） 通过从两端向中间进行比较和交换，将小于中间的数放在前面，通过从两端向中间进行比较和交换，将小于中间的数放在前面，将大于中间的数放在该数之后将大于中间的数放在该数之后快速排序算法：快速排序算法：（1）设有）设有n个数，存放在个数，存放在S数组中；数组中；（2）在）在 s1.n 中任取一个元素作为比较基准中任取一个元素作为比较基准, 例如取例如取 t=S1, 其目的是定出其目的是定出 t 应在排序结果中的位置应在排序结果中的位置 k, 并将排并将排序的元素交换成：序的元素交换成： s1.k-1 = sk = sk+1.n 即即 s1.k-1 中的元素皆小于等于中的元素皆小
11、于等于 sk; sk+1.n 中的元素皆大于等于中的元素皆大于等于 sk;（3）利利用用分分治治策策略略（即即大大化化小小的的策策略略）可可进进一一步步对对 s1.k-1 和和 sk+1.n 两两组组数数据据再再进进行行快快速速排排序序直直到到分分组组对对象只有一个数据为止。象只有一个数据为止。 （4）具体实现的过程可描述如下）具体实现的过程可描述如下, 设设 n=10, 排序数据为：排序数据为： 下标下标 1 2 3 4 5 6 7 8 9 10 45 36 18 53 72 30 48 93 15 36 i j 36 36 18 53 72 30 48 93 15 45 i j 36 36
12、 18 53 72 30 48 93 15 45 i j 36 36 18 15 72 30 48 93 45 53 i j 36 36 18 15 45 30 48 93 72 53 i j 36 36 18 15 45 30 48 93 72 53 i j 36 36 18 15 45 30 48 93 72 53 i j 36 36 18 15 30 45 48 93 72 53 i j 36 36 18 15 30 45 48 93 72 53 i, j 通过一次排序，将通过一次排序，将45放在它应有的位置，然后再对两个分放在它应有的位置，然后再对两个分表分别再进行快速排序，直到所有数
13、据排序完毕。程序如表分别再进行快速排序，直到所有数据排序完毕。程序如下：下： 重复重复N-1，则完成整个排序则完成整个排序program kuaisupaixu; const m=100 ; var i, m1,h1 :integer ; a : array 1.m of integer ; procedure quicsort(h, t : integer ); var mid,i,j,x: integer ; begin if ht then begin i:=h; j:=t ; x:=a(i+j) div 2 ;repeat while ai x do j:=j-1 ; if i=j ;
14、 end; if j h then quicsort(1, j) ; if i t then quicsort( i, t); end;begin writeln(input m1 number:); readln(m1); writeln(input number:); for i:=1 to m1 do read( ai ); quicsort(1,m1); for i:=1 to m1 do write(ai:5); writeln; end. （4）插入排序：）插入排序： 算法思想：算法思想： 输入输入N个数存入个数存入A数组数组 将第一个数将第一个数A1中，从中，从I：=当前后一个位
15、置开始，当前后一个位置开始，将无序的数与将无序的数与Ai比较，如果比比较，如果比Ai大，则从大，则从i 位开始向位开始向后移动，并将它插入其后移动，并将它插入其i 位位; 重复重复n-1次，完成插入排序次，完成插入排序（5）希尔排序（不稳定的排序）希尔排序（不稳定的排序） O( nlog2n ) O(n 2) 算法思想：改进插入排序算法思想：改进插入排序 输入输入N个数存入个数存入A数组数组 将将N个数分组进行插入排序，分组方法是：个数分组进行插入排序，分组方法是： D：= N ； D：= D DIV 2 （ 重复，直到重复，直到D 1为止）为止） 此排序方法是希尔此排序方法是希尔1959年提
16、出来的，又称缩小增量算法，年提出来的，又称缩小增量算法，其基本思想是：其基本思想是： （1）将将大大量量的的插插入入排排序序化化分分为为小小组组的的少少量量数数据据的的插插入入排序策略排序策略 （2）发现当）发现当 n 不大时，插入排序的结果是十分令人满不大时，插入排序的结果是十分令人满意的。设法先取小于意的。设法先取小于 n 的一个增量的一个增量 d1 , 将第将第 1, 1+d1 , 1+2d1 +个元素作为一组个元素作为一组, 第第 2, 2+d1 作第二组作第二组, 第第 d1 , d+d1 , 作为第作为第 d1 组组; 在各组之内用插入排序在各组之内用插入排序, 然后然后取取 d2
17、 =1 do begin for i:=d+1 to n1 do begin x:=bi;j:= i-d ; while (j0) and ( x bj) do begin bj+d:=bj ;j:=j-d ; end; bj+d:=x ; end; d:= d div 2 ; end; end;begin writeln(input n number:); for x:=1 to n do read(ax); for x:=1 to n do write(ax:4); writeln; shell(a,n); for x:=1 to n do write(ax:4); writeln; en
18、d.（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 ) 前者为小根堆，后者为大根堆。堆是一棵完全二叉树前者为小根堆，后者为大根堆。堆是一棵完全二叉树 堆排序：建堆和利用堆排序堆排序：建堆和利用堆排序数据结构书的数据结构书的20
19、1204 页页 建堆的过程建堆的过程 筛运算排序过程筛运算排序过程建堆算法：建堆算法： procedure cret ( A, n ,I ) ; begin (1) x:= AI ; ( 2) j:=2*I ; ( 3) while j=n do A. If (jn ) and (Aj Aj+1 do j:=j+1 ; B. If xA J then AI:=Aj ; I:=j ; j:=2*I ; else j:=n+1 ; ( 4) AI := x ; end; 堆排序的过程：堆排序的过程： procedure duisort ( A, n ) ; begin (1) for i:=(n
20、div 2) downto 1 do cret( A,n,I) ; (2) for i:= n downto 2 do A1 A i cret(A, i-1, 1 ) end; 作业作业: 完成所有排序程序的调试任务完成所有排序程序的调试任务,比较算法的时间复比较算法的时间复杂性。杂性。排序比较：排序比较：（1）当）当N较小时，用简单排序方法，（稳定）较小时，用简单排序方法，（稳定）（2）当）当N较大时，用改进型的排序（快速、希尔、堆排较大时，用改进型的排序（快速、希尔、堆排序）序） 简单排序的时间复杂性：简单排序的时间复杂性：O（n2） 改进算法的排序时间复杂性：改进算法的排序时间复杂性：
21、O（ n log2n ) 快速排序稳定性不好（正序、逆序）快速排序稳定性不好（正序、逆序） 归并排序稳定性最好（内存空间允许）归并排序稳定性最好（内存空间允许） 希尔、堆排序的稳定性比快速排序好。希尔、堆排序的稳定性比快速排序好。CONST N=5;VAR I,J,K : INTEGER; A : ARRAY1.2*N, 1.2*N OF INTEGER; BEGIN K:=1; FOR I:=1 TO 2*N-1 DO IF I=N THEN IF ODD(I) THEN FOR J:= I DOWNTO 1 DO BEGIN AI-J+1,J:=K; K:=K+1 END ELSE FOR J:=1 TO I DO BEGIN AI-J+1,J:=K; K:=K+1; END ELSE IF ODD(I) THEN FOR J:=N DOWNTO I-N+1 DO BEGIN AI-J+1,J:=K; K:=K+1; END ELSE FOR J:=I-N+1 TO N DO BEGIN AI-J+1,J:=K; K:=K+1; END; FOR I:=1 TO N DO BEGIN FOR J:=1 TO N DO WRITE(AI,J:3); WRITELN END;END.
