不插电的计算机科学资料下载.pdf

1、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 d

2、igit 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算出下面各组符号表示的数值算出下面各组符号表示的

3、数值？！？=（？=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=0

4、Off=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反射光：1

5、111100从小比特到大数字从小比特到大数字二进制数的性质二进制数的性质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 9020 20 20 20 200 200 200 2002 2 2 2、将、将0 0 0 0插入二进制数的右侧插入二进制数的右侧1 1 1 1 10 10 10 10101 101 101 101 1010 1010 1010 1010从小比特到大数字从小比特到大数字思考：思考：A.

6、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从

7、小比特到大数字从小比特到大数字大一点的二进制数大一点的二进制数怎样用二进制数来表示怎样用二进制数来表示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=1024byte1K

8、ilobyte=1024byte1 1 1 12 2 2 24 4 4 48 8 8 8161616161281281281283232323264646464256256256256512512512512从小比特到大数字从小比特到大数字读心术的小魔术读心术的小魔术从比特到字母从比特到字母一、游戏一、游戏 储藏室谜题储藏室谜题从比特到字母从比特到字母12345678910abcdef11121314151617181920ghijklmnop21222324252627282930qrstuvwxyz30个元素（26字母,4个声调）,空格用0表示从比特到字母从比特到字母编码编码（encode

9、）（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=1414141401101=1301101=1301101=1301101=1311001=2511001=2511001=2511001=2500100=400100=400100=400100=41 2 4 8 1610001=1710001

10、=1710001=1710001=1701101=1301101=1301101=1301101=1310010=1810010=1810010=1810010=1801011=1101011=1101011=1101011=1100100=400100=400100=400100=400110=600110=600110=600110=601001=9 01001=9 01001=9 01001=9 01101=1301101=1301101=1301101=1300100=400100=400100=400100=401111=1501111=1501111=1501111=1511001

11、=2511001=2511001=2511001=2510010=1810010=1810010=1810010=1800100001000010000100 =4=4=4=414132540jiu41713181140ming4691340bei415251840kun4jijijiji m m m m ng bng bng bng b i ki ki ki k n n n n从比特到字母从比特到字母将比特转换成声音的过程称为将比特转换成声音的过程称为调制调制（modulation）（modulation）（modulation）（modulation），而将声音转换回比特的过，而将声音转换

12、回比特的过程称为程称为解调解调（demodulation）（demodulation）（demodulation）（demodulation），所以连接电，所以连接电话线和计算机的设备又称为调制解调器，简称话线和计算机的设备又称为调制解调器，简称猫猫（modem）（modem）（modem）（modem）。制作属于你自己的信息制作属于你自己的信息平安平安有趣的事从比特到图像从比特到图像从比特到图像从比特到图像图像中的小方块被称为图像中的小方块被称为图像元素图像元素（picture elements）（picture elements）（picture elements）（picture ele

13、ments）。为了便。为了便于发音，用于发音，用pixpixpixpix表示表示picturepicturepicturepicture的缩写，并结合元素的缩写，并结合元素”elementselementselementselements”开头的两个字母，组成新名词开头的两个字母，组成新名词”pixelpixelpixelpixel”。从比特到图像从比特到图像0,1,1,1,00,1,1,1,00,1,1,1,00,1,1,1,00,0,0,0,10,0,0,0,10,0,0,0,10,0,0,0,1?,?1,0,0,0,11,0,0,0,11,0,0,0,11,0,0,0,1?0,1,1,1

14、,10,1,1,1,10,1,1,1,10,1,1,1,1从比特到图像从比特到图像游程编码游程编码（run-length encoding,RLE）（run-length encoding,RLE）（run-length encoding,RLE）（run-length encoding,RLE）0,1,1,1,00,0,0,0,1?1,0,0,0,1?0,1,1,1,11,3,14,1?0,1,3,1?1,4从比特到图像从比特到图像 小游戏：图像解码小游戏：图像解码4,114,9,2,14,9,2,14,114,94,95,70,171,15压缩信息压缩信息（Compressing Info

