当前位置：文档之家 › 计算机程序设计竞赛-第1讲

计算机程序设计竞赛-第1讲

  • 格式：pptx
  • 大小：581.04 KB
  • 文档页数：87

下载文档原格式

  / 87

合集下载

acm程序设计教程 course(1)初识ACM

acm程序设计教程 course(1)初识ACM


2011-9-5
38



2009-6-9 讨论湖南省大学生计算机程 序设计竞赛湖南师范大学具体实施方案 2009-6-10 下发2009年湖南省大学生计 算机程序设计竞赛湖南师范大学选拔赛 通知（数计院、物信院、工学院） 2009-6-15 正式选拔 2009-7-4 开学典礼 7-10——8-10 暑假集训
2011-9-5
6
ACM/ICPC in China

中国大陆高校从1996年开始参加ACM/ICPC—— 前六届中国赛区设在上海，由上海大学承办； 2002年由清华大学和西安交通大学承办； 2003年由清华大学和中山大学承办。 2004年由北京大学和上海交通大学承办。 2005年由四川大学、北大和浙大承办。 2006年由上海大学、清华和西电承办。 2007年：北航、南航、吉大、西华 2008年：哈工程、北交、合肥、杭电、西南民大
35
2011-9-5
今年比赛

2011(9.14-9.15) 湖南农业大学
2011-9-5
36
第三部分
我校ACM相关情况
2011-9-5 37
组建过程


Байду номын сангаас
2009-5-7 ACM/ICPC华中南区程序设 计大赛选拔考试（小范围，数计学院） 2009-5-8 组队报名、竞赛介绍、简单 培训 5月29日至5月31日 参加ACM/ICPC华 中南区程序设计大赛（湖南大学）
参赛队组成




ACM-ICPC以团队的形式代表各学校参赛， 每个 赛区的优胜队伍将获得参加ACM国际大学生程序 设计竞赛全球总决赛资格。 亚洲区的高校可以组队参加亚洲的任何一个或者 几个赛区的比赛，但每所高校最多只能有一队可 以获得参加全球世界决赛的资格。 每队由一名教练和三名队员组成, 有些赛区还允许 有一名候补队员。 亚洲区的每位参赛选手在一年内最多可参加两个 赛区的亚洲区预选赛, 每位选手最多可以参加五届 亚洲区预选赛和两届全球总决赛。
第1讲 程序设计的一般步骤ok资料

第1讲 程序设计的一般步骤ok资料

第1讲C++语言入门学习目标1、了解计算机语言发展的3个阶段。

2、理解程序设计的一般步骤。

3、掌握什么是算法。

4、掌握对给定的问题进行算法描述。

5、学会编写简单的程序。

随着科技的发展和社会的进步，计算机已经走入寻常百姓家。

人们可以使用同一台计算机做不同的事，我们可以看到其他机器或设备做不到这点。

计算机之所以能执行不同的工作任务，是基于其硬件和软件协同工作的工作机制。

要使计算机按人们指定的步骤有效地工作，必须事先编制好一组让计算机执行的指令，这就是程序。

随着计算机软件技术的发展，人们可以使用不同的计算机语言来编写程序。

一、计算机语言发展要使计算机按照人的规定完成一系列的工作，首先要解决一个“语言”沟通问题：在人和计算机之间找到一种两者都能识别的特定的语言，使计算机具备理解并执行人们给出的各种指令的能力。

这种特定的语言称为计算机语言，也叫程序设计语言，它是人和计算机沟通的桥梁。

随着计算机技术的迅速发展，程序设计语言经历了由低级向高级发展的多个阶段，程序设计方法也得到不断的发展和提高。

计算机语言按其发展程度可以划分为：机器语言、汇编语言和高级语言。

1、机器语言计算机并不能理解和执行人们使用的自然语言。

计算机能够直接识别的指令时由一连串的0和1组合起来的二进制编码，称为机器指令。

每一条指令规定计算机要完成的某个操作。

机器语言是计算机能够直接识别的指令的集合，它是最早出现的计算机语言。

例如，下图所示的是某一种型号计算机的一组二进制编码机器指令，用来完成一个简单加法操作。

1011000000001001000001000000100011110100显然，用机器语言编写的程序“难学、难记、难写、难检查、难调试”，给使用者带来很大的不便。

机器语言编写的程序另一个缺点是完全依赖于机器硬件，不同型号的机器语言指令不相同，程序的可移植性差。

其优点是计算机能直接识别、执行效率高。

2 、汇编语言20世纪50年代初,为了克服机器语言的缺点，人们对机器语言进行了改进，用一些容易记忆和辨别的有意义的符号代替机器指令。

