NOIP初赛复习(十九)计算机信息处理

基于计算机的信息处理过程

1、信息采集和表示:数字、字符、声音、图形、图像(计算机编码技术)
2、信息存储:存储器的分类、管理、访问等(计算机软硬件系统)
3、信息管理:采集、处理、输出(计算机程序设计)
4、信息组织:(计算机数据库技术)
5、信息传输、信息检索:(计算机网络技术)


计算机中数字的表示方法

1、数制转换:NOIP初赛复习(一)数制转换>>>

二进制:(1001)2或1001B
八进制:(237)8或237Q
十六进制:(5FE)16 或5FEH
NOIP初赛复习(十九)计算机信息处理-少儿编程网
2、原码、反码、补码:NOIP初赛复习(八)原码、补码、反码>>>

[+3]原码  = 0000,0011     [ -3]原码 = 1000,0011
[+3]反码 = 0000,0011      [ -3]反码 = 1111,1100
[+3]补码  = 0000,0011      [ -3]补码 = 1111,1101

NOIP初赛复习(十九)计算机信息处理-少儿编程网


计算机中字符的表示方法

字符是各种文字和符号的总称,包括各国家文字、标点符号、图形符号、数字等。字符集是多个字符的集合,字符集种类较多,每个字符集包含的字符个数不同。常见字符集名称:ASCII字符集、GB2312字符集、BIG5字符集、GB18030字符集、Unicode字符集等。

目前微机中普遍利用的字符编码是ASCII码,它是美国信息交换标准代码,也是国际上通用的微型机编码。ASCII码由8位二进制数组成,其中最高位为较验位,用于传输过程检验数据正确性。其余7位二进制数表示一个字符,共有128种组合。如回车的ASCII码为 0001101(13),空格的ASCII码为0100000(32),“0”的ASCII码为0110000(48),“A”的ASCII码为1000001(65),“a”的ASCII码为1100001(97)。

我国据此制定GB1988,GB1988用52个英文大小写字母,32个标点符号、运算符和34个控制字符,共128种。每个字符用一个7位二进制数来表示,在微型机内用一个字节来存储,最高位D7恒为0。

计算机中汉字的表示方法

1、汉字的编码

由于汉字具有特殊性(非拼音文字),因此汉字的输入、输出、存储和处理过程中所使用的汉字代码不相同。计算机处理汉字信息的前提条件是对每个汉字进行编码,对于不同的部位存在多种不同的编码方式。系统工作时,汉字信息在系统的各部分之间传送,到达某个部分就要用该部分所规定的汉字代码表示汉字。

2、汉字的交换码

交换码用于汉字外码和内码的交换。我国于1981年颁行的《信息交换用汉字编码字符集·基本集》(代号为GB2312—80)是交换码的国家标准,所以交换码也称为国标码。交换码规定了每个字符由一个2个字节的代码组成。每个字节的最高为恒为0,其余7位用于组成各种不同的码值。一个汉字所在的区号与位号简单地组合在一起就构成了汉字的一种外码—“区位码”。用两个字节表示,高字节表示区号,低字节表示位号。

3、汉字的机内码

在计算机内部传输、存储、处理的汉字编码称为汉字机内码。通常利用字节的最高位来区分某个码值是代表汉字还是ASCII字符,最高位为“1”视为汉字符,为”0”是为ASCII字符。机内码就是在国标码的基础上将两个字节的最高位一律由“0”改“1”。

4、汉字的输入码

为了利用计算机上现有的标准西文键盘来输入,必须为汉字设计输入编码。输入编码也称外码。归纳数量众多的输入码有四大类:数字编码、拼音码、字形码和音形码。其中,目前应用最广泛的是拼音码和字形码。无论采用哪一种汉字输入法,当用户向计算机输入汉字时存入计算机中的总是它的机内码,与所采用的输入法无关。

NOIP初赛复习(十九)计算机信息处理-少儿编程网

5、汉字的字形码

