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

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

《不插电的计算机科学资料下载.pdf》由会员分享，可在线阅读，更多相关《不插电的计算机科学资料下载.pdf（65页珍藏版）》请在冰点文库上搜索。

c.c.c.c.依照怎样的规律新增卡片？

依照怎样的规律新增卡片？

d.d.d.d.用卡片表示出用卡片表示出5555，13131313，28282828。

二进制数与二进制数与“比特比特”计算机仅用计算机仅用0000和和1111来表示信息来表示信息01011=11一个比特即是一个数位，其值可以为一个比特即是一个数位，其值可以为0000或或1111。

Abitisjustadigitthatcanbeazeroorone.Abitisjustadigitthatcanbeazeroorone.Abitisjustadigitthatcanbeazeroorone.Abitisjustadigitthatcanbeazeroorone.二进制数与二进制数与“比特比特”动动脑动动脑a.a.a.a.二进制数二进制数00110001100011000110对应的十进制数是多少？

对应的十进制数是多少？

b.b.b.b.二进制数二进制数01110011100111001110对应的十进制数是多少？

c.c.c.c.二进制数二进制数10001100011000110001对应的十进制数是多少？

66661414141417171717算出下面各组符号表示的数值算出下面各组符号表示的数值？

！

？

=（？

=1,!

=0）=1,!

=0）=（=1,=1,=1,=1,=0）=0）=0）=0）=（=1,=1,=1,=1,=0）=0）=0）=0）二进制数与二进制数与“比特比特”有趣的事有趣的事从小比特到大数字从小比特到大数字111122224444161616168888试一试试一试试一试试一试用用4444只手指从只手指从0000数到数到15151515从小比特到大数字从小比特到大数字TransistorTransistorTransistorTransistorCapacitorCapacitorCapacitorCapacitorOff=1,On=0Off=1,On=0Off=1,On=0Off=1,On=0比特的表示从小比特到大数字从小比特到大数字RAM（RAM（RAM（RAM（随机存取存储器随机存取存储器）：

采用晶体管和电容器等元件来储存数据。

优采用晶体管和电容器等元件来储存数据。

优点是存取速度快，缺点是价格昂贵，且断电后数据会丢失。

点是存取速度快，缺点是价格昂贵，且断电后数据会丢失。

从小比特到大数字从小比特到大数字用磁带或磁盘存储比特用磁带或磁盘存储比特NSSNNSSNSNN-S表示1S-N表示010010从小比特到大数字从小比特到大数字CDCDCDCD碟片上存储二进制数碟片上存储二进制数吸收光：

0反射光：

1111100从小比特到大数字从小比特到大数字二进制数的性质二进制数的性质1+2=？

1+2+4=？

1+2+4+8=？

1+2+4+8+16=？

计算规律？

从小比特到大数字从小比特到大数字二进制数的性质二进制数的性质1111、将、将0000插入十进制数的右侧插入十进制数的右侧999990909090202020202002002002002222、将、将0000插入二进制数的右侧插入二进制数的右侧1111101010101011011011011010101010101010从小比特到大数字从小比特到大数字思考：

思考：

A.A.用用55比特最大可以表示多少？

比特最大可以表示多少？

B.B.用用66比特最大可以表示多少？

C.C.用用77比特最大可以表示多少？

D.D.用用88比特最大可以表示多少？

16+8+4+2+1=31=32-164-1=63128-1=127256-1=255从小比特到大数字从小比特到大数字字节：

字节：

一般将连续存储的一般将连续存储的8888比特称为一个字节比特称为一个字节（byte）（byte）（byte）（byte），在计算机中，在计算机中每次都将这一组比特位一起处理。

每次都将这一组比特位一起处理。

1Byte=8bit1Byte=8bit1Byte=8bit1Byte=8bit从小比特到大数字从小比特到大数字大一点的二进制数大一点的二进制数怎样用二进制数来表示怎样用二进制数来表示77？

128643216842112864321684211286432168421128643216842100001111练习：

练习：

采用这种方法用二进制数来表示采用这种方法用二进制数来表示165165165165，99999999，127127127127，1000100010001000。

