不插电的计算机科学.pdf

不插电的计算机科学不插电的计算机科学不插电的计算机科学不插电的计算机科学主讲：叶永飞Computer Science UnpluggedComputer Science UnpluggedComputer Science UnpluggedComputer Science UnpluggedComputer Science UnpluggedComputer Science UnpluggedComputer Science UnpluggedComputer Science Unplugged“ “ “ “不插电的计算机科学不插电的计算机科学” ” ” ”项目项目 (Computer Science Unplugged)(Computer Science Unplugged)(Computer Science Unplugged)(Computer Science Unplugged)是一个是一个 世界范围的信息科学普及项目，它透过世界范围的信息科学普及项目，它透过 一些既有趣又容易的活动，来达到学习一些既有趣又容易的活动，来达到学习 “ “ “ “计算机科学计算机科学” ” ” ”的目的。

的目的�品种繁多的计算机品种繁多的计算机�课程的意义课程的意义旨在让学生们在学习程序设计之前，先来旨在让学生们在学习程序设计之前，先来旨在让学生们在学习程序设计之前，先来旨在让学生们在学习程序设计之前，先来 探寻、领悟计算机动作及其解决问题的精妙思探寻、领悟计算机动作及其解决问题的精妙思探寻、领悟计算机动作及其解决问题的精妙思探寻、领悟计算机动作及其解决问题的精妙思 想，并且开发他们的想，并且开发他们的想，并且开发他们的想，并且开发他们的“ “ “ “计算思维计算思维计算思维计算思维” ” ” ”来提高解决问来提高解决问来提高解决问来提高解决问 题的能力题的能力题的能力题的能力�教学方法教学方法不需要深入讲解专业的计算机知识，只要不需要深入讲解专业的计算机知识，只要不需要深入讲解专业的计算机知识，只要不需要深入讲解专业的计算机知识，只要 学生稍稍掌握基本的数学技能和拥有一颗学习学生稍稍掌握基本的数学技能和拥有一颗学习学生稍稍掌握基本的数学技能和拥有一颗学习学生稍稍掌握基本的数学技能和拥有一颗学习 新知识的心即可完成书中所有活动新知识的心即可完成书中所有活动新知识的心即可完成书中所有活动。

新知识的心即可完成书中所有活动内 容 大 纲二进制数二进制数1 1 1 1压缩信息压缩信息2 2 2 2检测错误检测错误3 3 3 3排序排序4 4 4 4路由和死锁路由和死锁5 5 5 5二进制数二进制数 （（BinaryBinaryBinaryBinary））二进制数与二进制数与“ “ “ “比特比特” ” ” ”�Binary 二进制数与二进制数与“ “ “ “比特比特” ” ” ”�小游戏：二进制数卡片a.a.a.a. 卡片上的圆点有怎样的规律？卡片上的圆点有怎样的规律？b.b.b.b. 如在左侧增加一张卡片，那么卡片上该画几个点？如在左侧增加一张卡片，那么卡片上该画几个点？c.c.c.c. 依照怎样的规律新增卡片？依照怎样的规律新增卡片？d.d.d.d. 用卡片表示出用卡片表示出5 5 5 5，，13131313，，28282828二进制数与二进制数与“ “ “ “比特比特” ” ” ”�计算机仅用计算机仅用0 0 0 0和和1 1 1 1来表示信息来表示信息01011=11一个比特即是一个数位，其值可以为一个比特即是一个数位，其值可以为0 0 0 0或或1 1 1 1。

A bit is just a digit that can be a zero or one.A bit is just a digit that can be a zero or one.A bit is just a digit that can be a zero or one.A bit is just a digit that can be a zero or one.二进制数与二进制数与““比特比特””� 动动脑动动脑a.a.a.a. 二进制数二进制数00110001100011000110对应的十进制数是多少？对应的十进制数是多少？b.b.b.b. 二进制数二进制数01110011100111001110对应的十进制数是多少？对应的十进制数是多少？c.c.c.c. 二进制数二进制数10001100011000110001对应的十进制数是多少？对应的十进制数是多少？6 6 6 61414141417171717算出下面各组符号表示的数值算出下面各组符号表示的数值？！？？！？！？？！= = = =( ( ( (？？=1,!=0)=1,!=0)=1,!=0)=1,!=0)◆◇◇◆◆◇◇◆= = = =( ( ( (◆◆=1, =1, =1, =1, ◇◇=0)=0)=0)=0)♀♂♀♀♂♀= = = =( ( ( (♂♂ =1, =1, =1, =1, ♀♀ =0) =0) =0) =0)二进制数与二进制数与““比特比特””�有趣的事有趣的事从小比特到大数字从小比特到大数字1 1 1 12 2 2 24 4 4 4161616168 8 8 8试一试试一试试一试试一试用用4 4 4 4只手指从只手指从0 0 0 0数到数到15151515从小比特到大数字从小比特到大数字TransistorTransistorTransistorTransistorCapacitorCapacitorCapacitorCapacitorOff=1,On=0Off=1,On=0Off=1,On=0Off=1,On=0比特的表示从小比特到大数字从小比特到大数字RAM(RAM(RAM(RAM(随机存取存储器随机存取存储器) ) ) )：：采用晶体管和电容器等元件来储存数据。