是表示汉字字形信息(汉字的结构、形状、笔划等)的编码,用来实现计算机对汉字的输出(显示、打印)。由于汉字是方块字,因此字形码最常用的表示方式是点阵形式,有16 ×16点阵、24×24点阵、32× 32点阵、48 ×48点阵等等。例如,16 ×16点阵的含义为:用256(16 ×16=256)个点来表示一个汉字的字形信息。每个点有“亮”或“灭”两种状态,用一个二进制位的“1”或“0”来对应表示。因此,存储一个16 ×16点阵的汉字需要256个二进制位,共32个字节。汉字字库由所有汉字的字模码构成,一个汉字字模码究竟占多少个字节由汉字的字形决定。常用的字模码有4种:

简易型16*16点阵,字模码为32字节

普通型24*24点阵,字模码为72字节

提高型32*32点阵,字模码为128字节

精密型48*48点阵,字模码为288字节

如何计算一个汉字点阵的字节数?汉字字模就是用0、1表示汉字的字形,将汉字放入n行*n列的正方形内,该正方形共有n^2个小方格,每个小方格用一位二进制表示。

NOIP初赛复习(十九)计算机信息处理-少儿编程网

6、BIG-5码

BIG-5码是通行于台湾、香港地区的一个繁体字编码方案,俗称“大五码”。

综上所述,汉字的处理过程就是这些代码的转换过程:

输入→输入码(外码)→键盘管理程序(输入法)→汉字机内码(内码)→字形码→输出


计算机中多媒体的表示方法

多媒体信息包括声音、图形(矢量图)、图像(静态图像—位图、视频图像)等,多媒体信息要为计算机处理,须首先数字化。

1、声音信息的数字化

声音是通过空气传播的一种连续的波(声波),声波是一种模拟信号。

NOIP初赛复习(十九)计算机信息处理-少儿编程网

模拟信号是在时间和幅度上都是连续变化的信号,而数字信号是指在时间和幅度上都是离散的信号。声音信号数字化的过程:

模拟声音信号→采样→量化→编码→数字声音信号

采样:在某些特定的时刻对这种模拟信号进行测量叫做采样(Sampling),采样所得到的信号称为离散时间信号,离散时间信号的特点: 时间上离散,幅度上连续。

例如:输入电压的范围是0.0~0.7V,在t1时刻采样得到的电压值可以是0.2718V。

量化:把信号幅度取值的数目加以限定,由有限个数值组成的信号就称为离散幅度信号。上例中在t1时刻采样得到的电压值 0.2718V,量化后就可以近似为0.3V。显然,量化后的数值位数越长,精确度就越高。

编码:用预先规定的方法将文字、数字或其他对象编成数码,或将信息、数据转换成规定的电脉冲信号。是用少量的基本符号,通过简单的组合规则来表示大量复杂的信息。在计算机内部,信息只有经过数字化编码后才能表示、存放和传递。

声音信号的数字化就是将连续变化的音频信号转换为时间和幅度都是离散的数字表示的信号。

NOIP初赛复习(十九)计算机信息处理-少儿编程网

采样频率:单位时间里的采样次数。

奈奎斯特理论(Nyqust theory):如果采样频率不低于信号最高频率的两倍,就能把以数字表达的声音还原成原来的声音。例:话音信号的最高频率为3400Hz,若采样频率为8000Hz,就能以数字声音还原原来的声音。

采样精度:表示采样点幅值的二进制位数,也叫样本位数或位深度。用声音样本的位数(bit)表示。

采样频率越高,采样精度越高,信号失真度越小,所得数据占用的存储空间越大。

声音文件的数据量=采样频率×样本精度×声道数×时间,例:设采样频率为8kHz,样本精度为8位,1分钟双声道声音文件的数据量为:

8(bit)*8kHz*2(声道数)*60(秒)/8=960kB

2、图像信息的数字化

图像是自然界的景物通过人的视觉器官在大脑中留下的印象,是连续变化的信息。

