作者：战德臣 陈荆亮 叶志伟 王春枝 战绪东
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
大学计算机——计算思维导学试读：
前言
计算思维被认为是与理论思维、实验思维并列的第3种思维模式，是“互联网+”、大数据和人工智能时代所有人都应具备的一种思维模式。近些年来，国家推行了一系列信息技术引领的行动计划，如“‘互联网+’行动计划”“新一代人工智能发展规划”等，这些计划的关键和基础是要培养一批具有“互联网+”思维、“大数据”思维和“人工智能”思维的人才，这种思维本质上都是一种计算思维。这种思维，既不能狭义地理解为“各种计算机硬件/软件的应用”，也不能狭义地理解为“计算机语言程序设计训练”，它其实是解决社会、自然问题的一种思维方式。例如，计算机管理“磁盘”所使用的“化整为零、还零为整”思维，对如何进行现实中不同性能资源（如物流仓储配送中的资源）的高效管理具有指导意义；管理“程序执行”的“分工—合作—协同”思维，对现实中管理和执行宏观任务也是有借鉴作用的。因此，计算思维对培养既有宏观协调能力又有微观精细化执行能力的新时代人才有重要的意义。2015地平线报告指出“强调计算思维教育，可以帮助学习者解读真实世界的系统并解决全球范围的复杂问题”，这应该是计算思维教育的终极目的之一。
在这种背景下，各高等学校都开设了“大学计算机”课程，要求各学科各专业的学生都要学习这门课程。那么，“大学计算机”应该是一门什么样的课程呢？它应是面向大学低年级学生开设的，与“大学数学”“大学物理”有一样地位的技术型通识类思维教育课程。它不应只是讲授计算机及其软件（如Office、Access、IE等）使用的课程，也不应是仅仅训练学生程序设计能力的课程，它应是讲授每个大学生都应具备的计算思维的课程。大学生创造性思维的培养离不开计算思维的培养，互联网公司（如阿里巴巴、Facebook、Apple、腾讯等）的成功应归属于计算思维运用的成功。当前，国家正在大力推动新工科建设，其中一个重要方面就是强调“各学科+计算机”，其根本应是“各学科+计算思维”。
那么，又应如何学习“大学计算机”课程呢？我认为，应更多地强调“思维”，而不应仅着眼于“知识”（即事实的学习）。你可以不知道“计算思维”的定义，那仅是概念，但你应该知道“符号化—计算化—自动化”，你应该知道“计算系统与程序的关系”，你应该知道“程序是如何被机器自动执行的”……这些都是体现计算思维的直观例子。以潜移默化的方式理解和接受计算思维，是把握和学习本门课程最重要的方式。举个例子，中医里讲究“穴位”，不同的穴位连接起来就是“脉络”，不同的脉络在临床诊断时有不同的意义，这是中医的基本认识。但即使你知道了脉络，为什么还不能治病呢？这是因为你没有能力让气息在脉络间流动。要做到这点，就需要长期训练。因此，知识好比是“穴位”，而一年级时学习“大学计算机”课程，好比是在学习“脉络”，你要熟悉这些“脉络”，然后才能进行“诊断”。当你经过若干年的不断努力，深入理解了知识，能将知识融会贯通时，你就能将思维转变成能力——运用计算思维的能力。
本书从最基本的“计算”讲起，从“计算+”讲到“大数据+”“互联网+”，覆盖了计算学科经典的、重要的计算思维，并从学习者的角度组织教学内容：首先，站在学科高度，凝练教学内容，提取重点之重点，以精练的语言进行讲述；然后，通过大量的、丰富的示例题目，引导读者对教学内容进行渐进式的、有一定深度的探索；最后，将教学内容转换成不同深度的示例题目，在场景、练习、模拟中，实现对教学内容不同深度的理解，进而达成“不仅是了解计算思维，而且能够理解和运用计算思维”的目标。同时，作者在中国大学MOOC等平台开设有“大学计算机——计算思维导论”和“计算机专业导论”慕课课程，读者可参考并学习。
本书适合各类专业的大学本科生学习（建议在大学一年级学习）。考虑到教学进度和学生接受程度，总学时安排48学时为宜（不含实验学时）。如果非计算机专业不再开设高级语言程序设计课程，则需增加实验，需分配64学时；如果还有高级语言程序设计课程，则建议本课程不含实验，因为实验会涉及很多细节性内容，在学时有限的情况下会影响对计算思维的理解，学校可依据实际情况，结合表中给出的内容与学时建议进行调整和设置。另外，书中标记“扩展学习”的内容，可作为课程的延伸内容，由教师引导，学生自主学习。学时安排表续表
本书得到教育部高等学校大学计算机课程教学指导委员会的大力支持，在此表示感谢。在本书编写过程中，很多学校的一线教师提出了很好的建议，在此对他们表示感谢。另外，感谢哈尔滨工业大学本科生院、计算机学院，湖北工业大学计算机学院对本书编写和出版工作所给予的大力支持。“大学计算机”是一门发展中的课程，教材中的内容难免有不完善之处，敬请广大读者谅解，并诚挚地欢迎读者提出宝贵建议。作者2018年5月1日第1章 什么是计算思维本章摘要
计算思维是信息化社会所有学生应掌握的基本思维模式，是促进学科交叉、融合与创新的重要思维模式。本章通过一个示例解释了什么是计算思维以及计算思维的价值。1.1 趣味故事：用小白鼠检验毒水瓶
学习计算机，首先要学习计算思维。那什么是计算思维呢？首先看一个问题及其求解，这个问题不需要很多数学知识，所有读者都应能求解。
示例1 问题：有1 000瓶水，其中一瓶是有毒的，小白鼠只要尝一点带毒的水，24小时内就会死亡，问：至少要有多少只小白鼠才能在24小时内检验出哪瓶水有毒？怎样检验？
看下面的求解过程，如图1.1所示。图1.1 “用小白鼠检验毒水瓶”问题求解示意
第1步，将1 000瓶水逐瓶编号，编号从0～999，假设第997号瓶水有毒。
仅用十进制编号，很难看出如何求解。怎么做呢？可以用二进制求解该题。
第2步，做一个变换，将每瓶水的编号由十进制转换为二进制。1
1位二进制数只能表示0或1（最大编号2-1）,2位二进制数能表2示0～3（最大编号2-1）,……，以此类推，10位二进制数能表示0～1 10023（最大编号2-1）。因此，若要表示999这个编号，则需要10位二进制数。由此，是否可想到需要10只小白鼠就可在24小时内检验出哪瓶水有毒呢？
答案是10只。问题接着来了：应该怎样让小白鼠喝水，才能用10只小白鼠的存亡状态，从1 000瓶水中判断出哪一瓶有毒呢？注意：小白鼠喝了有毒的水，可能很快死亡，但也可能在接近24小时时死亡，因此不能一只一只地试验，那样时间不够。987
第3步，每一瓶水的编号都是10位二进制数，记为BB B B 6543210BB B B B B （其中Bi仅为0或1,i=0,…,9）,10只小白鼠分别编号9876543210为M,M,M,M,M,M,M,M,M, M。制定规则如下：编号为9876543210BBBBBBBBBB的一瓶水，如果Bi位为1，则让Mi小白鼠喝一口；如果Bi位为0，则不让Mi小白鼠喝。
第4步，1 000瓶水，均按上述规则进行处理。待小白鼠喝完后，静等24小时，然后看哪只小白鼠死掉了。如Mi小白鼠死了，则Mi=1，否则Mi=0。将Mi连起来看，依题， 9876543210MMMMMMMMMM=1111100101，就得出了有毒水瓶的二进制编号，再还原回十进制编号，便可知道997号瓶的水有毒。1.2 什么是计算思维“用小白鼠检验毒水瓶”的问题（以下简称“小白鼠问题”）能够求解了，但这道题背后的思维是怎样的呢？下面试着归纳一下。1.2.1 二进制思维
首先，“小白鼠问题”的求解运用了二进制思维。
怎样理解二进制呢？与十进制对比一下就不难理解：（1）十进制是用10个数码{0,1,2,3,4,5,6,7,8,9}表达一位十进制数，如9 587；二进制是用2个数码{0,1}表达一位二进制数，如0111 0101；（2）十进制是“逢十进一、借一当十”，二进制是“逢二进一、借一当二”。
那么，二进制数与十进制数如何转换呢？规则是很简单的（详细内容可参见1.4节）。其实，日常生活中使用了许多的进制，如十二进制、二十四进制、六十进制等，类似于“时间由1时50分到3时20分是持续了多少分钟呢？”这样的问题我们是会转换的，只是不习惯而已，熟悉了就会了。
二进制思维有很重要的意义，它可将很多事物（或状态）非常巧妙地统一起来，如1.1节的示例。0和1可以表示“有毒”与“无毒”，可以表示“喝”与“不喝”，也可以表示“死”与“活”。对同一串0和1，如000010，可有以下不同的解读。
000010，对应编号为000010的水瓶。
000010，第i位对应第i只小白鼠，1表示喝，0表示不喝。
000010，第i位对应第i只小白鼠，1表示死亡，0表示存活。
很多情况下看起来不容易解决的问题，用二进制思维便可解决，如“小白鼠问题”的求解。“小白鼠问题”之所以看起来很难，是因为多种含义的0和1交织在一起，影响了思维的清晰性。但不管怎样，强化“将多种事物及状态用0和1统一在一起”的训练是运用计算思维的关键之一。
中国古老的易经也是采用二进制思维来表达万事万物及其变化规律的，如图1.2所示：0和1，对应“阴”和“阳”;3位0和1组合起来，共有8种组合，对应三画阴阳的组合，共有“八卦”;6位0和1组合起来，共有64种组合，对应六画阴阳的组合，共有“六十四卦”。易经的某一卦，即某一组0（阴）和1（阳）的组合可以解释为不同的含义，用“卦”“爻”的变化来理解自然现象及人事现象的变化规律，开启了用符号和二进制思维进行规律性问题研究的先河，是典型的二进制思维的代表。图1.2 《易经》与0和1的示意1.2.2 二分法——人类普遍应用的思维“小白鼠问题”的求解运用了二分法思维，这是人类普遍应用的一种思维模式。
所谓的二分法，就是通过不断地排除“不可能”，进而找出问题正确解的一种方法。之所以称“二分”，是因为每次处理都把所有情况分成“可能”和“不可能”两种情况，然后排除所有“不可能”的情况，而在“可能”的情况中再进行下一次的排除。
例如，一种典型的猜数游戏：机器随机设定一个数，由用户来猜。每当用户给出一个猜测值时，系统会提示“大了”，还是“小了”。此时如果大了，则你就向比猜测值小的方向选择新猜测值，如果小了，就向比猜测值大的方向选择新猜测值，直到找出正确答案。
再例如，工人要维修一条电话线路，如何迅速查出故障所在位置呢？如果沿着线路一段一段地查找，则每查一个点要爬一次电线杆，将会浪费时间和精力。此时可使用二分法：设电线两端分别为A、B，首先从中点C查起，用随身带的话机向两端测试时，发现AC段正常，则断定故障在BC段。再到BC中点D，发现BD正常，则断定故障在CD段，再到CD中点E检查，这样每查一次，就可以把待查线路长度缩减为一半，可以节省很多查找时间和精力。
前述两个例子的二分法思想是否可直接用于“小白鼠问题”的求解呢？似乎不可以，如图1.3（a）所示，每一次有毒/无毒的分类需要等本次实验的小白鼠死亡或等待24小时才能确定，满足不了时间约束。怎么解决呢？如图1.3（b）所示，是否可采取多只小白鼠同时进行实验呢？这是可以的：每一只小白鼠负责喝500瓶水，如果死亡，则说明这500瓶中有毒而另500瓶无毒；如果没有死亡，则说明这500瓶中无毒而另500瓶中有毒。每只小白鼠检验的范围不同，多只小白鼠交错可唯一确定某一瓶水是否有毒，即如果喝了这瓶水的所有小白鼠都未死亡，则说明该瓶水无毒。这就需要借助二进制编码的方式以决定哪一只小白鼠负责检验哪些水瓶。这种方法本质上仍旧是二分法，但却是并行实现的。图1.3 “小白鼠问题”的二分法求解示意1.2.3 过程化与符号变换思维计算与自动计算“小白鼠问题”的求解运用了“过程化”与“符号变换”的思维。“过程化”与“符号变换”是典型的计算思维，那计算思维中的“计算”是什么呢？
简单计算，例如从幼儿时期就开始学习和训练的算术运算：7 + 2= 9,4×6 = 24,30 - 13 = 17，是指“数据”在“运算符”的操作下，按“计算规则”进行的数据变换。我们不断学习和训练的是各种运算符的“计算规则”及其组合应用，目的是通过计算得到正确的结果。
广义地讲，一个函数f (x)，例如
把x变成了f (x)就可认为是一次计算，在高中及大学阶段不断学习各种函数及其“计算规则”并应用其求解各种问题，得到正确的计算结果，如对数与指数、微分与积分等。“计算规则”可以学习与掌握，但应用“计算规则”进行计算则可能超出了人的计算能力，即人知道计算规则但却没有办法得到计算结果。
从计算机学科角度，任何的函数f (x)，不一定能用数学函数表达，但只要其有明确的输入和输出，并有明确的可被机器执行的步骤将输入变换为输出，便可称为计算。一些学者认为“任何一个过程都有输入和输出，过程是将输入变换为输出的一组活动”，也有学者认为“过程实现了系统从一个状态（始态）变换成另一个状态（终态）”。万事万物都可被转换成符号作为过程的输入，通过符号变换，转换成另一种符号作为输出并转换成自然状态的万事万物，这也是计算。“小白鼠问题”求解体现了这样一种过程：水瓶十进制编号（所有）→（变换为）二进制编码→（变换为）分配给小白鼠喝与不喝，并产生小白鼠死与活的结果→（变换为）二进制编码→（变换为）十进制编号，找出毒水瓶。“过程化”是任何事物利用计算机进行处理的前提，即首先要过程化，然后才能将这种过程转变为计算机能够执行的程序，进而才能实现自动化。1.2.4 计算思维的概念什么是计算思维
结合前面的分析，是否能体验出什么是计算思维呢？
前卡内基·梅隆大学计算机系系主任、前微软公司副总裁周以真（Jeannette M. Wing）教授指出“计算思维（Computational Thinking）是运用计算（机）科学的基础概念去求解问题、设计系统和理解人类行为的一系列思维活动的统称”。它是所有人都应具备的如同“读、写、算”能力一样的基本思维能力，计算思维建立在计算过程的能力和限制之上，由人或机器执行。
这个定义赋予计算思维3层更高的含义。（1）计算思维是一种问题求解思维，即通过计算的手段求解现实中各种各样的计算问题，例如，通过数学建模、算法设计研究求解各种现实问题的方法和算法等。（2）计算思维是一种设计系统的思维。设计和构造新型计算系统或计算工具以解放人类劳动力始终是人们追求的目标，而各种新型计算工具的研制对于社会的进步和发展有重要的促进意义。例如，获得诺贝尔化学奖的J.A.Pople就是把计算机应用于量子化学，设计了一套计算程序，使全世界的量子化学工作者都在用他的程序研究化学问题。（3）计算思维是有助于人类行为理解的思维。计算思维源于社会/自然，又反作用于社会/自然。例如，“流水线”的概念是源于20世纪福特汽车生产线的概念，被计算机学科应用和发展，而现在很多工厂的数字化生产线又是借鉴计算学科的“流水线”概念在广泛应用。类似的，计算思维也在改变着社会的结构和人类的行为。
正像2015地平线报告指出的：复杂性思维教学是一种挑战，计算思维是一种高阶复杂性思维技能，是复杂性思维能力培养的重要支撑，强调计算思维教育，可以帮助学习者解读真实世界的系统并解决全球范围的复杂问题。
计算思维不同于数学思维，不仅仅是将数学公式变为程序；计算思维也不仅仅是计算机语言和编写程序。前面讨论的二进制思维、二分法思维、过程化与符号变换思维都是计算思维，但计算思维不仅仅是这些，它还包括计算+、互联网+、智能+、大数据+的思维等。
应该说计算思维不是简单的一个概念，而是需要在学习和实践过程中不断体会、不断理解的设计计算系统并运用计算系统的思维。技术与知识是创新的支撑，而思维是创新的源头。理解计算系统的一些核心概念，培养一些计算思维模式，对于所有学科的人员建立复合型的知识结构，进行各种新型计算手段研究以及基于新型计算手段的学科创新都有重要的意义。1.3 扩展学习：计算思维的价值在哪里
计算思维有什么价值呢？学好计算思维有助于创新想法，并将创新想法变为现实。下面类比“小白鼠问题”做一个测试：判断数据传输是否有错误。
大家都知道，计算机中所有的信息都展现为01串，如1001110010010111，并且需要不断地进行传输，如从一台计算机传输到另一台计算机，或者从一台计算机上传到网络中，那么有没有可能传输错误呢？当然是有可能的。那怎么判断并纠正错误呢？首先分析0和1的特性，然后再探讨判断并纠正错误的方法。1.3.1 0和1及其特性
二进制算术运算是位相关运算，即逢二进一、借一当二，有规则如下。
1.加法运算规则
0＋0 = 0; 0＋1 = 1; 1＋0 = 1; 1＋1 = 0（本位为0，进位为1）。
2.减法运算规则
0－0 = 0; 0－1 = 1（借位为1）; 1－0 = 1; 1－1 = 0。
示例2 X=10111,Y=10011，则X+Y = 101010。
解：
示例3 X=10101,Y=11011，则X+Y = 110000。
解：
示例4 X=10111,Y=10011，则X－Y = 00100。
解：
10111－) 10011 00100
示例5 X = 11001,Y=10110，则X－Y = 00011。
解：
如果仅做1位的加法，加数、被加数与和均为1位，所有进位将被自动舍掉，则n个1的累加和也只能是1位，其结果依赖于n是偶数，还是奇数。若n是偶数，则累加和为0，若n是奇数，则累加和为1。这一特性很重要，可以看出：判断一个01串中1的个数是偶数还是奇数，只需将该01串的各位逐位累加即可，依据其累加和为0，还是1即可判断。
为更严格地表述，下面引入异或运算。
3.异或运算规则
异或运算“⊕”是一种位运算，规则为“相同为0，不同为1”：
为叙述方便，定义一个新的运算：按位异或和，该运算用以判断一个01串中1的个数是奇数还是偶数。
4.按位异或和
一个01串（又称比特串），其按位异或和，即是将该01串的每一位实施异或运算得到的结果。该结果依赖于01串所包含的1的个数：如果包含奇数个1，则其按位异或和为1；如果包含偶数个1，则其按位异或和为0。（此可由异或运算规则予以证明，证明过程略。）
按位异或和得到的结果与仅做1位运算的按位累加和结果是一致的，所不同的是按位异或和没有产生任何进位，而按位累加和是舍掉了所有的进位。这两个操作的目的都是判断一个01串中1的个数是奇数还是偶数。
示例6 01串1011的按位异或和，即1⊕0⊕1⊕1 = 1（奇数个1，其按位异或和为1）。
示例7 01串1001的按位异或和，即1⊕0⊕0⊕1 = 0（偶数个1，其按位异或和为0）。
人在计算的过程中通过统计1的个数即可以获知1011 0110 1011 0110 1110 1001 1101 1010的按位异或和为0（其包含了20个1，偶数个1）。再例如1011 0111 1111 1110 1111 1101 1101 1010的按位异或和为1（其包含了25个1，奇数个1）。1.3.2 偶校验：判断数据传输有无错误
下面用对比的方式进行讨论。
小白鼠问题：有n瓶水，其中仅可能有1瓶水有毒，如果不考虑是哪一瓶有毒，而仅考虑是否有有毒的瓶，该怎样检测呢？
传输校验问题：对于一个n位的01串010…1101，如果在传输过程中仅可能有1位发生错误，如果不考虑是哪一位错误，而仅考虑是否有传输错误，该怎样检测呢？
小白鼠问题解决方案：仅判断是否有有毒的水，则只需1只小白鼠。将这n瓶水让小白鼠每瓶都喝一滴。如果小白鼠死亡，则表示有有毒的水；而如果小白鼠未死亡，则表示没有有毒的水。
传输校验问题解决方案：仅判断有无传输错误，则只需增加1位校验位P（小白鼠，只是P的值也只能是0或1）。传输前，P如何产生呢？
假设制定一规则：传输前01串中1的个数，与传输后01串中1的个数始终都保持偶数，则为传输正确。
因此，在传输前应使待校验01串S与校验位P所形成的新01串S’中1的个数为偶数。则P的产生规则为：P为S的按位异或和，即如01串S中1的个数为奇数，则P为1；如01串S中1的个数为偶数，则P为0。
这样无论S是怎样的01串，带校验位的01串S’中1的个数始终为偶数。
当S’传输过去后，对传输过去的S’再计算其按位异或和P'：如果P'=1（相当于小白鼠死亡），则传输错误；而如果P'=0（相当于小白鼠未死亡），则无传输错误。即如果传输过去，S’中1的个数仍旧为偶数，则表明没有传输错误；而如果传输过去，S’中1的个数为奇数，则表明有传输错误。
偶校验：通过增加一位校验位P，使得待传输01串S与P组合形成的新的01串S'中1的个数始终为偶数。通过判断传输中S’中1的个数是否仍为偶数来判断数据是否传输错误的方法就是偶校验。
示例8 传输01串1001 1010，若采用偶校验，则其校验位P的值应为 。
解：P = 1⊕0⊕0⊕1⊕1⊕0⊕1⊕0 = 0。
示例9 传输01串1111 1010 1011，若采用偶校验，则其校验位P的值应为 。
解：P = 1⊕1⊕1⊕1⊕1⊕0⊕1⊕0⊕1⊕0⊕1⊕1= 1。
示例10 假设01串1001 1110 1101，传输后变为1001 1010 1101，假设校验位传输无错误，若采用偶校验，请叙述其检测过程。
解：S为1001 1110 1101,P = 1⊕0⊕0⊕1⊕1⊕1⊕1⊕0⊕1⊕1⊕0⊕1= 0。
传输前S’应为1001 1110 1101 0。
传输后S’为1001 1010 1101 0,P' = 1⊕0⊕0⊕1⊕1⊕0⊕1⊕0⊕1⊕1⊕0⊕1⊕0 = 1。
因P'=1，故传输有错误。
示例11 已知接收到的01串为1101 1111 1011 0，采用偶校验，请判断是否传输错误。
解：P' = 1⊕1⊕0⊕1⊕1⊕1⊕1⊕1⊕1⊕0⊕1⊕1⊕0 = 0。故此传输无错误。
基于前述规则，可以发现，偶校验是能够检测出单数位数的数据传输错误，即当传输过程中有1位传输错误，或有3位传输错误，或有5位传输错误时，偶校验是可以判断出传输发生错误的。而当有偶数位数的传输错误，偶校验则发现不了。这是为什么？1.3.3 类比小白鼠问题判断哪一位出错
1.3.2小节讨论的是判断数据传输过程中有无错误，而并不能确定是哪一位出错。那如何判断哪一位出错呢？还是对比小白鼠问题进行讨论。
小白鼠问题：有7瓶水，其中仅可能有1瓶水有毒，例如，第6瓶水有毒，怎样判断出是第6瓶水有毒呢（从右向左，或者说从低位向高位编号）？
传输校验问题：对于一个7位的01串1101101，如果在传输过程中仅可能有1位发生错误，例如，传输后变为1001101，怎样判断出是第6位出错呢（从右向左，或者说从低位向高位编号）？
小白鼠问题解决方案：将7瓶水按十进制编号为1,…,7。然后将十进制编号转换为二进制编号，分别为001,010,011,100,101,110,111。421可见编号需要3位二进制位，因此需要3只小白鼠，编号为PPP。012P小白鼠喝二进制编号第2位为1的瓶中的水（即第1,3,5,7瓶水）;P14小白鼠喝二进制编号第2位为1的瓶中的水（即第2,3,6,7瓶水）;P小2白鼠喝二进制编号第2位为1的瓶中的水（即第4,5,6, 7瓶水）。然后等待小白鼠是否死亡：哪一只小白鼠死亡，则其为1，未死亡，则其421为0。依题，PPP=110，还原为十进制则为6，说明第6瓶水有毒。
传输校验问题：如图1.4所示，将7位的01串S 1101101按从低位向高位（自右向左）编号为1,…,7；然后将十进制编号转换为二进制编号，分别为001,010,011, 100,101,110,111。可见编号需要3位二进421制位，因此需要3位校验位，编号为PPP。采取偶校验，则校验位1的产生规则（类似于小白鼠如何喝的规则）为：P负责使二进制编号0第2位为1的那些位中1的个数为偶数（即使第1,3,5,7位中1的个数为12偶数）;P负责使二进制编号第2位为1的那些位中1的个数为偶数24（即使第2,3,6,7位中1的个数为偶数）;P负责使二进制编号第2位为1的那些位中1的个数为偶数（即第4,5,6,7位中1的个数为偶数）。图1.4 利用“小白鼠问题”探究数据传输纠错问题解决方案示意
可表示为：24
P= 第7位⊕第6位⊕第5位⊕第4位（即编号的2位为1的那些位的按位异或和）；12
P= 第7位⊕第6位⊕第3位⊕第2位（即编号的2位为1的那些位的按位异或和）；01
P= 第7位⊕第5位⊕第3位⊕第1位（即编号的2位为1的那些位的按位异或和）。421
依题，P= 1⊕0⊕1⊕1 = 1;P= 0⊕1⊕1⊕1 = 1;P= 1⊕1⊕0⊕1 = 1。
由此产生新的01串S’为1101101 111。
依题，传输过去后，S’变为1001101 111。按照偶校验的规则产421生P'P'P'（类似于确认小白鼠是否死亡）。44
P'= 第7位⊕第6位⊕第5位⊕第4位⊕P= 1⊕0⊕0⊕1⊕1 = 1；22
P'= 第7位⊕第6位⊕第3位⊕第2位⊕P= 1⊕0⊕1⊕0⊕1 = 1；11
P'= 第7位⊕第5位⊕第3位⊕第1位⊕P= 1⊕0⊕1⊕1⊕1 = 0。421
P'P'P'=110，还原为十进制则为6，说明第6位出错。
依题，传输过去后，S’如变为1101001 111。按照偶校验的规则421产生P'P'P'（类似于确认小白鼠是否死亡）。44
P'= 第7位⊕第6位⊕第5位⊕第4位⊕P= 1⊕1⊕0⊕1⊕1 = 0；22
P'= 第7位⊕第6位⊕第3位⊕第2位⊕P= 1⊕1⊕0⊕0⊕1 = 1；11
P'= 第7位⊕第5位⊕第3位⊕第1位⊕P= 1⊕0⊕0⊕1⊕1 = 1。421
P'P'P'=011，还原为十进制则为3，说明第3位出错。
示例12 待传输01串为1001111，若采用偶校验，需增加几位校验位才能判断出哪一位传输错误，若传输过去变为01串为1011111，则如何判断出是哪一位出错？23421
解：因2< 数据位数7 < 2，故需增加3位校验位，记为PPP。421其中PPP产生如下：421
P= 1⊕0⊕0⊕1 = 0;P= 1⊕0⊕1⊕1 = 1;P= 1⊕0⊕1⊕1=1。
S’串为1001111 011。
依题S’串传输过去后变为1011111 011。按照偶校验的规则产生421P'P'P'。44
P'= 第7位⊕第6位⊕第5位⊕第4位⊕P= 1⊕0⊕1⊕1⊕0 = 1；22
P'= 第7位⊕第6位⊕第3位⊕第2位⊕P= 1⊕0⊕1⊕1⊕1 = 0；11
P'= 第7位⊕第5位⊕第3位⊕第1位⊕P= 1⊕1⊕1⊕1⊕1 = 1。421
P'P'P'=101，还原为十进制则为5，说明第5位出错。
示例13 待传输01串为1111，若采用偶校验，需增加几位校验位才能判断出哪一位传输错误？若传输过去01串变为1011，则如何判断出是哪一位出错？23421
解：因2< 数据位数4 < 2，故需增加3位校验位，记为PPP。421其中PPP产生如下：421
P= 1;P= 1⊕1 = 0;P= 1⊕1=0。
S’串为1001 100。
依题，S’串传输过去后变为1011 100。按照偶校验的规则产生421P'P'P'。44
P'= 第4位⊕P= 1⊕1 = 0；22
P'= 第3位⊕第2位⊕P= 0⊕1⊕0 = 1；11
P'= 第3位⊕第1位⊕P= 1⊕0⊕0 = 1。421
P'P'P'=011，还原为十进制则为3，说明1011第3位出错。
需要注意：前面的讨论仅考虑数据位传输错误，而假设校验位没有传输错误，因此，若校验位传输错误，则不能被正确判断。如考虑校验位错误也能被判断，则在增加校验位时需将数据位和校验位一并进行二进制编码来确定所需校验位的位数。例如，数据为37654321DDDDDDD，而校验位就需要4位（即2 <（数据位数7+校验位48421数4）< 2），即PPPP，数据位和校验位的二进制编码次序为：使i7685434121校验位始终位于第2位上，排列出来如DDPDDDPDPP，即校验位始终位于第1,2,4,8位上，其余位自右至左排列数据位。这样再按类似前述方法产生校验位的值、传输和校验即可。
本节类比“小白鼠问题”探究了数据传输的检错问题解决方案，这种思想就是计算机领域的一种伟大思想“汉明码”，也称为“海明码”，但请注意本节并不是让读者学习汉明码，而只是通过该示例使读者体会计算思维的伟大之处。因此，关于汉明码检错纠错的原理还有很多内容，读者如感兴趣，可自主查阅资料。0和1与数值性信息1.4 基础知识：进位制及其相互转换1.4.1 二进制、十进制与r进制
进位计数制是一种用数码和数位（权）表示数值型信息的方法。一个数由一定数目的数码排列在一起组成，每个数码的位置规定了该数码所具有的数值等级——“权”，该位置也称为“数位”，可区分数码的个数称为“基值”。该计数制又称为以基值为进位的计数制，数位的“权”值是基值的幂，计数中，某一数位累计到基值后，向高数位进一；高数位的一，相当于低数位的基值大小。日常生活中，常见进位计数制有十进制（自然数）、十二进制（月）、二十四进制（昼夜）、六十进制（小时/分钟/秒）等。在计算机中，还有二进制、八进制和十六进制等。一般地，以后缀 B 表示二进制数，后缀 O 表示八进制数，后缀H表示十六进制数，后缀D表示十进制数，或者以（数码串）r表示一个r进制数，如图1.5所示。图1.5 r进制与十进制、二进制的概念比较示意
基值为r的r进制数值N的表示方法为：
该数表示的十进制大小为：（式1.1）。
式中：m、n为正整数，n为整数的位数，m为小数的位数，di为ri个数码0,1,…, r-1中的任意一个，r为基值，r为数位的权值，小数点位00于dr的后面。
1.十进制
当r =10时，表示十进制数。在十进制数中，10个数码为0,1,i…,9。逢十进一，其数位权值为10。210-1-2十
示例14 (245.25)= 2×10+ 4×10+ 5×10+ 2×10+ 5×10。
2.二进制
当r=2时，表示二进制数。在二进制数中，2个数码为0或1。逢二i进一，其数位权值为2。765432二
示例15 (11110101.01)=1×2+1×2+1×2+1×2+0×2+1×2+0×10-1-2十2+1×2+0×2+1×2=(245.25)。
3.八进制和十六进制
当r=8时，表示八进制数。在八进制数中，8个数码为0,1,…,7。i逢八进一，其数位权值为8。当r=16时，表示十六进制数。在十六进十十十制数中，分别用A表示(10)，用B表示(11)，用C表示(12)，用D表十十十示(13)，用E表示(14)，用F表示(15)。所以， 16个数码为0,1,2,i…,8,9,A,B,C,D,E,F。逢十六进一，其数位权值为16。210-1八十
示例16 (365.2)=3×8+6×8+5×8+2×8=(245.25)；10-1十六十
(F5.4)= F×16+5×16+4×16= (245.25)。1.4.2 进位制之间的相互转换
1.其他进制转换到十进制
表1.1给出了4种进位制之间转换的对应关系。表1.1 十进制数、二进制数、八进制数和十六进制数对照表
一个用任意进制表示的数，都可用上述式1转换成十进制数。为便于计算，可采用如下方法：整数部分和小数部分分别按下述方法转换。
整数部分采用基值重复相乘法：按括号及优先级次序，计算从最高位开始，乘基值加次高位，结果再乘基值加次次高位，一直加到个0位d为止。
示例17 11110101 B =______D。
解：。
小数部分采用基值重复相除法：按括号及优先级次序，计算从最低位开始，除基值加高位，结果再除基值，一直加到小数点为止，最后再除基值。
示例18 0.F62B H =______D。
解：N=0.F62B H = (((B÷16+2)÷16+6)÷16 +F)÷16=0.96159 D。
2.十进制转换到其他进制
整数部分和小数部分分别转换：整数部分采用基值重复相除法，即除基值取余数方法，一直除到商等于0时为止，将所得的余数从下到上排列起来即为所要求的进位制数（参见示例19）。小数部分采用基值重复相乘法，即乘基值取整数方法（参见示例20）。十进制小数转换成二进制小数时，有时永远无法使乘积变成0，在满足一定精度的情况下，可以取若干位数作为其近似值。
示例19 215 D =______B。
解：如图1.6（a）所示，不断除以基值2，直到商等于0时为止。将所得余数从下到上排列起来为11010111，便是该十进制数转换成二进制整数的结果，即215 D =11010111 B。
示例20 0.6875 D =______B。
解：如图1.6（b）所示，小数部分不断乘以基值2，将得到的各位整数从上到下排列起来为0.1011，便是该十进制小数转换成二进制小数的结果，即0.6875 D = 0.1011 B。图1.6 十进制转换成二进制的转换过程示意图
3.二进制、八进制、十六进制转换iii34ii
由于二进制权值2、八进制权值8=2、十六进制权值16=2具有整指数倍数关系，即1位八进制数相当于3位二进制数，1位十六进制数相当于4位二进制数，故可按如下方法转换。（1）二进制整数转换成八进制/十六进制整数的方法是：先将二进制整数从右向左每隔3位/4位分一组，再将每组按二进制数向十进制数转换的方法进行转换。（2）二进制小数转换成八进制/十六进制小数的方法是：先将二进制小数从左向右每隔3位/4位分一组，最后一组若不足3位/4位，在该组后面补相应数量的0，凑成3位/4位，再将每组按二进制数向十进制数转换的方法进行转换。
示例21 10110101 B= 265 O = B5 H。
解：第1步，将10110101按3位分组为10 110 101，按4位分组为1011 0101。
第2步，分别将每组转换成八进制数、十六进制数。
示例22 0.1011 B = 0.54 O = 0.B0 H。
解：第1步，将0.1011按3位分组为0.101 100，按4位分组为0.1011 0000。
第2步，分别将每组转换成八进制数。
分别将每一位八进制数转换成3位二进制数，每一位十六进制数转换成4位二进制数便可实现八进制数、十六进制数到二进制数之间的转换。1.5 计算之树——大学计算思维教育空间计算之树
计算（机）学科存在哪些“核心的”计算思维，哪些计算思维对学生的未来会产生影响和借鉴呢？自20世纪40年代出现电子计算机以来，计算技术与计算系统的发展好比一棵枝繁叶茂的大树，不断地成长与发展，为此本书将计算技术与计算系统的发展绘制成一棵树，如图1.7所示，称为“计算之树”。试图通过计算之树概括大学计算思维的教育空间，为学生指明未来的学习方向。图1.7 计算之树——大学计算思维教育空间
树根体现的是奠基性的技术或思维：“0和1”“程序”“递归”。树干体现的是通用计算环境的演化：“冯·诺依曼机”、“个人计算环境”、“并行分布环境”和“云计算环境”。树枝的黑、灰颜色体现的是“算法”和“系统”——两种不同的思维。各个树枝体现的是计算学科的分支研究方向，也体现了与其他学科相互融合产生的新研究方向，由树枝到树干，体现的是“抽象”，越来越抽象，而从树干到树枝，体现的是“自动化”，越来越自动化。有3个层面的抽象与自动化机制，“协议”和“编解码器”、“语言”和“编译器”、“模型”和“系统（即执行引擎）”。由内向外的3个同心半圆，可看到一边是“网络化”思维的发展，一边是“数据化”思维的发展。
这棵计算之树，给出了很多术语来刻画相应的计算思维，这些术语并不要求读者现在理解，它们将贯穿整本教材，将在课程中陆陆续续地加以学习，理解这些术语及其所体现的计算思维对今后构造、设计和应用计算技术/计算系统将有重要的影响。1.6 为什么要学习和怎样学习计算思维1.6.1 为什么：设计、构造和应用典型的计算工具需要计算思维
为什么要学习计算思维，从以下两个方面来看。
一是大趋势大环境。目前，社会已发展到信息化与智能化社会阶段，计算+、互联网+、大数据+、信息+、智能+，已经呈现出计算（机）与社会/自然（各学科）深度融合的趋势，不仅计算（机）学科要融合各个学科，而各个学科也逐渐在融合计算（机）学科，各学科的高端研究正由传统的学科问题向体现“自动化/计算化→网络化→智能化”的学科问题发展。体现这种融合的“新工科”的发展正在成为国家战略，而这种新工科需要的是计算思维教育，而不仅仅是计算机的使用。
二是毕业后可能从事的工作。在前述大趋势、大环境下，各学科同学毕业后主要从事两个方面的工作，基本上都离不开计算机（不一定是传统意义的台式机或笔记本电脑），如图1.8所示。图1.8 未来工作场景示意（1）应用各种“计算/仿真系统”进行本学科问题研究，例如，医生运用“诊疗辅助仪器”等进行病情诊断与医学问题研究。此时了解一些计算思维，对其更好地理解仪器及其产生的结果，从而做出更精确的诊断或研究有很大的帮助。（2）构造并设计这些“计算/仿真系统”。真正伟大的创新不是应用这些“计算/仿真系统”，而是能够创造这些“计算/仿真系统”给更多的人使用，诺贝尔化学奖奖励的是对设计/构造这些“计算/仿真系统”有重要贡献的科学家。若在毕业后“能做出”“能应用”这些“计算/仿真系统”，则在初入大学的时刻应注意学习计算思维，注意对计算思维的深入理解，注意联想本学科的思维，注意与本学科思维的交叉融合。随着专业课程的深入学习，将越来越多地思考计算思维的应用，这样才能达成毕业后“能做出”“能应用”的目标。1.6.2 怎样学：了解认知学习的不同深度
关于怎样学习，要了解评价认知学习不同深度的一种模型——Bloom分类法，其对认知层次，即学习深度定义了6个层次：（1）了解——学习过后，是否能回忆起或记住知识，是否能够区分与辨识知识；（2）理解——学习过后，是否能够用自己的话陈述或解释知识；（3）应用——学习过后，是否能够在新的场景下运用学过的知识；（4）分析——学习过后，是否能够从不同的角度分解或分析知识并做更透彻的理解；（5）综合——学习过后，是否能够综合不同的知识产生新的概念新的知识；（6）评价——学习过后，是否能够量化评价一项决策。
后人对“Bloom分类法”又进行了改进，形成了新的6个层次，分别是记忆（了解）、理解、应用、分析、评价和创造。所谓“创造”，即学习过后，是否能够创造新产品或新观点。1.6.3 怎样学：对比—联想式学习方法
本章不仅仅是在学概念学知识，更重要的是用“对比—联想”的方法学习思维。这种对比—联想式学习方法是一种重要的学习方法，尤其对思维类的课程学习很重要。
回忆一下，本章首先学习了“用小白鼠检验毒水瓶”这样一个趣味题目，进一步分析这道题目背后的思维究竟是怎样的，这些深层次的内容，即计算思维，需要读者来体验，而不仅仅是学习“计算思维”这样一个概念。再进一步又以“传输校验问题”这个不同的场景，用对比的语言，探究了计算思维的运用，揭示计算思维的价值。注意不要纠结一些术语本身，而要注意体验这样伟大的思维是完全可以借鉴小白鼠这个趣味题目的思维来研究和发现的。这种“趣味故事→思维挖掘→价值再现→对比联想”的学习方式，可有效地促进计算与各专业的思维融合，现在各专业学生在学习计算思维的过程中联想本专业的思维，将来在学习专业的过程中就会联想计算思维。从学而有趣→学而有思→学而有用→学而有（探）索，逐渐探索未知的奇妙世界，培养自己的研究与工程素质。
下面用“Bloom分类法”模型评价本章的学习成果。完成了1.1节和1.2节的学习，应该达到“了解”或“理解”的程度。完成1.3节的学习，应该达到“应用”的程度，如果学习到位，还可达到“分析”（不同角度的分析）与“综合”（归纳并产生新的概念，对规则的总结）的程度，并体验“创造”的快乐。1.4节是基础知识，建议达到“应用”程度。1.5节是概述，只需达到“了解”程度即可。之所以说是“应该达到”，是因为这取决于学生如何学习，例如，如果只是听一遍讲解，则可能只是“了解”，但如果又进行了复述，则可能“理解”，接着又做了不同的习题，则可能达到“应用”程度。第2章 计算思维基础：0和1与逻辑本章摘要
万事万物最终都可被符号化为0和1，也就都能基于0和1进行计算。逻辑运算是最基本的基于0和1的运算方法，人类使用逻辑进行思维，计算机使用逻辑实现自动化，所有运算最终都被转换成逻辑运算进而被计算机执行。0和1与逻辑是计算思维的基础，符号化—计算化—自动化是计算机的本质。本章学习万事万物符号化为0和1的方法，以及逻辑的不同应用方法。2.1 用0和1表示万事万物0和1与非数值性信息
英文字母与各种符号可用0和1表示，中文汉字也可以用0和1表示，音频、视频及万事万物都可通过采样、量化、编码的方法用0和1表示。既然万事万物最终都可被符号化为0和1，也就都能基于0和1进行计算。人类使用各种符号进行的运算，都可通过基于0和1的运算来让机器完成。如图2.1所示即为符号化与计算化简要示意图。图2.1 符号化与计算化简要示意图2.1.1 用0和1进行编码
类似于英文字母与符号这种非数值信息，可采用编码来表示。所谓“编码”就是以若干位数码或符号的不同组合来表示非数值性信息的方法，它是人为地将若干位数码或符号的每一种组合指定一种唯一的含义。
例如，可以指定“0表示男，1表示女”；也可以指定“1表示男，0表示女”。
再例如，可以指定“从000始至110止分别表示周一至周日”；也
试读结束[说明：试读内容隐藏了图片]