第1章 信息與計(jì)算思維

第1章

信息與計(jì)算思維1.1信息的概念1.2計(jì)算機(jī)中的信息表示1.3計(jì)算機(jī)與計(jì)算1.4計(jì)算思維的實(shí)踐方法1.1信息的概念信息：指音訊、消息、通信系統(tǒng)傳輸和處理的對(duì)象，泛指人類社會(huì)傳播的一切內(nèi)容。信息量：指從n個(gè)相等可能事件中選出一個(gè)事件所需要的信息度量或含量，也就是在辨識(shí)n個(gè)事件中特定的一個(gè)事件的過(guò)程中所需要提問(wèn)“是”或“否”的最少次數(shù)。1.2計(jì)算中信息的表示1.2.1進(jìn)制的基本概念進(jìn)制即表示數(shù)值的方法，它是指用一組固定的數(shù)字和一套統(tǒng)一的規(guī)則來(lái)表示數(shù)目的方法。在計(jì)算機(jī)進(jìn)制中，需要掌握數(shù)碼、基數(shù)和位權(quán)的概念。1.2計(jì)算中信息的表示1.2.1進(jìn)制的基本概念數(shù)碼：進(jìn)制中表示基本數(shù)值大小的不同數(shù)字符號(hào)。在一種進(jìn)制中，只能使用一組固定的符號(hào)來(lái)表示數(shù)的大小。十進(jìn)制：0、1、2、3、4、5、6、7、8、9

共10個(gè)數(shù)碼十六進(jìn)制：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F共16個(gè)數(shù)碼1.2計(jì)算中信息的表示1.2.1進(jìn)制的基本概念基數(shù)：一種進(jìn)制所使用數(shù)碼的個(gè)數(shù)。十進(jìn)制的基數(shù)為１０十六進(jìn)制的基數(shù)為１６1.2計(jì)算中信息的表示1.2.1進(jìn)制的基本概念位權(quán)：一個(gè)數(shù)值中某一位上的１所表示數(shù)值的大小(以基數(shù)為底的冪)。十進(jìn)制數(shù)123=1×102+2×101+3×100所以：1的位權(quán)是102，2的位權(quán)是101，3的位權(quán)是1001.2計(jì)算中信息的表示1.2.1進(jìn)制的基本概念進(jìn)制對(duì)應(yīng)的數(shù)碼表2i8i10i16i1.2計(jì)算中信息的表示1.2.2進(jìn)制表示在計(jì)算機(jī)內(nèi)部存儲(chǔ)、處理和傳遞的信息均采用二進(jìn)制代碼來(lái)表示，二進(jìn)制的基數(shù)為２，只有“０”和“１”兩個(gè)數(shù)碼。除二進(jìn)制外，計(jì)算機(jī)中常用的還有八進(jìn)制和十六進(jìn)制。1.2計(jì)算中信息的表示1.2.2進(jìn)制表示對(duì)于不同的進(jìn)制，常采用以下兩種書寫方式：1、在數(shù)字后面加一個(gè)大寫字母作為后綴，表示該數(shù)字采用的進(jìn)制；2、在括號(hào)外面加下標(biāo)。1.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換Ｒ進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)【轉(zhuǎn)換規(guī)則】采用Ｒ進(jìn)制數(shù)的位權(quán)展開法，即將Ｒ進(jìn)制數(shù)按“位權(quán)”展開形成多項(xiàng)式并求和，得到的結(jié)果就是轉(zhuǎn)換結(jié)果。(1101)2=1×23+1×22+0×21+1×20=13(732)8=7×82+3×81+2×80=474(1F04)16=1×163+15×162+0×161+4×160=79401.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換十進(jìn)制數(shù)轉(zhuǎn)換為Ｒ進(jìn)制數(shù)【轉(zhuǎn)換規(guī)則】整數(shù)部分（倒讀法）采用“逐次除以基數(shù)取余”法，直到商為０。例:(15)10轉(zhuǎn)換成二進(jìn)制數(shù)(15)10=(1111)21.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)間的相互轉(zhuǎn)換（1）二進(jìn)制

八進(jìn)制【轉(zhuǎn)換規(guī)則】三位并一位。1位八進(jìn)制數(shù)相當(dāng)于3

位二進(jìn)制數(shù)。（10010110）2=（?）8010010110226(10010110)2=(226)81.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)間的相互轉(zhuǎn)換（2）八進(jìn)制