空间坐标位置和景物明暗程度均是连续变化的。计算机中的图像都是数字图像。

图像的数字化过程:采样→量化→编码

采样:空间连续坐标(x,y)的离散化→将图像变为若干个点→像素点

量化:幅值f(x,y)的离散化→灰度级的整量(景物的明暗程度或色彩度)→用若干位二进制码表示一个像素点的灰度值

数字图像:空间上和灰度级上都离散的图像。例:对连续图像在x、y方向上均取N个等间隔的采样,就变成N×N个像素点组成的图像,对每一个像素点的灰度(或色彩)进行整量,就得到一个N×N的数组。

NOIP初赛复习(十九)计算机信息处理-少儿编程网

图像采样的点数称为图像分辨率,用点的“行数×列数”表示。例:数码像机的图像分辨率1024×768、2400×3000等。

表示每个像素颜色使用的二进制位数称为像素深度或位深度。

对相同尺幅的图像,如果组成该图的像素数目越多,图像的分辨率越高;像素深度值越大,能表示的颜色数越多。图像看起来就越逼真。图像文件占用的存储空间越大。

常见的像素深度有:1位(黑白图像),4位(16色或16级灰度图像),8位(256色或256 级灰度图像),24位(真彩色图像)——可以表示224种颜色。

图像文件大小的估算:图像的分辨率和像素位深度决定了图像文件的大小。

图像文件的大小=位深度×像素数,例:一幅640×480的图像,位深度是24位,则文件大小为:

24(bit)/8(bit/Byte)×640(列)×480(行)=921600B(Bytes)≈900kB

图像文件格式是图像数据在文件中的存放形式。主要的图像文件格式有:

位图文件(Bitmap-File,BMP):一种不压缩的格式,占有较大存储空间,但图像质量较高,没有数据损失。

GIF (Graphics Interchange Format)文件:压缩效率高、占用的存储空间很小。适合存储颜色较少的卡通图像、徽标等手绘图像。

JPEG(JointPhotographicExpertsGroup)文件:相应的文件存储格式为jpg格式,适合存储色彩丰富的照片。

3、图形(矢量图)信息的数字化

用计算机程序来表示一幅图,实际上是用数学的方法来描述一幅图。矢量图像文件所占空间较小,旋转、放大、缩小、倾斜等变换操作容易,且不变形、不失真;不存在采样分辨率问题,只与显示的尺寸及显示分辨率有关;矢量图通常比位图节省存储空间;矢量图适合于表示简单的图形。


计算机程序设计语言

编制程序的过程称程序设计。书写程序用的“语言”叫做程序设计语言即计算机语言。计算机语言通常是一个能完整、准确和规则地表达人们的意图,并用以指挥或控制计算机工作的“符号系统”。

一般的计算机目前还不能在人类的自然语言上直接操作,用计算机解决实际问题,必须对所要解决的问题周密考虑一个明确的处理方法(算法),再使用计算机能理解的计算机语言编制成程序,然后通过输入设备才能告诉计算机该怎么去做。

计算机语言通常分为三类:机器语言、汇编语言和高级语言

1、机器语言

机器语言是指一台计算机全部的指令集合,由“0”和“1”组成的二进制数指令序列,运算效率是所有语言中最高的。机器语言,是第一代计算机语言。

机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活、直接执行和速度快等特点。不同型号的计算机其机器语言是不相通的,按着一种计算机的机器指令编制的程序,不能在另一种计算机上执行。

2、汇编语言

汇编语言用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串。

比如,用“ADD”代表加法,“MOV”代表数据传递等等。汇编语言,是第二代计算机语言,如:PUSH AX、PUSH BX、POP AX、ADD CX,BX等。