从小比特到大数字从小比特到大数字1Kilobyte=1024byte1Kilobyte=1024byte1Kilobyte=1024byte1Kilobyte=1024byte1111222244448888161616161281281281283232323264646464256256256256512512512512从小比特到大数字从小比特到大数字读心术的小魔术读心术的小魔术从比特到字母从比特到字母一、游戏一、游戏储藏室谜题储藏室谜题从比特到字母从比特到字母12345678910abcdef11121314151617181920ghijklmnop21222324252627282930qrstuvwxyz30个元素（26字母,4个声调）,空格用0表示从比特到字母从比特到字母编码编码（encode）（encode）（encode）（encode）解码解码（decode）（decode）（decode）（decode）hellohellohellohello129161619129161619129161619129161619编码编码解码解码从比特到字母从比特到字母01110011100111001110=1414141401101=1301101=1301101=1301101=1311001=2511001=2511001=2511001=2500100=400100=400100=400100=412481610001=1710001=1710001=1710001=1701101=1301101=1301101=1301101=1310010=1810010=1810010=1810010=1801011=1101011=1101011=1101011=1100100=400100=400100=400100=400110=600110=600110=600110=601001=901001=901001=901001=901101=1301101=1301101=1301101=1300100=400100=400100=400100=401111=1501111=1501111=1501111=1511001=2511001=2511001=2511001=2510010=1810010=1810010=1810010=1800100001000010000100=4=4=4=414132540jiu41713181140ming4691340bei415251840kun4jijijijimmmmngbngbngbngbikikikiknnnn从比特到字母从比特到字母将比特转换成声音的过程称为将比特转换成声音的过程称为调制调制（modulation）（modulation）（modulation）（modulation），而将声音转换回比特的过，而将声音转换回比特的过程称为程称为解调解调（demodulation）（demodulation）（demodulation）（demodulation），所以连接电，所以连接电话线和计算机的设备又称为调制解调器，简称话线和计算机的设备又称为调制解调器，简称猫猫（modem）（modem）（modem）（modem）。

制作属于你自己的信息制作属于你自己的信息平安平安有趣的事从比特到图像从比特到图像从比特到图像从比特到图像图像中的小方块被称为图像中的小方块被称为图像元素图像元素（pictureelements）（pictureelements）（pictureelements）（pictureelements）。

为了便。

为了便于发音，用于发音，用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,10,1,1,1,10,1,1,1,10,1,1,1,1从比特到图像从比特到图像游程编码游程编码（run-lengthencoding,RLE）（run-lengthencoding,RLE）（run-lengthencoding,RLE）（run-lengthencoding,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压缩信息压缩信息（CompressingInformation）（CompressingInformation）（CompressingInformation）（CompressingInformation）压缩信息压缩信息滑动窗口压缩滑动窗口压缩（LZcompression）（LZcompression）（LZcompression）（LZcompression）PeaseporridgeNinedaysSomelikeithotcoldInthepPeaseporridgehot,Peaseporridgehot,Peaseporridgehot,Peaseporridgehot,Peaseporridgecold,Peaseporridgecold,Peaseporridgecold,Peaseporridgecold,Peaseporridgeinthepot,Peaseporridgeinthepot,Peaseporridgeinthepot,Peaseporridgeinthepot,Ninedaysold.Ninedaysold.Ninedaysold.Ninedaysold.Somelikeithot,Somelikeithot,Somelikeithot,Somelikeithot,Somelikeitcold,Somelikeitcold,Somelikeitcold,Somelikeitcold,Somelikeitinthepot,Somelikeitinthepot,Somelikeitinthepot,Somelikeitinthepot,Ninedaysold.Ninedaysold.Ninedaysold.Ninedaysold.压缩信息压缩信息文字的压缩文字的压缩PitterpatterPitterpatterPitterpatterPitterpatterPitterpaPitterpaPitterpaPitterpaPitterpatterPitterpatterPitterpatterPitterpatter-PitterPitterPitterPitterpapapapa（7,4）（7,4）（7,4）（7,4）压缩信息压缩信息考考你考考你miss（3,4）ppimiss（3,4）ppimiss（3,4）ppimiss（3,4）ppi?

解压缩解压缩mississipmississipmississipmississippipipipi检测错误检测错误（FindingErrors）（FindingErrors）（FindingErrors）（FindingErrors）检测错误检测错误小游戏：

小游戏：

翻卡魔术翻卡魔术被翻过的卡片被翻过的卡片检测错误检测错误奇偶校验奇偶校验（parity）parity）parity）parity）一词的英文来源于词根一词的英文来源于词根”pairpairpairpair”（对对），偶校验，偶校验（even（even（even（evenparity）parity）parity）parity）表示物件的总数量为偶数，奇校验表示物件的总数量为偶数，奇校验（oddparity）（oddparity）（oddparity）（oddparity）表示它们不能被表示它们不能被组成对。

组成对。

检测错误检测错误发现更多的错误发现更多的错误1.1.1.1.翻动翻动翻动翻动2222张卡片能检测出来吗？

能修正吗？

张卡片能检测出来吗？

2.2.2.2.翻动翻动翻动翻动3333张卡片能检测出来吗？

3.3.3.3.翻动翻动翻动翻动4444张卡片能检测出来吗？

NumberofErrorsAlwaysDetect?

AlwaysCorrect?

1Yesyes2or3YesNo4NoNo检测错误检测错误例子：

例子：

RAID5（RAID5（RAID5（RAID5（独立冗余磁盘阵列独立冗余磁盘阵列）？

检测错误检测错误小游戏：

ISBN（InternationalStandardBookNumber）检测，最后一位数字称计算机校验码（checkdigit）。

【例】计算10位ISBN的校验码。

