This is CS50 of Harvard University (2018)

Lecture 0 - Computational Thinking

听课笔记 [视频网址]([传思翻译组·中英字幕]CS50 哈佛大学 计算机科学导论 名校公开课[合集·完结]_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili)

• ​ input → 口 → output

计算机科学可以提炼成上述表达，计算机科学是关于解决问题的科学（computer science is about problem solving. ）

程序员通常亲自或通过利用代码协作来解决问题，而解决一个问题我们该如何去下手呢？

此时，我们需要一个能够代表问题的对象，这个对象是抽象的整体，代表着任意的问题。

让我们从计算机的最底层开始进入。

数

比如，一个房间内有很多人，我们要去统计这个房间的人数，可能需要我们去计数所看到的人。或许此时我们可以拿出一只粉笔画正字，或者用手扳手指来计算。

可是五根手指最大只能例举五个数字，我们要如何仅用五根手指表示更多的数字呢？这就引入了二进制。五根手指可以表示2的5次方即32。

计算机最底层，用二进制来表示。零和一，作为电源关闭和电源的打开的直接映射。

我们人类用十进制计数，用数字123来表达，实际上它可能仅仅只是个字符，但是从小学时代起这些字符被赋予意义，作为数字使用。

继续深入，为什么123可以被表示为一百二十三。因为不同数字被安排在不同位上，等价于1x100+2x10+3x1 .

计算机工作原理也相似，在十进制当中，10和100甚至1000往上都是10的幂，被称之为位权。计算机显然使用着2的幂。

当我们拥有足够的位，我们可以去表示更多的数。

字符

那么，如我我想表示一个字母或字符，我们又应该如何做？

我们设计了一个集合，规定了一定的数值所对应的字符，组成一个字符集。即ASCII，美国信息交换标准代码，用于信息交换。

从最底层的零和一，抽象到上一层的十进制数字映射，再抽象到上一层的字符映射，然后由几个字符来表示一个单词甚至一个句子。

字节

在计算机内部，存储单位也相当的重要。1byte对应8bit，一个字节表示一个ASCII编码，在一个字节当中八位二进制数字都各有意义。

抽象、编码集

抽象是将低水平的事物概括到更高的一个层次上去进行理解和操作。比如处理信息，表达一个信息时候我们喜欢在字符或单词的层面上去交流，而不是下沉到计算机的底层用0和1来理解信息，这样就过于繁琐且消耗心力。抽象是将较低级别的信息进行简化，以便于我们进行更有用的对话。

如此，在计算机的0与1之上，我们可以更进一步，去表示其他多样的信息。

受限于早期，传统字符编码方案的局限，Unicode是为了解决这样的问题而产生的，它为每种语言中的字符设定了统一并且唯一的二进制编码，便于跨语言跨平台进行文本转换、处理。（代表的特定版本：UTF-8）

用更多的字节，更多的存储位，我们得以有能力去代表数千甚至数百万个字符。

颜色、像素、图像

在不同的模式下，在其他场景中，通过不同编码我们不将其解释为文本，而是图像，某种颜色。

RGB(red,green,blue)，工业界制定的一种颜色标准，通过对红绿蓝三种颜色的变化和互相之间的叠加，来获得各种各样的颜色。此标准同时几乎包括了人类视力所能感知到的所有颜色，是运用最广的颜色系统之一。

一张图片（位图），有无数个像素组成，一个像素的RGB值用三个字节来表示，一个字节指定该特定像素应有多少红、绿、蓝，以此表示其对应的颜色。又由各种色彩的像素块组成一幅彩色图像。

视频

我们常常听到过这么一个名词，帧数。例如电影往往是每秒24帧或每秒30帧，表示每一秒钟有24或30张图像向你显示。通过视网膜的残留效应，将不断闪过的一系列静态图像组合成一幅运动的景物。

视频-图像-颜色-位，这同样也是计算机从底层存储的数值逐级抽象的表示。

算法

算法（algorithms），指解决计算机问题的方法。

对于一个问题，有不同的算法（解决方法）。例如，典型的排序问题，则有着不同的排序算法。

而对于算法的价值，我们用时间复杂度和空间复杂度去衡量他们，前者指需要花费的时间，后者指运行需要调动的资源。

算法是对问题的解决方法，但是我们要将其输入到机器内，让机器识别并且明白我们所需求的内容，并去运行它。

从顶层往下，我们先是了解问题的情况，然后给出解决的方法，再往下就是分解方法的步骤。

此时，方法的步骤用伪代码来表示（注意，伪代码没有定义，只是一种使用诸如语法或者口头语言之类的文本方式）。

此处开始，涉及到了我们所说的编程。

电话簿问题

假设我们拥有一本电话簿，要从中去查找一个人的电话号码，此时我们应该如何去做。

当我们选择了一页一页翻的时候，这样的方法时间复杂度和页数成正比的关系，表示为一个线性函数

当我们选择了两页两页的翻，速度可能会变得更快一点，但仍然是线性函数，而且这么做也会出现错过目标对象的糟糕结局。

当我们直接从中间开始（二分查找），舍弃一半查找目标对象所存在的另一半，继续往下，此刻是时间复杂度是对数函数表示。

伪代码（函数 条件 循环）

打开电话簿
从中间翻开
查找名字
如果找到目标
    拨打电话
否则……
……

以上表示我们可以看出，通过特定步骤和特定行为以及不断的重复，来缩小问题和趋近问题的答案。

• 函数(functions)

特定的行为，或者说特定的动作，为了达成某种目的而采取的若干行为，编程中我们将之成为函数。在一个程序当中，程序由若干个程序块来组成，每一个程序块实现一个特定的功能。而在编程过程中我们将经常使用的功能模块编写成函数，供人调用，来实现特定的功能。

编写程序，善于利用函数来减少编码的工作量。

• 条件（conditions）/分支 布尔表达式（Boolean expressions）

如果 否则（if，else if ，else），表示对所提出问题的判断。计算机中将其需要判断的选择抽象为布尔表达式，得出布尔值（真或假）后进行所预设的行为步骤。

• 循环(loops)

计算机一遍又一遍执行某项操作.通常有按一定次数循环和按照条件判断循环。是程序中重要的一个处理过程。规律性的重复操作对某些问题的解决起到作用。

同时，对于循环我们要特别注意其终止条件，防止出现死锁现象。

• 程序背后的所有内容，是函数，循环和条件以及其他的一些概念组成。

Scratch

麻省理工学院所开发的图形化编程工具。本视频（2018 cs50 lecture 0 ）后半段部分主要讲解了其语言的使用方法，并且从中简单说明了选择结构，循环结构，判断，分支，条件等概念。

此笔记对此部分进行省略。