为了克服机器语言难读、难编、难记和易出错的缺点,人们就用与代码指令实际含义相近的英文缩写词、字母和数字等符号来取代指令代码。所以说,汇编语言是一种用助记符表示的仍然面向机器的计算机语言,亦称符号语言。由于汇编语言是面向具体机型的,仍离不开具体计算机的指令系统,因此,对于不同型号的计算机,有着不同的结构的汇编语言,而且,对于同一问题所编制的汇编语言程序在不同种类的计算机间是互不相通的。汇编语言是低级语言,使用起来还是比较繁琐费时,通用性也差。但是,汇编语言用来编制系统软件和过程控制软件,其目标程序占用内存空间少,运行速度快,有着高级语言不可替代的用途。

3、高级语言

计算机事业的发展,促使人们去寻求一些与人类自然语言相接近且能为计算机所接受的语意确定、规则明确、自然直观和通用易学的计算机语言。这种与自然语言相近并为计算机所接受和执行的计算机语言称高级语言。高级语言是面向用户的语言。无论何种机型的计算机,只要配备上相应的高级语言的编译或解释程序,则用该高级语言编写的程序就可以通用。

高级语言普遍的有BASIC、Pascal、C、C++、VC、VB、Delphi、JAVA等。与机器语言、汇编语言相比,高级语言的主要好处包括:

1、高级语言接近算法语言,易学、易掌握;
2、高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;
3、高级语言远离机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可移植性好,重用率高;
4、自动化程度高,开发周期短。

计算机并不能直接地接受和执行用高级语言编写的源程序,源程序在输入计算机时,通过“翻译程序”翻译成机器语言形式的目标程序,计算机才能识别和执行。这种“翻译”通常有两种方式,即编译方式和解释方式。

编译方式:如果所使用的翻译的机制是将所要翻译的程序代码作为一个整体翻译,并之后运行内部格式,那么这个翻译过程就称为编译。因此,一个编译器是一个将可阅读的程序文本(叫做源代码)作为输入的数据,然后输出可执行文件(object code)。所输出的可执行文件可以是机器语言,由计算机的中央处理器直接运行,或者是某种模拟器的二进制代码。PASCAL、FORTRAN、COBOL等高级语言执行编译方式。

解释方式:如果程序代码是在运行时才即时翻译,那么这种翻译机制就被称作解释。经解释的程序运行速度往往比编译的程序慢,但往往更具灵活性,因为它们能够与执行环境互相作用。BASIC语言以执行解释方式为主。

BASIC语言

BASIC语言全称是 Beginner’s allPurpose Symbolic Instruction Code,意为“初学者通用符号指令代码“。1964年由美国达尔摩斯学院的基米尼和科茨完成设计并提出了BASIC语言的第一个版本,经过不断丰富和发展,现已成为一种功能全面的中小型计算机语言。BASIC易学、易懂、易记、易用,是初学者的入门语言,也可以作为学习其他高级语言的基础。BASIC有解释方式和编译方式两种翻译程序。

PASCAL语言

PASCAL是一种结构程序设计语言,由瑞士苏黎世联邦工业大学的沃斯(N.Wirth)教授研制,于1971年正式发表。是从ALGOL60衍生的,但功能更强且容易使用。目前,作为一个能高效率实现的实用语言和一个极好的教学工具,PASCAL语言在高校计算机软件教学中一直处于主导地位。Pascal(B.Pascal)是十七世纪法国著名数学家,他于1642年曾发明现代台式计算机的雏型机—加减法计算机。PASCAL 具有大量的控制结构,充分反映了结构化程序设计的思想和要求,直观易懂,使用灵活,既可用于科学计算,又能用来编写系统软件,应用范围日益广泛。

C语言

C语言是美国AT&T(电报与电话)公司为了实现UNIX系统的设计思想而发展起来的语言工具。C语言的主要特色是兼顾了高级语言和汇编语言的特点,简洁、丰富、可移植。相当于其他高级语言子程序的函数是C语言的补充,每一个函数解决一个大问题中的小任务,函数使程序模块化。C语言提供了结构式编程所需要的各种现代化的控制结构。C语言是一种通用编程语言,正被越来越多的计算机用户所推崇。使用C语言编写程序,既感觉到使用高级语言的自然,也体会到利用计算机硬件指令的直接,而程序员却无需卷入汇编语言的繁琐。