c语言程序设计竞赛辅导1

c语言程序设计竞赛辅导1

记a，b，c分别为所猜数据d除以3，5，7后的余数， 则d=70*a+21*b+15*c。 则建立数学模d=70*a+21*b+15*c的过程如下:
8/4/2013
12
d = 7 0 *a + 2 1 *b + 1 5 * c
a、b、c的系数必须满足：
1）b、c的系数能被3整除，且a的系数被3整除余1；
printf(“The number of >=90 is“%d”,num);
8/4/2013
}
17
【例2】开灯问题：有从1到n依次编号的n个同学 和n 盏灯。1号同学将所有的灯都关掉；2号同学
将编号为2的倍数的灯都打开；3号同学则将编号
为3的倍数的灯作相反处理（该号灯如打开的，则
关掉；如关闭的，则打开）；以后的同学都将自
2. 算术运算的妙用
1） 减化或避免条件判断
【例1】一次考试，共考了五门课。统计五十个学生
中至少有三门课成绩高于90分的人数。 实 现 要 点 ：
1）对每个同学，先计算其成绩高于90分的课程 数目，若超过3，则累加满足条件的人数中。 2）用二重循环实现以上过程，外层循环模拟50
个同学，内层循环模拟五门课程。
8/4/2013
哥 德 巴 赫 猜 想 ） ， 或 通 过 程 序 进 行 大 量
是 否 正 确 可 以 通 过 数 学 方 法 证 明 （ 就 象
是 利 用 数 学 知 识 建 模 的 过 程 。 “ 感 知 ”
的 组 数 等 于 与 的 最 大 公 约 数 。 这 就
问 题 与 最 大 公 约 数 有 关 ， 即 循 环 移 动
3、5和7并得到三个余数。你把这三个余数告诉计算机，
计算机编程C语言第1讲C语言Windows命令行编程

计算机编程C语言第1讲C语言Windows命令行编程

C语言Windows命令行编程
1、Windows提供了很多DOS命令
CMD命令：开始－>运行－>键入cmd或command（在命令行里可以看
到系统版本、文件系统版本）
1. appwiz.cpl：程序和功能
2. calc：启动计算器
3. certmgr.msc：证书管理实用程序
4. charmap：启动字符映射表
5. chkdsk.exe：Chkdsk磁盘检查（管理员身份运行命令提示符）
6. cleanmgr: 打开磁盘清理工具
7. cliconfg：SQL SERVER 客户端网络实用工具
8. cmstp：连接管理器配置文件安装程序
9. cmd.exe：CMD命令提示符
10. 自动关机命令
Shutdown -s -t 600：表示600秒后自动关机
shutdown -a ：可取消定时关机
Shutdown -r -t 600：表示600秒后自动重启
rundll32 user32.dll,LockWorkStation：表示锁定计算机
11. colorcpl：颜色管理，配置显示器和打印机等中的色彩
12. CompMgmtLauncher：计算机管理
13. compmgmt.msc：计算机管理
…………………………..
2、按下Win+R，输入cmd进入命令行模式
3、ping 是查看网络是否畅通
4、运行如下的代码，打开本地用户和组管理器
运行效果如下
4、把IP路由打印出来
运行效果如下：
5、下面有很多的DOS命令通过system函数在程序中运行。

NOI初级教程

NOI初级教程