15、rmation）（Compressing Information）（Compressing Information）（Compressing Information）压缩信息压缩信息滑动窗口压缩滑动窗口压缩（LZ compression）（LZ compression）（LZ compression）（LZ compression）Pease porridgeNine days Some like ithotcoldIn the pPease porridge hot,Pease porridge hot,Pease porridge hot,Pease porridge hot,Pease

16、porridge cold,Pease porridge cold,Pease porridge cold,Pease porridge cold,Pease porridge in the pot,Pease porridge in the pot,Pease porridge in the pot,Pease porridge in the pot,Nine days old.Nine days old.Nine days old.Nine days old.Some like it hot,Some like it hot,Some like it hot,Some like it ho

17、t,Some like it cold,Some like it cold,Some like it cold,Some like it cold,Some like it in the pot,Some like it in the pot,Some like it in the pot,Some like it in the pot,Nine days old.Nine days old.Nine days old.Nine days old.压缩信息压缩信息文字的压缩文字的压缩Pitter patterPitter patterPitter patterPitter patterPitt

18、er paPitter paPitter paPitter paPitter patterPitter patterPitter patterPitter patter -Pitter Pitter Pitter Pitter papapapa（7,4）（7,4）（7,4）（7,4）压缩信息压缩信息考考你考考你miss（3,4）ppimiss（3,4）ppimiss（3,4）ppimiss（3,4）ppi?解压缩解压缩mississipmississipmississipmississippipipipi检测错误检测错误（Finding Errors）（Finding Errors）（Find

19、ing Errors）（Finding Errors）检测错误检测错误小游戏：小游戏：翻卡魔术翻卡魔术被翻过的卡片被翻过的卡片检测错误检测错误奇偶校验奇偶校验（parity）parity）parity）parity）一词的英文来源于词根一词的英文来源于词根”pairpairpairpair”（对对），偶校验，偶校验（even（even（even（even parity）parity）parity）parity）表示物件的总数量为偶数，奇校验表示物件的总数量为偶数，奇校验（odd parity）（odd parity）（odd parity）（odd parity）表示它们不能被表示它们不能被组

20、成对。组成对。检测错误检测错误发现更多的错误发现更多的错误1.1.1.1.翻动翻动翻动翻动2 2 2 2张卡片能检测出来吗？能修正吗？张卡片能检测出来吗？2.2.2.2.翻动翻动翻动翻动3 3 3 3张卡片能检测出来吗？3.3.3.3.翻动翻动翻动翻动4 4 4 4张卡片能检测出来吗？Number of ErrorsAlways Detect?Always Correct?1Yesyes2 or 3YesNo4NoNo检测错误检测错误 例子：例子：RAID5（RAID5（RAID5（RAID5（独立冗余磁盘阵列独立冗余磁盘阵列）？检测错误检测错误 小游戏：ISBN（International

21、Standard Book Number）检测，最后一位数字称计算机校验码（check digit）。【例】计算10位ISBN的校验码。ISBN 0-13-911991-4（0X10）+（1X9）+（9X3）+（1X2）=172172 11=15711-7=4检测错误检测错误【例】计算13位ISBN的校验码。ISBN 978-897283571-4（9X1）+（7X3）+（8X1）+（8X3）+（7X1）+（1X3）=146146 10=14610-6=4 思考：如果两个数字颠倒、或者错写一位如果两个数字颠倒、或者错写一位数字，结果怎样？数字，结果怎样？排序排序（Sorting）（Sortin

22、g）（Sorting）（Sorting）排序排序选择排序选择排序（selection sort）（selection sort）（selection sort）（selection sort）20g70g60g40g10g30g80g50g排序排序排序方案：排序方案：每次从未排序的物体中找出质量最轻者。最佳方案是让最轻的重物始终都在天平的同一端，然后最佳方案是让最轻的重物始终都在天平的同一端，然后最佳方案是让最轻的重物始终都在天平的同一端，然后最佳方案是让最轻的重物始终都在天平的同一端，然后拿其他重物过来和它进行比较，如果遇到更轻的重物，拿其他重物过来和它进行比较，如果遇到更轻的重物，拿其他重