二進(jìn)制【轉(zhuǎn)換規(guī)則】一位拆三位。把1位八進(jìn)制數(shù)寫成對(duì)應(yīng)的3位二進(jìn)制數(shù)，然后連接起來(lái)即可。（2304）8=（？）22304010000100(2304)8=(10011000100)20111.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)間的相互轉(zhuǎn)換（3）二進(jìn)制

十六進(jìn)制【轉(zhuǎn)換規(guī)則】四位并一位。1位十六進(jìn)制數(shù)相當(dāng)于4

位二進(jìn)制數(shù)。（10010110）2=（?）161001011096(10010110)2=(96)161.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)間的相互轉(zhuǎn)換（4）二進(jìn)制

十六進(jìn)制【轉(zhuǎn)換規(guī)則】一位拆四位。把1

位十六進(jìn)制數(shù)寫成對(duì)應(yīng)的4位二進(jìn)制數(shù)，然后連接起來(lái)即可。（A0E）16=（？）2A0E10101110(A0E)16=(101000001110)200001.2計(jì)算中信息的表示1.2.3不同進(jìn)制之間的轉(zhuǎn)換二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)間的相互轉(zhuǎn)換（5）其他非十進(jìn)制數(shù)之間的轉(zhuǎn)換不滿足以上幾種情況的兩個(gè)非十進(jìn)制數(shù)之間的轉(zhuǎn)換，可以先把要轉(zhuǎn)換的數(shù)值轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)，然后再將二進(jìn)制數(shù)轉(zhuǎn)換成對(duì)應(yīng)數(shù)制的數(shù)值。1.2計(jì)算中信息的表示1.2.5ASCⅡ碼在ASCⅡ碼中，規(guī)定一個(gè)字符用7

位二進(jìn)制編碼，最高位為０ASCⅡ共有128

種編碼，用來(lái)表示128個(gè)不同的字符1.2計(jì)算中信息的表示1.2.6漢字編碼1、漢字輸入碼常見的有智能ABC、五筆字型碼、搜狗輸入法等。2、漢字機(jī)內(nèi)碼又稱“漢字ASCII碼”，簡(jiǎn)稱“內(nèi)碼”，指計(jì)算機(jī)內(nèi)部存儲(chǔ)，處理加工和傳輸漢字時(shí)所用的由0和1符號(hào)組成的代碼。輸入碼被接受后就由漢字操作系統(tǒng)的“輸入碼轉(zhuǎn)換模塊”轉(zhuǎn)換為機(jī)內(nèi)碼，與所采用的鍵盤輸入法無(wú)關(guān)。國(guó)標(biāo)碼的機(jī)內(nèi)碼為兩字節(jié)長(zhǎng)的代碼。1.2計(jì)算中信息的表示1.2.6漢字編碼3、字形碼字形碼是點(diǎn)陣代碼的一種。顯示一個(gè)漢字一般采用16×16點(diǎn)陣或24×24點(diǎn)陣或48×48

點(diǎn)陣。已知漢字點(diǎn)陣的大小，可以計(jì)算出存儲(chǔ)一個(gè)漢字所需占用的字節(jié)空間。【例】使用16×16

點(diǎn)陣存儲(chǔ)一個(gè)漢字的字形，需要占用多大的存儲(chǔ)空間。16×16=256（位）/8=32（字節(jié)）000010101000字節(jié)數(shù)＝點(diǎn)陣行數(shù)×點(diǎn)陣列數(shù)/