ISBN0-13-911991-4（0X10）+（1X9）+（9X3）+（1X2）=17217211=15711-7=4检测错误检测错误【例】计算13位ISBN的校验码。

ISBN978-897283571-4（9X1）+（7X3）+（8X1）+（8X3）+（7X1）+（1X3）=14614610=14610-6=4思考：

如果两个数字颠倒、或者错写一位如果两个数字颠倒、或者错写一位数字，结果怎样？

数字，结果怎样？

排序排序（Sorting）（Sorting）（Sorting）（Sorting）排序排序选择排序选择排序（selectionsort）（selectionsort）（selectionsort）（selectionsort）20g70g60g40g10g30g80g50g排序排序排序方案：

排序方案：

每次从未排序的物体中找出质量最轻者。

最佳方案是让最轻的重物始终都在天平的同一端，然后最佳方案是让最轻的重物始终都在天平的同一端，然后最佳方案是让最轻的重物始终都在天平的同一端，然后最佳方案是让最轻的重物始终都在天平的同一端，然后拿其他重物过来和它进行比较，如果遇到更轻的重物，拿其他重物过来和它进行比较，如果遇到更轻的重物，拿其他重物过来和它进行比较，如果遇到更轻的重物，拿其他重物过来和它进行比较，如果遇到更轻的重物，就用这个更轻的取代之前最轻重物的位置。

就用这个更轻的取代之前最轻重物的位置。

20g70g60g50g40g10g30g80g总共比较的次数为：

7+6+5+4+3+2+1排序后：

排序后：

效率不高效率不高排序排序插入排序插入排序（insertionsort）（insertionsort）（insertionsort）（insertionsort）：

在一个未排序的序列中在一个未排序的序列中在一个未排序的序列中在一个未排序的序列中依次移出每个对象将它们插入到有序序列中正确的位置依次移出每个对象将它们插入到有序序列中正确的位置依次移出每个对象将它们插入到有序序列中正确的位置依次移出每个对象将它们插入到有序序列中正确的位置。

30g70g60g10g40g80g20g50g总共比较的次数为：

最佳情况只需比较7次，最糟情况比较28次（1+2+3+7）。

排序排序冒泡排序冒泡排序（bubblesort）（bubblesort）（bubblesort）（bubblesort）：

将整个序列反复扫描，并将整个序列反复扫描，并将整个序列反复扫描，并将整个序列反复扫描，并交换所有相对位置错误的相邻数据的方法。

当检查整交换所有相对位置错误的相邻数据的方法。

当检查整个序列发现不用交换任何数据时便证明序列已被排好个序列发现不用交换任何数据时便证明序列已被排好个序列发现不用交换任何数据时便证明序列已被排好个序列发现不用交换任何数据时便证明序列已被排好序了。

序了。

效率最低效率最低20g40g80g10g30g50g60g70g总共比较的次数为：

最佳情况只需比较7次，最糟情况比较49次（7X7）。

排序排序快速排序快速排序（quicksort）（quicksort）（quicksort）（quicksort）：

第一步选取一个重物，将其第一步选取一个重物，将其第一步选取一个重物，将其第一步选取一个重物，将其放置在天平的一端。

第二步，将剩下的所有重物依次和放置在天平的一端。

第二步，将剩下的所有重物依次和这个重物进行比较，将较轻的放在你的左边，较重的放这个重物进行比较，将较轻的放在你的左边，较重的放这个重物进行比较，将较轻的放在你的左边，较重的放这个重物进行比较，将较轻的放在你的左边，较重的放在你的右边，然后将之前选取的重物放在两组之间。

然在你的右边，然后将之前选取的重物放在两组之间。

然后再对每一组重复此过程，直到每一组中只有一个对象后再对每一组重复此过程，直到每一组中只有一个对象后再对每一组重复此过程，直到每一组中只有一个对象后再对每一组重复此过程，直到每一组中只有一个对象。

20g60g80g50g30g10g40g70g20g30g10g40g60g80g70g20g70g60g50g40g10g30g80g排序后排序后排序排序快速排序总共比较的次数为：

最佳情况只需比较13-14次，最糟情况比较28次（7X7）。

排序排序归并排序归并排序（mergesort）（mergesort）（mergesort）（mergesort）：

首先将待排序序列随机分首先将待排序序列随机分首先将待排序序列随机分首先将待排序序列随机分成两组且两组中对象数相同成两组且两组中对象数相同成两组且两组中对象数相同成两组且两组中对象数相同（如果对象总数为奇数的话如果对象总数为奇数的话如果对象总数为奇数的话如果对象总数为奇数的话，两组数量则应接近相等，两组数量则应接近相等，两组数量则应接近相等，两组数量则应接近相等）。

然后分别对两组对象进行。

然后分别对两组对象进行排序，再将两组对象归并起来。

排序，再将两组对象归并起来。

30g50g60g10g30g70g80g40g对子序列再进行归并排序，直至所有的子序列都变对子序列再进行归并排序，直至所有