优采用晶体管和电容器等元件来储存数据优点是存取速度快，缺点是价格昂贵，且断电后数据会丢失点是存取速度快，缺点是价格昂贵，且断电后数据会丢失从小比特到大数字从小比特到大数字�用磁带或磁盘存储比特用磁带或磁盘存储比特N S S N N S S N S N N-S 表示1S-N 表示010010从小比特到大数字从小比特到大数字�CDCDCDCD碟片上存储二进制数碟片上存储二进制数吸收光：0反射光：1111100从小比特到大数字从小比特到大数字�二进制数的性质二进制数的性质1+2=？1+2+4=？1+2+4+8=？1+2+4+8+16=？计算规律？从小比特到大数字从小比特到大数字�二进制数的性质二进制数的性质 1 1 1 1、将、将0 0 0 0插入十进制数的右侧插入十进制数的右侧9 9 9 9 ————> 90> 90> 90> 90 20 20 20 20 ————> 200> 200> 200> 2002 2 2 2、将、将0 0 0 0插入二进制数的右侧插入二进制数的右侧1 1 1 1 ————> 10> 10> 10> 10 101 101 101 101 ————> 1010> 1010> 1010> 1010从小比特到大数字从小比特到大数字�思考：思考：A.A.用用5 5比特最大可以表示多少？比特最大可以表示多少？B.B.用用6 6比特最大可以表示多少？比特最大可以表示多少？C.C.用用7 7比特最大可以表示多少？比特最大可以表示多少？D.D.用用8 8比特最大可以表示多少？比特最大可以表示多少？16+8+4+2+1=31=32-164-1=63128-1=127256-1=255从小比特到大数字从小比特到大数字字节：字节：一般将连续存储的一般将连续存储的8 8 8 8比特称为一个字节比特称为一个字节(byte)(byte)(byte)(byte)，在计算机中，在计算机中 每次都将这一组比特位一起处理。

每次都将这一组比特位一起处理1Byte=8bit1Byte=8bit1Byte=8bit1Byte=8bit从小比特到大数字从小比特到大数字�大一点的二进制数大一点的二进制数怎样用二进制数来表示怎样用二进制数来表示77？？128 64 32 16 8 4 2 1128 64 32 16 8 4 2 1128 64 32 16 8 4 2 1128 64 32 16 8 4 2 100001111练习：练习：采用这种方法用二进制数来表示采用这种方法用二进制数来表示165165165165，，99999999，，127127127127，， 1000100010001000从小比特到大数字从小比特到大数字1Kilobyte=1024byte1Kilobyte=1024byte1Kilobyte=1024byte1Kilobyte=1024byte1 1 1 12 2 2 24 4 4 48 8 8 8161616161281281281283232323264646464 256256256256512512512512从小比特到大数字从小比特到大数字�读心术的小魔术读心术的小魔术从比特到字母从比特到字母一、游戏一、游戏 储藏室谜题储藏室谜题从比特到字母从比特到字母12345678910－／∨﹨abcdef11121314151617181920ghijklmnop21222324252627282930qrstuvwxyz30个元素(26字母,4个声调),空格用0表示从比特到字母从比特到字母�编码编码(encode)(encode)(encode)(encode) �解码解码(decode)(decode)(decode)(decode)hellohellohellohello12 9 16 16 1912 9 16 16 1912 9 16 16 1912 9 16 16 19编码编码解码解码从比特到字母从比特到字母01110 01110 01110 01110 ==> ==> ==> ==> 14141414 01101 ==> 1301101 ==> 1301101 ==> 1301101 ==> 13 11001 ==> 2511001 ==> 2511001 ==> 2511001 ==> 25 00100 ==> 400100 ==> 400100 ==> 400100 ==> 41 2 4 8 1610001 ==> 1710001 ==> 1710001 ==> 1710001 ==> 17 01101 ==> 1301101 ==> 1301101 ==> 1301101 ==> 13 10010 ==> 1810010 ==> 1810010 ==> 1810010 ==> 18 01011 ==> 1101011 ==> 1101011 ==> 1101011 ==> 11 00100 ==> 400100 ==> 400100 ==> 400100 ==> 400110 ==> 600110 ==> 600110 ==> 600110 ==> 6 01001 ==> 9 01001 ==> 9 01001 ==> 9 01001 ==> 9 01101 ==> 1301101 ==> 1301101 ==> 1301101 ==> 13 00100 ==> 400100 ==> 400100 ==> 400100 ==> 401111 ==> 1501111 ==> 1501111 ==> 1501111 ==> 15 11001 ==> 2511001 ==> 2511001 ==> 2511001 ==> 25 10010 ==> 1810010 ==> 1810010 ==> 18。