基础+数据结构+算法ppt课件.ppt
《基础+数据结构+算法ppt课件.ppt》由会员分享,可在线阅读,更多相关《基础+数据结构+算法ppt课件.ppt(70页珍藏版)》请在三一办公上搜索。
1、信息学奥林匹克竞赛,任课教师:郑文云、岳水平Tel:13518080777、13178906711,一、单项选择题(共10题,每题1.5分,共计15分。每题有且仅有一个正确答案.)。二、不定项选择题(共10题,每题1.5分,共计15分。每题正确答案的个数大于或等于 1。多选 或少选均不得分)。三、问题求解(共2题,每题5分,共计10分)四、阅读程序写结果(共4 题,每题8 分,共计32 分)五、完善程序(前5空,每空2分,后6空,每空3分,共28分),全国青少年信息学奥林匹克联赛初赛试题题型(时间:2小时),一、奥赛相关简介和语言,NOIP:全国青少年信息学奥林匹克联赛(10-11)冬令营:全
2、国青少年信息学奥林匹克竞赛冬令营(2-3)NOI:全国青少年信息学奥林匹克竞赛 (7-8)(4男1女)网上同步赛夏令营:全国青少年信息学奥林匹克竞赛夏令营选拔赛:选拔参加国际信息学奥林匹克竞赛的中国代表队的竞赛 (4-5)(noi前20名)APIO2007:亚洲与太平洋地区信息学奥林匹克 IOI:国际奥林匹克竞赛(8-9),1、竞赛简介,一、奥赛相关的知识和语言,free pascal 、gcc/g+ (c+),2、竞赛语言,二、计算机的产生和发展,世界上的第一台计算机(ENIAC)于1946年诞生在美国宾夕法尼亚大学,第一代电子管计算机,始于1946年,结构上以CPU为中心,使用计算机语言,
3、速度慢,存储量小,主要用于数值计算; 第二代晶体管计算机,始于1958年,结构上以存储器为中心,使用高级语言,应用范围扩大到数据处理和工业控制; 第三代中小规模集成电路计算机,始于1964年,结构上仍以存储器为中心,增加了多种外部设备,软件得到了一定的发展,文字图象处理功能加强; 第四代大规模和超大规模集成电路计算机,始于1971年,应用更广泛,很多核心部件可集成在一个或多个芯片上,从而出现了微型计算机,二、计算机的产生和发展,我国从1956年开始电子计算机的科研和教学工作,1983年研制成功1亿/秒运算速度的“银河”巨型计算机,1992年11月研制成功10亿/秒运算速度的“银河II”巨型计算
4、机,1997年研制了每秒130亿运算速度的“银河III”巨型计算机。1999年,银河四代巨型机研制成功。 2000年,我国自行研制成功高性能计算机神威I,其主要技术指标和性能达到国际先进水平。我国成为继美国、日本之后世界上第三个具备研制高性能计算机能力的国家。,三、计算机系统及工作原理,1.计算机的系统组成,计算机系统由软件和硬件两部分组成。,输入输出:触摸屏,三、计算机系统及工作原理,存储器:具有记忆功能的物理器件,用于存储信息。存储器分为内存和外存内存是半导体存储器(主存):它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器(Cache);ROM:只能读,不能用普通方法写入,
5、通常由厂家生产时写入,写入后数据不容易丢失,也可以用特殊方法(如紫外线擦除(EPROM)或电擦除(EEPROM_)存储器);RAM:可读可写,断电后内容全部丢失;Cache:因为CPU读写RAM的时间需要等待,为了减少等待时间,在RAM和CPU间需要设置高速缓存Cache,断电后其内容丢失。 外存:磁性存储器软盘和硬盘;光电存储器光盘,它们可以作为永久存器; 存储器的两个重要技术指标:存取速度和存储容量。内存的存取速度最快(与CPU速 度相匹配),软盘存取速度最慢。存储容量是指存储的信息量,它用字节(Byte)作为基本单位,,三、计算机系统及工作原理,1.计算机的系统组成,计算机系统由软件和硬
6、件两部分组成。,Linux、unix、DOS、NT等,三、计算机系统及工作原理,到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计算机自动存取指令(计算机可执行的命令=操作码+操作数)并执行它。,2.计算机的工作原理,三、计算机系统及工作原理,2.计算机的工作原理,(1)运算器用于进行加、减、乘、除等算术运算以及逻辑运算。运算器是决定计算机运算速度的主要环节。(2)控制器用于控制并协调计算机各部分工作流程与顺序。(3)存储器存储器由许多存储单元,用于存储程序和数据。(4)输入设备用于把程序及原始数据转换成计算机可以识别的代码并送入存储器中保存。(5)输
7、出设备用于送出计算机运行的结构及人们所需要的信息。,四、计算机中有关数及编码,在计算机中,所有的数据、指令以及一些符合等都是用特定的二进制代码表示的。,b:一位二进制码叫做一比特(bit),它是计算机能处理和存储的最小单位。字节(B):八位二进制码叫做一个字节(Byte),计算机的存 储容量就是以字节为单位计算的。计算机中存贮容量的单位:字节(Byte),用 B 表示: 字节1B=8b 千字节1KB=1024B 兆字节1MB=1024KB 千兆1GB=1024MB,四、计算机中有关数及编码,1.二进制数的运算法则,0+0=0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*0=
8、0 1*1=1,2.十进制与二进制、八进制、十六进制数之间的相互转换,(1)数的进制与基数,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,(2)数的权 不同进制的数,基数不同,每位上代表的值的大小(权)也不相同。,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,(3)十进制数转换任意进制 a) 将十进制整数除以所定的进制数,取余逆序。,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,b)将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分,直到为零或精确到小数点后几位。,(3)十进制数转换任
9、意进制 a) 将十进制整数除以所定的进制数,取余逆序。,四、计算机中有关数及编码,2.十进制与二进制、八进制、十六进制数之间的相互转换,(4)任意进制的数转换十进制 按权值展开:,一个数在计算机内被表示的二进制形式称为机器数,该数称为这个机器数的真值。,机器数具有下列特点:,(a)由于计算机设备上的限制和操作上的便利,机器数有固定长度; 如:一个8位机器数,所能表示的无符号整数的最大值是: “11111111”,即十进制数255。,(b)机器数把其真值符合数字化; 通常是用机器数中规定的符号位(一般是最高位)取0或1, 来分别表示其真值的正或负。 如:一个8位机器数,其最高位是符号位,那么在定
10、点整数 原码表示情况下,对于00101110 和 10010011 其真值分别为十进制:46 和 19,(c)机器数中,采用定点或浮点方式来表示小数点的位置。,四、计算机中有关数及编码,3、原码、反码和补码,机器数的形式是人们规定的,原码和补码是最常见的机器数形式或称数的编码方式。,(a)原码,整数X的原码是指:其符号位的0或1表示X的正或负,其数值部分就是X绝对值的二进制表示。通常用X原表示X的原码。,如:假设机器数的位数是8,其中最高位是符号位,其余是数值部分,则: +17原00010001 39原10100111,注:0原00000000 0原10000000 零的原码不唯一,有“正零”
11、和“负零”之分。,四、计算机中有关数及编码,(b)反码,在反码表示法中,正数的表示方式与原码相同;负数的补码是把其原码除符号位外的各位取反(即0变1,1变0)。通常用X反表示X的反码。,如: 45反 45原00101101,32原10100000 则32反11011111,四、计算机中有关数及编码,3、原码、反码和补码,(c)补码,在进行减法运算时,数的原码表示显得不方便,故引进了数的补码表示。,正数的补码与其原码相同;负数的补码是在其反码的最低有效位上加1。用X补表示X的补码。,如: +14补+14原00001110,-36原10100100 而-36反11011011 则-36补11011
12、100,数0的补码表示是唯一的,即0 0补 0原00000000,利用公式:X补+ Y补=X Y补可以把加法和减法统一成加法。,四、计算机中有关数及编码,3、原码、反码和补码,4.数的定点和浮点表示,数的补码表示解决了带符号数的运算问题。至于小数点的处理,计算机中通常用定点表示法或浮点表示法来解决。,(a)定点表示法,定点表示法是把小数点约定在机器数的某一固定的位置上。,如果小数点约定在符号位和数值的最高位之间,这时所有参加运算的数的绝对值小于1,即为定点纯小数。,如: X补01010000,这时X0.625,如果小数点约定在数值的最低位之后,这时所有参加运算的数都是整数,即为定点整数。,如:
13、 X补11010000,这时X-48,四、计算机中有关数及编码,由于M补01111111,即M271127 N补10000000,即N 27128所以8位定点整数(补码表示)的范围是128127,16位定点整数(补码表示)的范围是3276832767,定点数在使用时,所有原始数据事先都要按比例化成纯小数或整数,运算结果又要按比例转换成实际值。,四、计算机中有关数及编码,4.数的定点和浮点表示,(a)定点表示法,(b)浮点表示法,任何一个二进制数N,都可写成2e*t的形式,即N 2e*t如:1010.11可写成2100*0.101011即1010.11 2100*0.101011e称为N的阶码,
14、是一个二进制整数,t称为N的尾数,是一个二进制纯小数,机器数用阶码和尾数两部分表示,称为浮点表示法。一般规定: 阶码是定点整数,尾数是定点纯小数。它们可采用原码、补码或其他编码表示。,四、计算机中有关数及编码,4.数的定点和浮点表示,如:一个数X用8位机器数浮点表示如下,其中前三位表示阶符 和阶码值,后五位表示尾符和尾数值,它们都用原码表示:,1 10 0 1100阶符 阶码 尾符 尾值,则X22*0.11000.0011000.1875,浮点表示中,尾数的大小和正负结点了所表示的数的有效数字和正负;阶码的大小和正负决定了小数点的位置;因此机器数小数点的位置随阶码的变化而浮动。,为了使运算中不
15、丢失有效数字,提供运算精度,计算机中的浮点表示,通常采用改变阶码来达到规格化数的表示。注:规格化要求尾数值的最高位必须是1。,如:在16位机器浮点表示中,取前六位为阶码(其中第一位为 是阶符), 后十位为尾数(其中第一位为尾符),它们都用 原码表示,那么它能表示的最大数和最小数分别为:,0111110111111111即231(129)约2.14329*1090111111111111111即231(129)约2.14329*109,可见比相同位数机器数定点表示的范围大得多。,5、ASCII码和BCD码,a、ASCII码,字符或字符的组合、控制功能符号等,在计算机内部,必须用一种二进制代码来表
16、示。国际上广泛使用的是:美国标准信息交换代码(Amenrican Standand Codefor Information Interechange)简称:ASCII,ASCII码是7位二进制编码,它可以表示27128个字符。,四、计算机中有关数及编码,16进制表示ASCII码AZ:415Aaz:617A09:30-39,一个字符的ASCII码可用二进制表示,也可用八进制、十进制、十六进制表示。,四、计算机中有关数及编码,5、ASCII码和BCD码,a、ASCII码,计算机在进行字符处理和传送时,一般在7位的ASCII码左边附加一个奇偶校验位,组成8位代码进行存储和传送。,在偶校验系统中,用附
17、加的偶数校验位使所有字符的8位代码都有偶数个1。,在奇校验系统中用附加的奇数校验位使所有字符的8位代码都有奇数个1。,如:“R”和“S”的ASCII码为:1010010 和1010011 则偶校验: 11010010 和 01010011 奇校验: 01010010 和 11010011,由于标准的7位ASCII码所表示的字符较少,设计扩充了的8位二进制ASCII码,可表示256个字符。,b、BCD码,十进制数在键盘输入和打印、显示输出时,往往是将各个数字以ASCII码来表示的。但在计算机内运算时,是以二进制进行的。,为了便于转换,人们设计了二进制编码来表示十进制,称二-十进制码,即BCD码。
18、,BCD码是用四位二进制代码来表示一位十进制码。,从16个四位二进制代码00001111中,只须选择其中的10个作为十进制数的10个数字的代码就可以了。这样就有多种BCD码:8421码、2421码、余3码、格雷码等。,8421码最常用,它是用四位二进制代码来表示十进制数字,其特点是二进制代码本身的值就是它对应的十进制数字的值。所以8421码也称BCD码。,如:十进制315可用BCD码表示为001100010101,注:用BCD码表示的数,形式上像二进制数,但不是真正的 二进制数。 (315)10(100111011)2,五、逻辑运算,1.逻辑运算 not(逻辑非) :你真我假 and(逻辑与)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基础 数据结构 算法 ppt 课件
链接地址:https://www.31ppt.com/p-1877396.html