\(NOIP\)（全国青少年信息学奥林匹克竞赛）于2019年取消。取而代之的是由\(CCF\)推出的非专业级软件能力认证，也就是现在的\(CSP-J/S\)。作为一名于2019年1月入\(OI\)的蒟蒻\(OIer\)，没能参加\(NOIP\)是我一生的遗憾。但在遗憾之余，我不得不备战\(CSP\)的认证。而\(CSP\)非专业级认证的第一轮（也就是\(NOIP\)初赛）常常使某些大神\(OIer\)（就是对基础知识不太了解）无缘复赛...所以今天来盘一下初赛知识点，顺带着自己也学习一下......

图灵奖：由ACM（美国计算机协会）设立于1966年。是“计算机界的诺贝尔奖”。

冯·诺依曼奖：由IEEE设立。

对信息科学做出突出贡献的大神：图灵（所以才有个奖），冯 · 诺伊曼

中国获图灵奖的大神：姚期智（清华就有姚班，就是以他的名字命名的）

世界第一台电子计算机：埃尼阿克（\(ENIAC\)），于1946年2月14日（够虐狗的）在美国宾夕法尼亚大学诞生。又被叫做电子管计算机。

分两类：面向对象和面向过程。

高级语言需要编译运行，常数较大，运行速度慢。而低级语言常数极小，运行速度快。此外，高级语言更容易移植。

汇编

C++，Java，EIFFEL，Simula 67等。

C，Fortran语言。

递归是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题。简单来讲，就是“自身调用自身”（在函数中）。

1、P类问题：如果一个问题能找到一个在多项式时间内解决它的算法，那么这个问题就是P问题。

2、NP类问题：注意：NP问题不是非P类问题，而是在多项式时间内验证一个解的问题。或者，我们可以将其理解为在多项式时间内猜出一个解的问题。

3、NPC类问题：定义如下：如果一个问题是NP问题，而且所有的NP问题都可以约化到它。那么它就是NPC类问题。再来介绍一下关于约化的定义：如果一个问题A可以约化为问题B，含义就是这个问题A可以用问题B的解法来解决。

先上张大图：

重要设备：

硬件组成：

控制器(Control):是整个计算机的中枢神经，其功能是对程序规定的控制信息进行解释，根据其要求进行控制，调度程序、数据、地址，协调计算机各部分工作及内存与外设的访问等。

运算器(Datapath):运算器的功能是对数据进行各种算术运算和逻辑运算，即对数据进行加工处理。

存储器(Memory):存储器的功能是存储程序、数据和各种信号、命令等信息，并在需要时提供这些信息。

输入设备(Input system):输入设备是计算机的重要组成部分，输入设备与输出设备合称为外部设备，简称外设，输入设备的作用是将程序、原始数据、文字、字符、控制命令或现场采集的数据等信息输入到计算机。常见的输入设备有键盘、鼠标器、光电输入机、磁带机、磁盘机、光盘机等。

输出设备(Output system):输出设备与输入设备同样是计算机的重要组成部分，它把外算机的中间结果或最后结果、机内的各种数据符号及文字或各种控制信号等信息输出出来。微机常用的输出设备有显示终端CRT、打印机、激光印字机、绘图仪及磁带、光盘机等。

CPU及存储：

CPU（中央处理器）=运算器+控制器+寄存器

运算器=算术逻辑运算单元（ALU）及浮点运算单元（FPU）

存储器=内存储器+外存储器

BIOS是英文"Basic Input Output System"的缩略语，直译过来后中文名称就是"基本输入输出系统"。其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。

随机存储器RAM的“随机”指“随时访问”

所以，我们记下来以下知识点：

断电后可以保存数据：硬盘，ROM

断电后不可以保存数据：显存（显卡内存），RAM，CPU

计算机的存储单位有以下几种：

\(TB/GB/MB/KB/B\)

他们之间的进位关系为1024（这应该是常识，没打过比赛还没玩过手机么？）

特殊地，\(1B=8(bit)\)，这里的\(bit\)是二进制下的一位内存。

将十进制转换成\(N\)进制，只需把十进制数每次除\(N\)求余数，然后把余数逆序写出来。

看不懂就看图：

这是二进制的图，其他进制就类比推一下就可以了。如果这个看不懂的话就不要参加初赛了，50块钱买点啥不好...

简单说就是：按位转，第\(i\)位的数字乘以要转换的进制的\(n-1\)次幂即可。

还是上图：

这里考虑用十进制做中转，先把\(A\)进制转十进制，再把十进制转\(B\)进制。

十进制转任意进制的小数不进行除法运算，而进行乘法运算后取整，取整后从前向后排列。

任意进制转十进制的小数只需要乘上负指数，最后算出来即可。

\(H(Hexadecimal)\)——16进制

\(D(Decimal)\)——10进制

\(O(Octonary)\)——8进制

\(B(Binary)\)——2进制

二进制是计算机进行计算所使用的工具，自然也是非常常考的要点。二进制的相关知识有许多，甚至算法中的位运算也是二进制的相关内容，但为了过第一轮初赛，我们只介绍一些理论知识。关于位运算的相关知识请有兴趣的同学自己学习。

顾名思义，原码就是十进制数直接转换成二进制之后直接形成的二进制编码。

正数的补码是本身，负数的补码是其反码加一。

顾名思义：正数的反码是本身，负数的反码是其除符号位之外的所有位按位取反的结果。

ASCII码的正规名称是：美国信息交换标准代码，是基于拉丁字母的一套电脑编码系统。是最通用的信息交换标准。一共定义了128个字符。

这里不赋ASCII码的转换表。只给出几种比较常用的转换：

字符0→48

大写字母A→65

小写字母a→97

空格→32

换行→13

位运算不仅在初赛中是一个知识点分类，在复赛（即真正的程序设计与运用）的时候也有很大的一个应用。而且，位运算的相关知识是计算机运算的灵魂，更是每个程序猿应该理解的一种基本操作。

关于位运算的相关知识，本蒟蒻在另一篇专门的博客中详细的讲解。

常用的位运算技巧

为了应对初赛的笔试题，建议读者在阅读完这篇博客之后至少应该掌握：各种位运算的运算法则以及位运算优先级。

逻辑运算一共有三种，每种都有两种写法：

逻辑非：！或 ┐

逻辑与：&& 或 ∧

逻辑或：|| 或 ∨

非\(>\)与\(>\)或

逻辑非（！，┐）=按位反（~）>位移运算（）>不等号（>=,等号（==,!=）>按位与（&）>按位异或（^）>按位或（|）>逻辑与（&&，∧）>逻辑或（||，∨）

由逻辑运算复合而成，只有两种结果：\(true\)和\(false\)，在C/C++中，返回的值以\(0\)表示假，以\(1\)表示真。

条件表达式的基本形式如下：

？：

其表达意义是：如果表达式1成立，则执行表达式2，否则执行表达式3。其实也等价于\(if-else\)条件语句。例如下：