81.3計(jì)算機(jī)與計(jì)算1.3.1計(jì)算機(jī)硬件與計(jì)算的概念１．計(jì)算機(jī)硬件的基本結(jié)構(gòu)?CPU（中央處理器）：計(jì)算機(jī)的計(jì)算部件，能夠執(zhí)行機(jī)器指令；?存儲(chǔ)器：計(jì)算機(jī)的記憶部件，用于存儲(chǔ)數(shù)據(jù)和程序；?輸入／輸出設(shè)備：輸入設(shè)備和輸出設(shè)備提供了人與計(jì)算機(jī)進(jìn)行交互的手段。1.3計(jì)算機(jī)與計(jì)算1.3.1計(jì)算機(jī)硬件與計(jì)算的概念１．計(jì)算的概念?針對(duì)一個(gè)問(wèn)題，設(shè)計(jì)出解決問(wèn)題的程序，并由計(jì)算機(jī)來(lái)執(zhí)行這個(gè)程序，這就是計(jì)算。1.3計(jì)算機(jī)與計(jì)算1.3.2計(jì)算機(jī)語(yǔ)言1、機(jī)器語(yǔ)言機(jī)器語(yǔ)言采用二進(jìn)制代碼，即所有指令都是由0和1組成的二進(jìn)制序列。2、匯編語(yǔ)言匯編語(yǔ)言本質(zhì)上是將機(jī)器指令用更加容易為人們所理解和記憶的“助憶符”形式表現(xiàn)出來(lái)。1.3計(jì)算機(jī)與計(jì)算1.3.2計(jì)算機(jī)語(yǔ)言3、高級(jí)語(yǔ)言①高級(jí)語(yǔ)言吸收了人們熟悉的自然語(yǔ)言（英語(yǔ)）和數(shù)學(xué)語(yǔ)言的某些成分，因而非常易學(xué)、易用、易讀；②高級(jí)語(yǔ)言在構(gòu)造形式和意義方面具有嚴(yán)格定義，從而避免了語(yǔ)言的歧義性；③高級(jí)語(yǔ)言與計(jì)算機(jī)硬件沒有關(guān)系，用高級(jí)語(yǔ)言寫的程序可以移植到各種計(jì)算機(jī)上執(zhí)行。1.3計(jì)算機(jī)與計(jì)算1.3.2計(jì)算機(jī)語(yǔ)言4、編譯和解釋高級(jí)語(yǔ)言的翻譯有兩種方式：編譯和解釋?！靖呒?jí)語(yǔ)言的編譯】1.3計(jì)算機(jī)與計(jì)算1.3.2計(jì)算機(jī)語(yǔ)言4、編譯和解釋高級(jí)語(yǔ)言的翻譯有兩種方式：編譯和解釋?！靖呒?jí)語(yǔ)言的解釋】1.3計(jì)算機(jī)與計(jì)算1.3.3算法解決特定問(wèn)題的一系列明確可行的步驟稱為算法。算法表達(dá)了解決問(wèn)題的核心步驟，反映的是程序解題的邏輯。1.3計(jì)算機(jī)與計(jì)算1.3.3算法【例】求兩個(gè)自然數(shù)的最大公約數(shù)。輸入：自然數(shù)a、b輸出：a、b的最大公約數(shù)步驟：①令r為a/b所得的余數(shù)；②若r=0，則算法結(jié)束，b

即為答案；

否則置a←b，b←r，轉(zhuǎn)到第①步。1.3計(jì)算機(jī)與計(jì)算1.3.3算法對(duì)算法的兩個(gè)要求：

①每個(gè)步驟必須具備明確的可操作性；

②構(gòu)成算法的所有步驟必須能在有限時(shí)間內(nèi)完成。1.3計(jì)算機(jī)與計(jì)算1.3.4實(shí)現(xiàn)當(dāng)找到解決問(wèn)題的算法后，就需要用某種計(jì)算機(jī)語(yǔ)言將這個(gè)算法表示出來(lái)，最終得到一個(gè)能被計(jì)算機(jī)執(zhí)行的程序（或代碼），這個(gè)過(guò)程稱為實(shí)現(xiàn)，俗稱為寫代碼。嚴(yán)格地說(shuō)，算法和程序是不同的：算法是用非形式化方式表述的解決問(wèn)題的過(guò)程；程序則是用形式化編程語(yǔ)言表述的精確代碼。1.4計(jì)算思維1.4.1計(jì)算思維的定義計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)以及人類行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)。1.4計(jì)算思維1.4.2計(jì)算思維的基本原則基本原則：既要充分利用計(jì)算機(jī)的計(jì)算和存儲(chǔ)能力，又不能超出計(jì)算機(jī)的能力范圍。1.4計(jì)算思維1.4.3計(jì)算思維的運(yùn)用1、問(wèn)題表示抽象是用于問(wèn)題表示的重要思維工具。計(jì)算機(jī)科學(xué)中的抽象包括數(shù)據(jù)抽象和控制抽象，簡(jiǎn)言之就是將現(xiàn)實(shí)世界中的各種數(shù)量關(guān)系、空間關(guān)系、邏輯關(guān)系和處理過(guò)程等表示成計(jì)算機(jī)世界中的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)，或者說(shuō)建立實(shí)際問(wèn)題的計(jì)算模型。1.4計(jì)算思維1.4.3計(jì)算思維的運(yùn)用2、算法設(shè)計(jì)算法設(shè)計(jì)是計(jì)算思維大顯身手的領(lǐng)域，計(jì)算機(jī)科學(xué)家采用多種思維方