目前,程序设计语言及编程环境正向面向对象语言及可视化编程环境方向发展,出现了许多第四代语言及其开发工具。如微软公司(Microsoft)开发的 Visual 系列(VC++、VB、FoxPro) 编程工具及 Power Builder 等,目前已经在国内外得到了广泛的应用。

从应用角度来看,高级语言可以分为基础语言、结构化语言和专用语言。

1、基础语言

基础语言也称通用语言。它历史悠久,流传很广,有大量的已开发的软件库,拥有众多的用户,为人们所熟悉和接受。属于这类语言的有 FORTRAN、COBOL、BASIC、ALGOL等。

2、结构化语言

20 世纪 70 年代以来,结构化程序设计和软件工程的思想日益为人们所接受和欣赏。在它们的影响下,先后出现了一些很有影响的结构化语言,这些结构化语言直接支持结构化的控制结构,具有很强的过程结构和数据结构能力。PASCAL、C、Ada 语言就是它们的突出代表。

3、专用语言

是为某种特殊应用而专门设计的语言,通常具有特殊的语法形式。一般来说,这种语言的应用范围狭窄,移植性和可维护性不如结构化程序设计语言。随着时间的发展,被使用的专业语言已有数百种,应用比较广泛的有 APL 语言、Forth 语言、LISP 语言。

从描述客观系统来看,程序设计语言可以分为面向过程语言和面向对象语言。

1、面向过程语言

以“数据结构+算法”程序设计范式构成的程序设计语言,称为面向过程语言。前面介绍的程序设计语言大多为面向过程语言。

2、面向对象语言

以“对象+消息”程序设计范式构成的程序设计语言,称为面向对象语言。比较流行的面向对象语言有 Delphi、Visual Basic、Java、C++等。

程序设计语言的历史

二十世纪四十年代当计算机刚刚问世的时候,程序员必须手动控制计算机。当时的计算机十分昂贵,唯一想到利用程序设计语言来解决问题的人是德国工程师楚泽(Konrad Zuse)。第一个写程序的人:Ada Lovelace。常见的程序设计语言包括:APL、A+和J、Ada、汇编语言、AWK、Basic、Fortran、VBScript、Brainfuck、C、C++、C#、Clipper、COBOL、dBase、PASCAL、Delphi、Forth、FoxPro、F#、Fava、IDL、Java、JavaScript、J#、LISP、Lua、LOGO、Modula、Nuva、Perl、PHP、PL/I、Prolog、Python、R、Ruby、Scheme、Smalltalk、SQL、Tcl/Tk、Visual Basic、Visual FoxPro、XML等。

程序设计语言的发展趋势

程序设计语言是软件的重要方面。它的发展趋势是模块化、简明性和形式化。

1、模块化:不仅语言具有模块成分,程序由模块组成,而且语言本身的结构也是模块化的。

2、简明性:涉及的基本概念不多,成分简单,结构清晰,易学易用。

3、形式化:发展合适的形式体系,以描述语言的语法、语义、语用。


信息学竞赛(C++)中常用STL结构与函数

Sort

Sort函数是用于给一个数组进行排序,在algorithm库里。

使用方法为sort(v.begin(),v.end(),cmp)),这里的v.begin()是开始的指针位置,v.end()是结束的指针位置(这里的表示是左闭右开,也就是说v.end()并不在排序内容里),cmp则是可要可不要,但如果使用的是自定义类型且没有重载运算符的话就一定需要。

这个数组的类型可以是自定义类型或者STL中的vector,但需要注意的是如果采用的是自定义类型则需要重载运算符(也可以如上面说的一样用cmp)。

Low bound

lower_bound(v.begin(),v.end(),c)可以在一个有序数组当中找出刚好大于或等于c的数,在algorithm库里。

