浙江师范大学ACM算法入门教材

需积分: 9 172 浏览量更新于2024-07-29 收藏 430KB PDF 举报

"浙师大acm教材" 本书是针对浙江师范大学数理与信息工程学院ACM/ICPC集训队的算法设计入门教材，由瞿有甜整理。教材旨在介绍算法设计的基础概念、方法和分析，帮助学生掌握解决计算问题的技巧。在第一章《算法初步》中，教材首先定义了算法的含义。算法是一系列精确描述解决问题步骤的方法，但并非所有问题都能找到有效的算法。算法设计的关键在于将问题精确地形式化，并根据问题特性设计出合适的算法。教材列举了一些常见的算法设计策略，如穷举搜索法、递归法、回溯法、贪心法和分治法。接着，教材探讨了算法分析，这是评估算法性能的重要手段。时间复杂度衡量算法运行所需时间，而空间复杂度则关注算法执行过程中所需存储空间。两者通常用大O记法表示，如O(f(n))和O(g(n))分别代表时间复杂度和空间复杂度。在后续部分，教材转向程序设计，强调了程序是数据结构和算法的结合，程序设计不仅仅是编写代码，还包括调试和优化。结构化程序设计作为一种设计准则，强调逐步求精和模块化，使得程序更易于理解、维护和验证。这种设计方法通过逐步细化将复杂问题分解为可管理的部分，从最抽象的程序设计到最终的可执行程序。通过本教材的学习，读者可以系统地了解算法和程序设计的基础知识，为参与ACM/ICPC竞赛或从事相关领域的研究打下坚实的基础。浙江师范大学的ACM/ICPC集训队成员可以通过这本教材，深入理解算法设计的原理和实践，提升解决问题的能力。

浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料

if b<>0 then ReadDigit(b);

End;

writeln;

End.

5、数列找数

：数组 A(N)的各下标变量中Ｎ个互不相等的数，键盘输入正整数Ｍ（Ｍ≤Ｎ），要求打印

数组中第Ｍ大的下标变量的值。

例如：数组 A（10）的数据为：

A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8)

A(9) A(10)

16 57 20 19 38 41 6 13

25 32

运行结果：INPUT AN NUMBER:３

A(5)=38 （即第３大的数是 A(5)=38）

[解]该题要从 N 个互不相等的数中找第 M 大的值。有以下两种解法：

解法一：初始时：A 数组存放 N 个互不相等的数；B 数组用于存放数组 A 的下标。见下表一。

下标值 i 1 2 3 4 5 6 7 8

9 10

数组 A 16 57 20 19 38 41 6 13

25 32

数组 B 1 2 3 4 5 6 7 8

9 10

降序处理（冒泡排序法）：

数组 A 的元素由大到小进行排序，同时数组 B 的元素排列也随之变化。

下标值 I 1 2 3 4 5 6 7 8

9 10

数组 A 57 41 38 32 25 20 19 16

13 6

数组 B（原

数组A的

下标）

例题中 M=3，由表二知 A[3]=38，B[3]=B[M]=5（原数组 A 的下标值）即为所求。

[程序]

Program Max01;{冒泡排序法}

var i,j,n,m,x:integer;

A,B:ARRAY[1..100] of integer;

Procedure Init; {读数初始化过程}

Var i,j:integer; fd:boolean;

Begin

write('Input N:');readln(N); {读入 N}

if N<1 then begin writeln('Input error!');halt;end;

write('Input ',N:3,' Data:');

For i:=1 to n Do

begin read(A[i]);B[i]:=i;end;{读入 A[i],且 B[i]初值置为 i}

Readln;

i:=1; fd:=false; {数组中的数有相同的标志}

while NOT fd and (i<=N-1) do

Begin j:=i+1;

While NOT fd and (j<=N) do

begin fd:=A[i]=A[j]; {若 A[i]=A[j]，则 fd=true；否则 fd=false}

j:=j+1;

end;

i:=i+1;

End;

If fd then {fd 为 True，则表示数组中至少有两个相等的数}

begin writeln('More equal number!');halt;end;

write('Input M:');readln(M);

If M>N then {表明所找的数 M 已超过输入数的总数 N}

begin writeln('Input error!');halt;end;

End; {Init}

Begin {MAIN}

瞿有甜整理第 5 页 2006 年 9 月

剩余26页未读，继续阅读

hkx1n

粉丝: 119
资源: 216

浙江师范大学ACM算法入门教材

浙师大acm教材，浙师大acm教材，为你提供最基础的acm知识

浙江师范大学acm教材

浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料

浙师大ACM教材：详解算法设计与程序编程

浙江师范大学ACM算法设计入门教材概览

浙师大ACM算法设计入门教材解析

浙师大ACM入门资料：算法设计详解与程序编程指南

ACM资料合集

acm程序设计算法集

浙师大ACM教材

最新资源