前言^[1]

这么厚一本书 6 天怎么讲完？ 这里的东西是真的非常多。

• 前言
• 计算机基础知识
  • 计算机发展史
  • 计算机语言
  • 进制转换
  • 信息编码
  • 原码、反码、补码
  • 小数表示方法
• 程序设计基础知识
  • 时间、空间复杂度
  • C++语言基础
  • 排序算法

---

计算机基础知识^[2]

这一块本来东西非常非常非常多，但是我讲不了那么详细。

计算机发展史^[3]

纯知识点。

1. 分为五个阶段：

代别	组成
第一代	（真空）电子管
第二代	晶体管
第三代	集成电路
第四代	（超）大规模集成电路
第五代	智能计算机系统

（这里是科幻部分：）可能在未来会发明出量子计算机，这样题目测评就再也不会出现 TLE 和 MLE 了。

2. $1946$ 年，世界上第一台电子计算机 ENIAC 在美国宾夕法尼亚大学诞生。（太过老旧，可能不考）

3. 计算机界两个重要人物：

   1. 图灵：人工智能之父，提出图灵机模型 。还有以他命名的图灵奖。
   2. 冯·诺依曼：计算机之父，提出计算机体系结构，沿用至今。

4. 冯·诺依曼的计算机体系结构：

   计算机硬件由输入输出设备、运算器、存储器、控制器组成，各个设备之间由总线连接。

计算机组成

计算器由硬件系统和软件系统组成。

计算机语言^[4]

计算机语言可以分为低级语言和高级语言。

低级语言

低级语言分为：

1. 机器语言：由二进制编写。能直接被计算机识别，但是又臭又长。
2. 汇编语言：由指令编写，不能被计算机识别。

高级语言

按照解决问题方式分：

1. 面向过程语言：自顶向下，模块化思想。 例如： C 语言。
2. 面向对象语言：将问题抽象成类，再实例对象包括属性和行为 。例如： C++ 、 Java 、 Python 。

按照执行过程分：

1. 编译型语言：将整个文件编译为机器语言，再执行。 例如： C++ 语言。
2. 解释型语言： 一句一句执行 。例如： Python 。

进制转换^[5]

数制

1. 十进制：数字 $0$ ~ $9$ ，逢十进一。
2. 二进制：数字 $0$ ~ $1$ ，逢二进一。
3. 八进制：数字 $0$ ~ $7$ ，逢八进一。
4. 十六进制：数字 $0$ ~ $9$ 和字母 $\texttt{A}$ ~ $\texttt{F}$ 对应十进制 $10$ ~ $15$ 。逢十六进一。
5. 权值：一位数在当前进制表示的数。例如 $123$ ： $1$ 的权值是 $100$ ， $2$ 的权值为 $10$ 。

转换

1. K 进制转十进制：加权求和法。

   将数字转化为一个多项式，每一项是当前位数与权值之积的和： $(ab.cd)_K = a\times K^1+b\times K^0+c\times K^{-1}+d\times K^{-2}$ 。

2. 十进制转 D 进制（整数部分）：短除求余法。

   将十进制数不停除以 D 直到这个数为 $0$ 。倒序组成余数就是转换后的数。

3. 十进制转 D 进制（小数部分）：长乘取整法

   将十进制数不停乘以 D 直到这个数为 $0$ 。正序组成整数部分就是转换后的数。

4. 二进制与 $2^k$ 进制转换。

   $k$ 位之间转换。

信息编码^[6]

1. 字母编码： ASCLL 编码。例如 'A' = 65 。
2. 中文编码： GB （国标）编码。
3. 字模：用二进制信息在 $16\times16$ 的点阵写出汉字。
4. 国际编码： Unicode 编码。

原码、反码、补码^[7]

由于 $32$ 位整型变量的第一位为符号位。直接加减有麻烦，所以引入这些编码。

1. 正数的原码、反码、补码均相同。
2. 负数的原码为：这个数的绝对值的编码并把符号位改为 $1$ 。
3. 负数的反码为：除符号位之外的所有数字都取反。
4. 负数的补码为：反码 $+1$ 。

小数表示方法^[8]

1. 定点表示法：

   在一段内存中选择一个位置为小数点，则前为整数，后为小数。

2. 浮点表示法：

   类似十进制中的科学计数法。通过位移将小数表示为：

   $$N = 2^E\times S$$

   E 为价码，决定数字的大小；

   S 为尾码，决定数字的精度。

计算机网络

这里只能靠蒙了。

程序设计基础知识^[9]

时间、空间复杂度^[10]

用大写 $O$ 加括号表示算法的时间复杂度。下面是一些方便但非正式的计算方法：

1. 对于递归函数：如果每次递归为 $\frac{n}{x}$ ，则时间复杂度内一定包含 $\log n$ 。
2. 如果有循环，则一定要多加个 $n$ 。
3. 正式计算方法： 主定理。

空间复杂度也可以用大写 $O$ 表示，即程序运行的内存占用。

C++语言基础^[11]

基本构成

#include <iostream> // 主函数
using namespace std; // 命名空间

int main() // 主函数，程序开始的地方
{

	return 0; // 程序结束
}

数据类型

基本数据类型：

1. 布尔型： bool ；
2. 字符型： char ；
3. 整型： int ；
4. 实型：
   1. 浮点型： float ；
   2. 双精度： double ； 非基本数据类型：
5. 数组 [] ；
6. 指针 * ；
7. 空 void ；
8. 结构体： struct ；
9. 联合体： union ；
10. 类： class 。

类

class potato // 定义一个叫做potato的类 
{
	public: // 类型修饰符，对外公开 
		int weight, hight; // 公开的变量 
		void weiche() // 类成员函数 
		{
			double PMI = weight / ((hight / 100.0) * (hight / 100.0));
			cout << "PMI为：" << PMI << ", "; 
			if (PMI > 999999) cout << "超重，须减肥\n";
			else if (PMI < 23) cout << "偏瘦，须多吃\n";
			else cout << "正常，须保持\n";
		}
}

程序基本结构

1. 顺序结构：从上往下逐行执行；

   cout << "Hello world"; 
   

2. 选择结构：如果条件成立则执行；

   if (a > b)
   {
     cout << a;
   }
   else
   {
     cout << b;
   }
   

3. 循环结构：循环直到条件不成立。

   while (a > b)
   {
    	b++;
    	cout << "Hello world\n";
   }
   

函数

返回类型 函数名(参数列表)
{
	函数体 
}

递归函数

函数调用自身。

排序算法^[12]

常用排序算法复杂度：

算法名称	最坏时间复杂度	平均时间复杂度	空间复杂度	稳定性
选择排序	$O(n^2)$		$O(1)$	不稳定
插入排序				稳定
冒泡排序
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$
快速排序	$O(n^2)$		$O(1)$	不稳定

---

1. 前言 ↩︎

2. 计算机基础知识 ↩︎

3. 计算机发展史 ↩︎

4. 计算机语言 ↩︎

5. 进制转换 ↩︎

6. 信息编码 ↩︎

7. 原码、反码、补码 ↩︎

8. 小数表示方法 ↩︎

9. 程序设计基础知识 ↩︎

10. 时间、空间复杂度 ↩︎

11. C++语言基础 ↩︎

12. 排序算法 ↩︎