二、分区联赛特点和历史回顾
从 1995 年第一届分区联赛开始，已经比较成熟了。题目的难度和考查 范围从总体来说是逐年增加。初赛主要是靠平时的积累。其中选择题部分各 年差别比较大，考查的范围很不相同。坦白地说，初赛的题目水平并不是很 高，虽然题目有时看起来不大规范，不过从另一方面讲，在选拔复赛选手的 角度讲，初赛题目还是比较成功的。只要基础好（选择题和填空题），有耐 心（完善程序）和细心（写运行结果），初赛一般都能得到高分。 至于复赛， 全是上机完成。
6、已知 N*N 个数据成方阵排列: A11 A12 A13 ... A1n A21 A22 A23 ... A2n ... An1 An2 An3 ... Ann 已知 Aij=Aji, （ 1 ） 、 将 A11,A21,A22,A31,A32,A33... 存 储 到 一 维 数 组 A(1),A(2),A(3)...A(K) 给出 i,j 写出求 K 的表达式:_________________ （ 2 ）、 将 A11,A12,...A1n,A22,A23,...A2n,A33... Ann 存 储 到 一 维 数 组 A(1),A(2),A(3)...A(K), 给出 i,j 写出求 K 的表达式:_________________
4、根据后缀表达式,写出前缀及中缀表达式 ABC/DE+GH-/*+ 前:_________________中:_________________ [说明]：这两题考查了数据结构中的表达式树。
5、用一个字节来表示整数,最高位用作符号位(1 为正,0 为负),其他位表示数 值： （1）、这样的表示法称为原码表示法,表示数的范围为:_________________ （2）、原码表示法,将出现_________________有两种表示 （3）、实际上计算机中是用补码表示数,其表示范围为:_________________ [说明]：考查了数的原码，补码表示形式，知道了原码就是直接二十进制的 转化，补码是反码的基础上加 1，而补码只对非正数应用。
计算机程序设计竞赛-第1讲[详版课资]

计算机程序设计竞赛-第1讲[详版课资]

ELSE print -x
也可以用汉字伪代码表示：
若 x为正 打印 x
打印 -x
也可以中英文混用，如：
IF x print x
ELSE print -x
23
课堂优质
1.4 算法的表示
❖用计算机语言表示算法 ▪ 概念： 用计算机语言描述算法，就是用计算机语言编写程序。 计算机是无法识别流程图和伪代码的。只有用计算机语 言编写的程序才能被计算机执行。 ▪ 特点： 设计算法的目的是为了实现算法。 用计算机语言表示算法，必须严格遵循所用的语言的语法 规则。
✓自然语言 ✓传统流程图 ✓N-S流程图 ✓伪代码 ✓计算机语言
8
课堂优质
1.4 算法的表示
❖传统流程图（流程图）
美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：
起止框
判断框
处理框
输入/输出框
注释框
流向线
连接点
9
课堂优质
26
课堂优质
1.5 算法复杂度的分析
❖ 算法的复杂性越高，所需的计算机资源越多。 ❖ 最重要的计算机资源是时间资源与空间资源。 ❖ 需要计算机时间资源的量称为时间复杂度，需要计算机空
间资源的量称为空间复杂度。 ❖ 时间复杂度与空间复杂度集中反映算法的效率。
27
课堂优质
1.5 算法复杂度的分析
✓ 一个算法的时间复杂度是指算法运行所需的时间。 一个算法的运行时间取决于算法所需执行的语句（运算）的 多少。 算法的时间复杂度通常用该算法执行的总语句（运算）的数 量级决定。
例1-4 估算以下程序段所代表算法的时间复杂度。 for(k=1;k<=n;k++) for(j=1;j<=k;j++)
PASCAL第1讲 Pascal语言基础知识

PASCAL第1讲 Pascal语言基础知识

div mod 整除 取余 运算对象 整型、实型 整型、实型 整型、实型 整型、实型 整型 整型 结果类型 只要有一个运算对象是实型，结果就 是实型，如果全部的运算对象都是整 型并且运算不是除法，则结果为整型 若运算是除法，则结果是实型。 整型 整型
2、表达式 是通过运算符把常量、变量、函数调用结合起来组成的。 3+x1+b
e=2.718…..
abs(-4)=4
abs(-7.49)=7.49
int(3.71)=3.0 sqrt(4)=2
正确的书写表达式：
1 1）、 a cb
2）、
b b 4ac 2a 2
上机练习
1、输入三角形的三条边a，b，c，输出三角形的面 积。（a，b，c是正整数<100，满足三角形条件）
Write语句与writeln语句格式上都相似，但它们在功能 上有所不同，两个语句的区别在于: write语句将其后括号中的表达式一个接一个输出后， 没有换行。 而writeln语句则在输出各个表达式的值后换行。 例如以下两个程序段的输出分别为： write(1,2,3,4); write(5,6); 输出为： 123456 writeln(1,2,3,4); write(5,6); 输出为： 1234 56
read(v1，v2，…，vn)； readln(v1，v2，…，vn)；
从键盘逐次读入数据，分别赋给变量v1，v2，…，vn。 一行输入多个整型或实型变量值时，要求数据之间用空格 分隔，readln语句要求输入数据后必须回车，使得后继操 作从下一行的头上开始。
read语句与readln语句区别是：
6 4 8 10 8
例:
输入:两个整数a、b(<=3000)，输出它的乘积c，商d。
信息学奥赛第一讲-Pascal入门

信息学奥赛第一讲-Pascal入门


上机操作练习一


【题目描述】Hello,world! 2016年3月，由谷歌公司研发的围棋人工智能程序（AlphaGo）以 4:1的总比分战胜世界围棋冠军、职业九段选手李世石。随后数年间， 更强大、更智能的人工智能程序如雨后春笋般涌现。 人工智能逐步渗入了人类的军事、经济、政治等各领域，最终引 发了威胁魔法世界人类生存的重大危机，但据说当第一个拥有独立人 格和意识的人工智能程序体最初来到这个世界时，它曾经友善而好奇 地在屏幕上输出一行“Hello,world!"。 【输出格式】 输出一行“Hello,world!"的字符串（不包含双引号），注意字符均 为半角字符。注意程序为标准输入输出格式，由评测软件自动评测而 不是人工评测，所以上交的代码无需添加暂停命令。 【输出样例】 Hello,world!



怎么描述算法？
我们可以用自然语言或者是用流程图来描述算法
自然语言描述算法：
例1.1 有三个杯子：A杯装着白开水、B杯装着红茶，C杯空着。 想要把A杯和B杯里的内容交换过来，需要怎样做呢？ （1）A杯的白开水倒给C杯； （2）将B杯的红茶倒给A杯； （3）将C杯的白开水倒给B杯； 例1.2 交换A和B的值。 （1）将A的值给C； （2）将B的值给A； （3）将C的值给B；
Pascal语言概述
自然语言 信息交流（地位平等） 有思维、推理能力 语法规则、句法规则灵活 （可省略、颠倒） 表达方式多样
Pascal语言 人机对话（命令方式） 有计算、逻辑判断的能力 语法句法固定 （按部就班） 算法多样
学习要点：学会Pascal的语法、句法； 学会算法分析与算法设计；
Pascal语言的特点
两个误区

误区1 信息学竞赛 = “计算机”竞赛
第1讲 计算机与程序设计

第1讲 计算机与程序设计


机器语言
10110000 00001001 00000100 00001000 11110100
计算机能够直接识别 的语言 。
汇编语言
MOV AL，9
ADD AL，8
汇编语言和机器语言实 质是相同的，都是直接 对硬件操作，只不过指 令采用了英文缩写的标 识符，容易识别和记忆
高级语言
Print 8+9
1.什么是硬件? 2.列出典型计算机系统的6种基本组件? 3.计算机的哪个部分长时间保存数据,即使未通电? 4.列举一些输入设备? 5.您将从计算机向外界输出数据的设备称为什么? 6.什么是软件 ? 7.软件类别分为几种?它们的名称各是什么? 8.什么是编译器? 9.什么是解释器? 10.”机器语言”是什么意思?
由于船小,农夫一次只能带其中的一样过河。 如无人看管,狼要吃羊,羊 要吃菜。问农夫如何安排过河,才能使狼、羊、菜都安然无恙。
渡河的方法与步骤:
第一步：农夫带着羊渡过河去； 第二步：农夫划船回来； 第三步：农夫带着菜渡过河去； 第四步：农夫带着羊划船回来； 第五步：农夫带着狼渡过河去； 第六步：农夫划船回来； 第七步：农夫带着羊渡过河。
好好学习 天天向上
第一课:计算机与程序设计
目标
01.计算机基础 02.计算机语言与程序设计 03.算法
PART 01
计算机基础
硬件:是指组成计算机的所有设备或组件.
输出 设备
输入 设备
辅助存 储器
主存 (RAM)
中央处 理器
主存 (ROM)
软件:是一系列按照特定顺序组织的计算机数据和序.例如:操作 系统(windows,linux)
和汇编语言相比，它不 但将许多相关的机器指 令合成为单条指令，并 且去掉了与具体操作有 关但与完成工作无关的 细节。
ACM程序设计竞赛II第一章

ACM程序设计竞赛II第一章


•
if(q >= y || (p < m && A[p] <= A[q]))//右边空，或者两边都不空且右边大
•
T[i++] = A[p++];//复制左边的
•
else
•3;] = A[q++];//复制右边的
•
*cnt += m-p;//是逆序数的数目
•
}
•}
• for(i = x; i < y; i++) A[i] = T[i];
count++;
printf("%d\n",count);
}
2021/8r/e2turn 0;
11
}
首先抽象数学模型
• 数据如何存储
– 问题一：顺序表、链表？ – 问题三：二维数组？
• 对模型选择适当算法
– 问题one by one
• 求解
– 此处省略1万字
2021/8/2
12
关于字符串
• 基本：长度、拷贝、连接、比较、反串、判断回文 • 进阶：子串（模式匹配）
照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：
No duplicates
(注2意021N/8大/2 写)
19
Sample Input
问题六—(HDOJ-1800)
Flying to the Mars
2021/8/2
20
字符串哈希 HDOJ-1800题
• 除去马甲，本题的本质是——求相同级别（level）的人 最多是几个。
• 输出：每一行一个整数x,对应一组case,表示该组case的 字符串中所包含的最长回文长度.
ACSL美国计算机科学联赛-Intermediate Division中级-Contest 1竞赛1-Programming Problem程序设计问题

ACSL美国计算机科学联赛-Intermediate Division中级-Contest 1竞赛1-Programming Problem程序设计问题

INTERMEDIATE DIVISION PROGRAMMING PROBLEMWRAP AROUND CODEPROBLEM: This is yet another in a long list of ACSL code programs. You would think wewould have run out of them by now. In this program you will be given a set of letters to encode. The difference here is that different rules are used for different letters and the counting process starts where the last letter ends. Using the numerical value of each letter (A=1, B=2, … Z= 26) the rules are as follows :As an example, if the set of letters to encode consists of the letters B, G and Z, then the B with a numerical value of 2 encodes to a 4. Counting 4 letters from A produces an E. The G, with a numerical value of 7, encodes to a 5. Counting down 5 letters from the E produces the letter J. The Z with a numerical value of 26 has 13 as its largest factor. Counting 156 letters ( 12 * 13) has the effect of wrapping around the alphabet 6 complete times and ending at J. The encoded solution for the letter set B, G, I is E J J.INPUT : There will be 5 input lines. Each will consist of a series of upper case letters and will end with a $. You may enter the letters one at a time. The commas shown are for clarification and do not have to be entered. The $ is not encoded.OUTPUT: For each set of letters, print the results of the encoding.SAMPLE INPUT SAMPLE OUTPUT1. B,G,Z,$ 1. E J J2. A,R,J,$ 2. C O T3. A,C,S,L,$ 3. C I E CNote: Students have 72 hours in which to submit a solution. Students may not consult any person for assistance. The program must accept all the data and print all the solutions in one RUN of the program. We suggest that you print the solution for each input prior to entering the next input since, if the program stops, you will not be allowed to enter the remaining data.. Make sure that you put your name, your school name and your division at the top of your program file. Advisors must send to ACSL the program file of all students who score a 10 for the contest.INTERMEDIATE DIVISION PROGRAMMING PROBLEMTEST DATATEST INPUTSTEST OUTPUTS1. A,B,C,$ 1. C G M2.L,U,C,K,$ 2. Y E K A3.A,E,I,O,U,$ 3. C M M K Q4.C,O,N,T,E,S,T,$ 4. G E C W G C W5.M,O,N,T,R,E,A,L,$ 5. Y W U O A K M K。

第1讲 程序和程序设计、算法、结构化程序设计方法


传统流程图常用的符号
例1.2 输入一个整数，将它倒过来输出
定义变量X

用自然语言描述：
① 输入一个整数送给x； ② 求x除以10的余数，结果送 给d，并输出d ； ③ 求x除以10的整数商，结果 送给x； ④ 重复② ，③步，直到x变为 零时终止。
输入一个数给X 否 x≠0? 是 d=x%10; 输出d; x=x/10;
肯尼思·汤普森和 丹尼斯·里奇
• 在计算机发展的历史上，大概没有哪个程序设 计语言像C那样得到如此广泛地流行；也没有哪 个操作系统像UNIX那样获得计算机厂家和用户的 普遍青睐和厚爱。它们对整个软件技术和软件产 业都产生了深远的影响。 • 而C和UNIX两者都是贝尔实验室的 Dennis Ritchie和 Kenneth Thompson设计、开发的。 • 他们两人共同获得1983年度的图灵奖。
1. 机器语言
• 由“0”和“1”组成的二进制表示的机器指令的集 合。
例如某种类型的计算机规定以“10000000”表示一个“加 法”操作，以“10010000”表示一个“减法”操作。
• 机器指令一般由操作码和操作数两个部分组成。
• 计算机硬件可以直接识别，因此，它的执行速度 比较快。
• 针对一种计算机所编写的机器语言程序，一般不 能在另一种类型的计算机上运行，而且程序的编 写难度较大，修改、调试也不方便，容易出错， 程序的直观性较差。
1.1 程序与程序设计
• 程序与程序设计
–程序是控制计算机运行的指令序列。 –程序设计就是设计、书写及检查程序的过程。
• 程序设计语言
–程序设计语言是软件系统的重要组成部分 – 程序设计语言是描述计算机指令的工具。 –各种程序设计语言有自己的语法、词汇。 –可分为机器语言、汇编语言和高级语言三类。

ACM 程序设计竞赛入门：第1讲 快速入门


2020/12/10
13
本类输入解决方案：
C语法：
scanf("%d",&n) ;
for( i=0 ; i<n ; i++ ) {
.... }
C++语法：
cin >> n;
for( i=0 ; i<n ; i++ )
{
....
}
2020/12/10
14
输入(3)：
输入不说明有多少个Input Block,但以某 个特殊输入为结束标志。 参见：本校OJ1000
第一讲 快速入门
2020/12/10
1
ACM题目特点:
严格的输入、输出格式；有偏差则不能AC；
追求高效简洁的算法 。即便算法是正确的， 但策略过于复杂，会导致超时；
测试数据庞大；即便算法是正确的，如果在程 序实现时出现误差都会被严密的测试数据查出 而把程序判定为错误的；
强调解决实际问题的能力。赛题与实际应用的 联系很紧密，很多试题被出题者描述成一个有 趣的故事。因此，读题能力、分析能力相当重 要。
2020/12/10
4
困惑：用C/C++的输入/输出？
一般来说，差别不是太大，习惯就好； cin,cout 使用方便；scanf, printf 控制灵 活，在效率上有优势； 不要混用。 千万不要把cout和printf混用，因为cout 是带缓冲的而printf不带，所以会使得输 出的数据顺序混乱。
8
本类输入解决方案：
C语法：
while(scanf("%d %d",&a, &b) != EOF)

《算法竞赛》课件1第1章 绪论


计算机程序设计语言的发展
4
高级语言
• 高级语言屏蔽了机器的细节，提高了语言的抽象层次，程序中可以采 用具有一定含义的数据命名和容易理解的执行语句。这使得在书写程 序时可以联系到程序所描述的具体事物。
计算机程序设计语言的发展
5
面向对象的语言
• 出发点：
▫ 更直接地描述客观世界中存在的事物(对象)以及它们之间的关系。
▫ 例如，石头、树木、汽车、房屋等都是人们在长期的生产和生活实践中抽象 出的概念。
• 面向对象方法中的"类"
▫ 具有相同属性和服务的一组对象的集合 ▫ 为属于该类的全部对象提供了抽象的描述，包括属性和行为两个主要部分。 ▫ 类与对象的关系：
犹如模具与铸件之间的关系，一个属于某类的对象称为该类的一个实例。
面向对象的方法 -> 面向对象的基本概念
12
封装
• 把对象的属性和服务结合成一个独立的系统单元。 • 尽可能隐蔽对象的内部细节。对外形成一个边界（或者说一道屏障）
，只保留有限的对外接口使之与外部发生联系。
面向对象的方法 -> 面向对象的基本概念
13
继承
• 继承对于软件复用有着重要意义，是面向对象技术能够提高软件开发 效率的重要原因之一。
▫ 是系统中用来描述客观事物的一个实体，它是用来构成系统的一个基本单 位。对象由一组属性和一组行为构成。
▫ 属性：用来描述对象静态特征的数据项。 ▫ 行为：用来描述对象动态特征的操作序列。
面向对象的方法 -> 面向对象的基本概念
11
类
• 分类——人类通常的思维方法 • 分类所依据的原则——抽象
▫ 忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而找出 事物的共性，把具有共同性质的事物划分为一类，得出一个抽象的概念。

第1讲续：程序等几个基本概念


编辑 file.c
编译 file.obj
连接 file.exe
执行 结果
言：需要先经过编译和连接程序 产生可执行文件的语言，如java/C/C++等 ->开发人员编译连接 • 解释型语言 解释型语言：不需要经过编译和连接的过 程，直接在特定的程序或环境下即可执行 的语言，如：JavaScript/Python等 ->自动编译连接
基本概念（三）
• 编 译
1）把高级语音的源代码转换成机器码的过程 2）之前还会进行前期处理 3）过程中会进行语法检查 4）编译器：完成编译动作的程序，最终生成目 目 标文件
• 链 接
将目标文件与所用到的函数库文件建立关联和连 接的过程，最终生产可执行文件
键盘输入 源程序 磁盘文件 目标文件 执行文件
基本概念（二）
•什么是程序？（有何作用） 什么是程序？
– 我们必须通过指令，指挥计算机执行我们想要它做 的动作 – 而依照顺序执行的一组指令就是程序
•什么是程序设计？ 什么是程序设计？
– 编写程序的过程
•什么是语言？ 什么是语言？
– 一种交流的工具
• 什么是程序设计语言？ 什么是程序设计语言？
– 是一种描述程序的工具，是用来表达（由人控制计算 机运行的）指令的一种方法
基本概念（一）
• 信 息 数、图形、图像、声音、视频、气味等。 • 数 据 是计算机程序处理的对象，可以是整数、实数、 字符，也可以是图像、声音等的编码 编码表示。 编码 • 数据类型 指数据的不同类别，主要有整型、实型、字符型、 字符串、布尔型、二进制数值等。 • 数据结构 指数据与数据间存在一种或多种特定关系。与数 据结构密切相关的便是数据的类型和数据的存放。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(2) for(k=1;k<=n;k++) { x=x+y; y=x+y; s=x+y; } “k=1”执行1次；“k<=n”与“k++”各执行n次；3个赋值语 句，每个赋值语句各执行n次；共执行5n+1次. 时间复杂度
为O(n).
1.5 算法复杂度的分析
例1-3 试计算下面三个程序段的执行频数
(3) for(t=1,k=1;k<=n;k++) { t=t*2; for(j=1;j<=t;j++) s=s+j; }
算法是解决“做什么”和“怎么做”的问题。即是为 解决一个问题而采取的方法和步骤。
1.2 简单算法举例
ቤተ መጻሕፍቲ ባይዱ
步骤1：先求1×2，得到结果2
步骤2：将步骤1得到的乘积2再乘以
3，得到结果6 步骤3：将6再乘以4，得24
步骤4：将24再乘以5，得120
1.2 简单算法举例
何为算法
“烧水泡茶”有如下五道工序： 1、烧开水2、洗茶壶3、茶杯4、拿茶叶5、泡茶。 烧开水、洗茶壶、茶杯，拿茶叶是泡茶的前提。其中烧开水需要15分 钟，洗茶壶需要2分钟，洗茶杯需要1分钟，拿茶叶需要1分钟，泡茶需 要1分钟。 下面是两种“烧水泡茶”的方法。 方法1： 第一步：烧水； 第二步：水烧开后，洗刷茶具，拿茶叶； 第三步：沏茶。 方法2： 第一步：烧水； 第二步：烧水过程中，洗刷茶具，拿茶叶； 第三步：水烧开后沏茶。
1.4 算法的表示
例5： “打印x的绝对值” ，用伪代码表示算法。
用英文伪代码表示：
IF x is positive THEN print x ELSE print -x
也可以用汉字伪代码表示：
若 x为正 打印 x
打印 -x
也可以中英文混用，如：
IF x print x ELSE print -x
一个算法的运行时间取决于算法所需执行的语句（运算）的
多少。 算法的时间复杂度通常用该算法执行的总语句（运算）的数 量级决定。
1.5 算法复杂度的分析
算法的执行频数的数量级直接决定算法的时间复杂 度。
1.5 算法复杂度的分析
(1) x=x+1; s=s+x; 2个语句各执行1次，共执行2次。时间复杂度为O(1)
2.1 经典算法——枚举法
（2）恒心、演练、举一反三
学习编程的过程是枯燥的过程，我们需要将学习算法当成是自己的乐趣
，只有做到持之以恒才能有机会学好。另外编程最注重实践，最害怕闭门造车
。每一个语法，每一个知识点，都要反复用实例来演练，这样才能加深对知识 的理解。并且要做到举一反三，只有这样才能对知识的深入理解。
（3）语言之争的时代更要学会坚持
例6：求5!用C语言表示。
N-S图为：
1 t
2 i
当i<=5
t*it
i+1i 输出t
#include <stdio.h> int main( ) { int i,t; t=1; i=2; while(i<=5) { t=t*i; i=i+1; } printf(″%d\n″,t); return 0; }
1.5 算法复杂度的分析
算法的复杂性越高，所需的计算机资源越多。 最重要的计算机资源是时间资源与空间资源。 需要计算机时间资源的量称为时间复杂度，需要计算机空 间资源的量称为空间复杂度。 时间复杂度与空间复杂度集中反映算法的效率。
1.5 算法复杂度的分析
一个算法的时间复杂度是指算法运行所需的时间。
// 统计解的个数
2.1 经典算法——枚举法
举例：完美综合式
案例提出：
把数字1,2,...,9这9个数字分别填入以下含加、减、乘、除
与乘方(^)的综合运算式中的9个□中
□^□+□□÷□□-□□×□=0 要求数字1,2,...,9这9个数字在式中出现一次且只出现一次， 且约定数字“1”不出现在乘、乘方的一位数中。
算法用N-S图表示，如右图。
1 i
输入ni、gi i+1i 直到i>50
练习：使用流程图表示算法。
是
1 i
gi≧80 否
输出ni,gi
i+1i 直到i>50
1.4 算法的表示
例3 流程图如下：
开始
Y 1 i 输出ni、gi 输入ni、gi i+1i N i>50 N i+1i i>50 Y gi≧80 N
1.3 算法的特性
有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 确定性 算法中的每一个步骤都应当是确定的，不能含糊。 输入 输出
有零个或多个输入，从外界获取必要信息。 有一个或者多个输出，得到问题的解。
有效性 每一个步骤有效执行，得到确定的结果。
1.4 算法的表示
算法的表示
自然语言
当型循环结构
直到型循环结构
1.4 算法的表示
N-S流程图（ N-S图） 由I. Nassi和Shneiderman提出的新的流程图形式，称为 N-S流程图。其三种基本结构的N-S图表示：
A Y
p
N B A
当p1成立 A
循环结构 （当型）
A 直到p2成立 循环结构 （直到型）
B
顺序结构
选择结构
1.4 算法的表示
23
1.4 算法的表示
用计算机语言表示算法
概念： 用计算机语言描述算法，就是用计算机语言编写程序。 计算机是无法识别流程图和伪代码的。只有用计算机语 言编写的程序才能被计算机执行。
特点：
设计算法的目的是为了实现算法。 用计算机语言表示算法，必须严格遵循所用的语言的语法 规则。
1.4 算法的表示
1.4 算法的表示
算法
广义地说，为解决一个问题而采取的方法和步骤，称为“算法”。
对同一个问题，可以有不同的算法。
计算机算法可分为两大类别：
数值运算算法，目的是求数值解。 非数值运算算法，包括的面十分广泛，最常见的是用于事务管理领 域。
注意：
写出了C程序，仍然只是描述了算法，并未实现算法。 只有运行程序才是实现算法。
2.经典算法
九大大算法思想
枚举算法思想 递推算法思想 递归算法思想 分治算法思想 贪心算法思想 试探法算法思想 迭代算法思想 动态规划算法思想 模拟算法思想
2.1 经典算法——枚举法
比较笨的枚举算法思想
枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件
判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法
1.4 算法的表示
例4 判定2000 - 2500年中的每一年是否闰年，并将结果输出 开始 。
2000year year不能被4整除 N
year不能被100整除
Y year不是闰年 Y
year不能被400整除
N
Y year是闰年 year+1year year>2500 N
N
year不是闰年
1.4 算法的表示
流程图的连接点举例
①
③
② ③ ③
位置 不够
防止 交叉
①
②
1.4 算法的表示
流程图表示三种基本结构
顺序结构
A
B
1.4 算法的表示
流程图表示三种基本结构
选择结构 Y N Y N
p
p
A
B
A
1.4 算法的表示
流程图表示三种基本结构
循环结构
p1 Y A
N
A N p2 Y
计算机程序设计竞赛
信科系专职教师：赵小蕾
邮箱：zxl_xinhua@
课程介绍及要求
课程类别：全校公选课 总学时数：36（实操课） 开课目的：为信息科学系——竞赛项目：第六届“蓝 桥杯软件人才与设计大赛”培养人才。
主要培养学生解决实际问题的编程能力、培养学生的
创新思维。程序是自己设计出来的，而不是某个固定 的方程式。
1.5 算法复杂度的分析
算法的空间复杂度是指算法运行的存储空间，是实现算 法所需的内存空间的大小。 一个程序运行所需的存储空间通常包括固定空间需求与
可变空间需求两部分。
1. 固定空间需求包括程序代码、常量与静态变量等所占 的空间。 2. 可变空间需求包括局部作用域非静态变量所占用的空 间、从堆空间中动态分配的空间与调用函数所需的系
“t=1”与“k=1”各执行1次；“k<=n”与“k++”各执行n次；“t=t*2”执行n次； “j=1”执行n次；“j<=t”、“j++”与内循环的赋值语句“s=s+j”各执行频数为: 总的执行频数为：
1.5 算法复杂度的分析
在估算算法的时间复杂度时，为简单计，以后只考虑内循环 语句的执行频数，而不细致计算各循环设计语句及其它语句的执 行次数，这样简化处理不影响算法的时间复杂度。 例1-4 估算以下程序段所代表算法的时间复杂度。 for(k=1;k<=n;k++) for(j=1;j<=k;j++) { x=k+j; s=s+x;} 每个赋值语句执行频率为n(n+1)/2, 该算法的时间复杂度 为:O(n^2)
输出 year 闰年
1.4 算法的表示
用伪代码表示算法 概念：
伪代码是用介于自然语言和计算机语言之间的文字和符
号，用来描述算法。
特点：
如一篇文章，自上而下地写下来。每一行(或几行)表示 一个基本操作。它不用图形符号，因此书写方便 、格式紧 凑，也比较好懂，也便于向计算机语言算法(即程序)过渡 。