23、物过来和它进行比较，如果遇到更轻的重物，拿其他重物过来和它进行比较，如果遇到更轻的重物，就用这个更轻的取代之前最轻重物的位置。就用这个更轻的取代之前最轻重物的位置。20g70g60g50g40g10g30g80g总共比较的次数为：7+6+5+4+3+2+1排序后：排序后：效率不高效率不高排序排序插入排序插入排序（insertion sort）（insertion sort）（insertion sort）（insertion sort）：在一个未排序的序列中在一个未排序的序列中在一个未排序的序列中在一个未排序的序列中依次移出每个对象将它们插入到有序序列中正确的位置依次移出每个对象将它们插入到有

24、序序列中正确的位置依次移出每个对象将它们插入到有序序列中正确的位置依次移出每个对象将它们插入到有序序列中正确的位置。30g70g60g10g40g80g20g50g总共比较的次数为：最佳情况只需比较7次，最糟情况比较28次（1+2+3+7）。排序排序冒泡排序冒泡排序（bubble sort）（bubble sort）（bubble sort）（bubble sort）：将整个序列反复扫描，并将整个序列反复扫描，并将整个序列反复扫描，并将整个序列反复扫描，并交换所有相对位置错误的相邻数据的方法。当检查整交换所有相对位置错误的相邻数据的方法。当检查整个序列发现不用交换任何数据时便证明序列已被排好个

25、序列发现不用交换任何数据时便证明序列已被排好个序列发现不用交换任何数据时便证明序列已被排好个序列发现不用交换任何数据时便证明序列已被排好序了。序了。效率最低效率最低20g40g80g10g30g50g60g70g总共比较的次数为：最佳情况只需比较7次，最糟情况比较49次（7X7）。排序排序快速排序快速排序（quicksort）（quicksort）（quicksort）（quicksort）：第一步选取一个重物，将其第一步选取一个重物，将其第一步选取一个重物，将其第一步选取一个重物，将其放置在天平的一端。第二步，将剩下的所有重物依次和放置在天平的一端。第二步，将剩下的所有重物依次和这个重物进行

26、比较，将较轻的放在你的左边，较重的放这个重物进行比较，将较轻的放在你的左边，较重的放这个重物进行比较，将较轻的放在你的左边，较重的放这个重物进行比较，将较轻的放在你的左边，较重的放在你的右边，然后将之前选取的重物放在两组之间。然在你的右边，然后将之前选取的重物放在两组之间。然后再对每一组重复此过程，直到每一组中只有一个对象后再对每一组重复此过程，直到每一组中只有一个对象后再对每一组重复此过程，直到每一组中只有一个对象后再对每一组重复此过程，直到每一组中只有一个对象。20g60g80g50g30g10g40g70g20g30g10g40g60g80g70g20g70g60g50g40g10g30

27、g80g排序后排序后排序排序快速排序总共比较的次数为：最佳情况只需比较13-14次，最糟情况比较28次（7X7）。排序排序归并排序归并排序（merge sort）（merge sort）（merge sort）（merge sort）：首先将待排序序列随机分首先将待排序序列随机分首先将待排序序列随机分首先将待排序序列随机分成两组且两组中对象数相同成两组且两组中对象数相同成两组且两组中对象数相同成两组且两组中对象数相同（如果对象总数为奇数的话如果对象总数为奇数的话如果对象总数为奇数的话如果对象总数为奇数的话，两组数量则应接近相等，两组数量则应接近相等，两组数量则应接近相等，两组数量则应接近相等）。然后分别对两组对象进行。然后分别对两组对象进行排序，再将两组对象归并起来。排序，再将两组对象归并起来。30g50g60g10g30g70g80g40g对子序列再进行归并排序，直至所有的子序列都变对子序列再进行归并排序，直至所有