同样地,可以使用自定义类型,用法与sort相类似。

这里,还有一个比较类似的upper_bound函数,这个函数则是在有序数组中找出刚好大于c的数。

Nextpermutation

next_permutation(v.begin(),v.end())可用于求出当前v数组序列的下一个排列,在algorithm库里。

这里所指的排列可以不仅仅是全排列:比如说数组存储1 3 5,用了这个函数之后也可以得到 1 5 3.

相对应的还有一个prev_permutation()函数,则用于求前一个排列。

这两个函数在找不到对应排列的时候都会返回false,但是仍会得到一个序列。

Vector

Vector代表的是一个不定长数组,就在vector库里。

Vector <Type> A;定义方式;

常用操作:

A.clear():清空;

A.push_back(a):尾部添加元素;

A.pop_back():尾部删除元素;

A.empty():检查是否为空,空返回true

Set

一个存储集合的容器,在set库里。

需要注意的是,set使用的自定义类型一定要重载“小于”运算符。

set <Type> A;定义方式;

常用函数:

A.insert(a):插入a;

A.erase(a):删除a;

A.find(a):查找a,如果查找成功,返回对应指针,查找失败返回尾指针;

A.begin(),A.end():返回头指针与尾指针,尾指针不存储具体内容

Map

存储一个从key到value的映射。某种意义上就是“广义”数组。在map库里。

map <Type1,Type2> A;Type1是key类型,Type2是value类型。

Type1必须重载“小于”运算符。(如果是自定义类型的话)

可以通过A[B]=C这种形式赋值,B为Type1,C为Type2。

常用函数:

A.clear():清空;

A.empty():判断是否为空;

A.insert(pair<Type1,Type2>(C,D)):插入,不建议这么写;

A.erase(B):删除,B可以是key值也可以是指针;

A.begin(),A.end():头指针,尾指针

Pair

一个包含两个可以不同的数据值的类型。

pair <Type1,Type2> A;

往往Type1,Type2都是标准类型,但如果是自定义类型,需要重定义运算符;

常用:

make_pair(t1,t2):赋值;

A.first,A.second:返回对应的值

Stack

模拟栈。在<stack>里。

stack <Type> A;

常用函数:

A.push(a):入栈;

A.pop():出栈;

A.top():返回栈顶元素(但不出栈)

Queue

模拟队列。在<queue>里。

queue <Type> A;

常用函数:

A.push(a):入队;

A.pop():出队;

A.front():返回队首元素(但不出队)

Priority queue

优先队列,一个类似于堆的数据结构。在<queue>里。

以O(logN)复杂度完成插入元素,删除最值,寻找最值。

Priority_queue <Type> A;

常用函数:

A.push(a):插入;

A.pop():删除最值(默认为最大值);

A.top():返回最值(但不删除)

Bitset

一个用于处理二进制串的“数组”。在<bitset>里。

bitset <n> A;n为长度;

支持所有位运算:<<,>>,&,|,^;

常用函数:

A.count():统计1的个数;

A.reset():清0;

A.set():全赋为1;

A.size():返回位数

*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
新手想参加信息学竞赛NOIP ,如何入门进阶?
新手想参加信息学竞赛NOIP ,如何入门进…
从NOIP三年榜单看全国信息学竞赛形势(2017终结版)
从NOIP三年榜单看全国信息学竞赛形势(2…
IOI金牌再传秘笈:水平不高怎么拿NOIP一等奖?
IOI金牌再传秘笈:水平不高怎么拿NOIP一…
杜博闻:信息学奥赛一等奖,获三所名校保送资格!
杜博闻:信息学奥赛一等奖,获三所名校…
这些参加信息学竞赛的娃高一就保送清华!
这些参加信息学竞赛的娃高一就保送清华!
【NOIP专栏】搜狗CEO王小川的传奇人生!
【NOIP专栏】搜狗CEO王小川的传奇人生!
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。