計(jì)算思維與信息表示

1、 計(jì)算思維計(jì)算思維與計(jì)算機(jī)中的信息表示與計(jì)算機(jī)中的信息表示計(jì)算思維計(jì)算機(jī)中的信息表示 2006年3月，美國(guó)卡內(nèi)基梅隆大學(xué)計(jì)算機(jī)科學(xué)系主任周以真（Jeannette M. Wing）教授在美國(guó)計(jì)算機(jī)權(quán)威期刊Communications of the ACM雜志上給出，并定義的計(jì)算思維（Computational Thinking）。周教授認(rèn)為： 計(jì)算思維計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問(wèn)題求解、系問(wèn)題求解、系統(tǒng)設(shè)計(jì)統(tǒng)設(shè)計(jì)、以及人類行為理解人類行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)。 21世紀(jì)每個(gè)人都應(yīng)該具備的能力。計(jì)算思維計(jì)算思維計(jì)算思維是人類應(yīng)具備的第三種思維理論思維理論思維：對(duì)

2、事物的感性認(rèn)識(shí)資料，經(jīng)過(guò)抽象抽象、概括概括，形成描述事物本質(zhì)的概念，主要以推理推理和演繹演繹的方法，探尋概念之間相互聯(lián)系的一種思維活動(dòng)。實(shí)驗(yàn)思維實(shí)驗(yàn)思維：通過(guò)觀察觀察和實(shí)驗(yàn)實(shí)驗(yàn)的手段，揭示自然規(guī)律法則的一種思維方法。特征是觀察、整理、歸納、對(duì)比和驗(yàn)證特征是觀察、整理、歸納、對(duì)比和驗(yàn)證。計(jì)算思維計(jì)算思維：構(gòu)造思維，是指從具體的算法設(shè)計(jì)設(shè)計(jì)規(guī)范入手，通過(guò)算法過(guò)程的構(gòu)造構(gòu)造與實(shí)施，來(lái)解決給定問(wèn)題的一種思維方法。在當(dāng)前環(huán)境下，理論與實(shí)驗(yàn)手段面臨大規(guī)模數(shù)據(jù)的情況下，不可避免的要用計(jì)算手段來(lái)輔助進(jìn)行。計(jì)算機(jī)能干什么計(jì)算機(jī)能干什么 多記憶一些數(shù)據(jù)，多接收一些信息，算的快一些，交流方便些。 以億次的計(jì)算，求解

3、繁復(fù)的微分方程和方程組，描繪超乎想象的圖像，模擬無(wú)法實(shí)現(xiàn)或耗資巨大的過(guò)程等等。計(jì)算機(jī)不能干什么計(jì)算機(jī)不能干什么 不能替人拿主意、定方案 人機(jī)分界面恰在思考二字，即把計(jì)算機(jī)所不具備的直覺(jué)、綜合、機(jī)敏，甚至藝術(shù)家的靈感留給人，由人來(lái)創(chuàng)造性的開發(fā)各種所需的算法、模型、方法。計(jì)算思維的關(guān)鍵計(jì)算思維的關(guān)鍵：用計(jì)算機(jī)模擬現(xiàn)實(shí)世界計(jì)算思維的本質(zhì)計(jì)算思維的本質(zhì): 抽象和自動(dòng)化 計(jì)算思維中的抽象完全超越物理的時(shí)空觀，并完全用符號(hào)來(lái)表示。自動(dòng)化是機(jī)械地一步一步自動(dòng)執(zhí)行，其基礎(chǔ)和前提是抽象。 案例：18世紀(jì)著名的古典數(shù)學(xué)問(wèn)題哥尼斯堡七橋問(wèn)題。哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題哥尼斯堡地處東普魯士，位于普雷格爾河的兩岸

4、及河中心的兩個(gè)島上，城市各部分由七座橋與兩岸連結(jié)起來(lái)。多年來(lái)，當(dāng)?shù)氐木用窨傆幸粋€(gè)愿望：從家里出去散步，能否通過(guò)沒(méi)每座橋恰好一次，再返回家中？但是任何人也沒(méi)有找到這樣一條理想的路徑。1976年，瑞士數(shù)學(xué)家歐拉(Euler)解決問(wèn)題的辦法是把陸地抽陸地抽象為一個(gè)點(diǎn)象為一個(gè)點(diǎn)，用連接兩個(gè)點(diǎn)的線段表示橋梁用連接兩個(gè)點(diǎn)的線段表示橋梁，將該問(wèn)題抽象成點(diǎn)與線連接圖的數(shù)學(xué)問(wèn)題。把一個(gè)實(shí)際問(wèn)題抽象成合適的“數(shù)學(xué)模型”，這就是計(jì)算思維中的抽象。計(jì)算思維品質(zhì)對(duì)人的能力影響作用計(jì)算思維品質(zhì)對(duì)人的能力影響作用問(wèn)題抽象層次的能力是衡量人的思維品質(zhì)的重要方面。問(wèn)題抽象層次的能力是衡量人的思維品質(zhì)的重要方面。 根據(jù)求解問(wèn)題的

5、需要，在分析問(wèn)題的過(guò)程中，人們可以對(duì)問(wèn)題進(jìn)行多層次的抽象，將注意力集中在感興趣的抽象層次或關(guān)系相對(duì)密切的上下層，拋棄那些不感興趣的(不重要的)層次或細(xì)節(jié)，使問(wèn)題分析相對(duì)簡(jiǎn)單，以控制問(wèn)題解決的復(fù)雜性。抽象的概念是由具體概念依其“共性”而產(chǎn)生的，把具體概念的諸多個(gè)性排出，集中描述其共性，就會(huì)產(chǎn)生一個(gè)抽象性的概念。 人的大腦思維方法和思維品質(zhì)的差異決定著： 同一問(wèn)題解決辦法和處理方式各不相同。其付出的代價(jià)與取得效果甚至可能天壤之別。 計(jì)算思維的應(yīng)用領(lǐng)域計(jì)算思維的應(yīng)用領(lǐng)域 計(jì)算思維是每個(gè)人應(yīng)當(dāng)具備的基本技能，也是創(chuàng)新人才的基本要求和專業(yè)素質(zhì)，每個(gè)人都應(yīng)當(dāng)學(xué)習(xí)和應(yīng)用計(jì)算思維。正如印刷出版促進(jìn)了閱讀、寫作

6、和算術(shù)的傳播一樣，計(jì)算和計(jì)算機(jī)也促進(jìn)著計(jì)算思維的傳播。迄今為止，計(jì)算思維不僅滲透到每個(gè)人的生活，而且對(duì)生物信息學(xué)、生物計(jì)算、專家系統(tǒng)、經(jīng)濟(jì)學(xué)等學(xué)科領(lǐng)域產(chǎn)生了重大影響，在科技創(chuàng)新與教育教學(xué)中起著非常重要的作用。 計(jì)算思維領(lǐng)域提出的新思想、新方法不斷地促進(jìn)自然科學(xué)、工程技術(shù)和社會(huì)經(jīng)濟(jì)等領(lǐng)域產(chǎn)生革命性的發(fā)展。1.2 101.2.1數(shù)制概念及數(shù)制間的轉(zhuǎn)化1.2.2計(jì)算機(jī)中數(shù)據(jù)的表示方法1.2.3 常用信息編碼1.2.4 計(jì)算機(jī)中信息單位1.數(shù)制 即計(jì)數(shù)制，用一組固定的符號(hào)和統(tǒng)一的規(guī)則來(lái)表示 數(shù)值的方法 。計(jì)算機(jī)領(lǐng)域中涉及的數(shù)制有4種：十進(jìn)制、二進(jìn)制二進(jìn)制、八進(jìn)制、十六進(jìn)制。例如：36D、1010lB、

7、76O、5AH分別標(biāo)識(shí)十進(jìn)制數(shù)36、二進(jìn)制數(shù)1010、八進(jìn)制數(shù)76、十六進(jìn)制數(shù)5A。 1.2.11.2.1數(shù)制概念及數(shù)制間的轉(zhuǎn)化數(shù)制概念及數(shù)制間的轉(zhuǎn)化進(jìn)制表示符號(hào)B 二進(jìn)制O八進(jìn)制D十進(jìn)制H十六進(jìn)制 在計(jì)算機(jī)內(nèi)部，數(shù)據(jù)的存儲(chǔ)和處理都是采用二進(jìn)制數(shù)，主要原因是：（1）二進(jìn)制數(shù)在物理上最容易實(shí)現(xiàn)。（2）二進(jìn)制數(shù)的運(yùn)算規(guī)則簡(jiǎn)單，這將使計(jì)算機(jī)的硬件結(jié)構(gòu)大大簡(jiǎn)化。（3）二進(jìn)制數(shù)的兩個(gè)數(shù)字符號(hào)“1”和“0”正好與邏輯命題的兩個(gè)值“真”和“假”相對(duì)應(yīng)，為計(jì)算機(jī)實(shí)現(xiàn)邏輯運(yùn)算提供了便利的條件。 但二進(jìn)制數(shù)書寫冗長(zhǎng)，所以為書寫方便，一般用十六進(jìn)制數(shù)或八進(jìn)制數(shù)作為二進(jìn)制數(shù)的簡(jiǎn)化表示。 位權(quán)例如14十六進(jìn)制數(shù)1十進(jìn)制

8、數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)整數(shù)：除以基值取余法，直到商為零時(shí)為止 ，逆讀 小數(shù)：乘以基值取整法，直到積中的小數(shù)部分為零，或者達(dá)到所要求的精度為止，順讀2二進(jìn)制、八進(jìn)制、十六進(jìn)制轉(zhuǎn)化為十進(jìn)制-按權(quán)展開，相加求和按權(quán)展開，相加求和(110101)2=125+124+023+122+021+120 = 32+ 16+ 0+ 4+ 0+1 =(53)103.二進(jìn)制轉(zhuǎn)化成八進(jìn)制和十六進(jìn)制轉(zhuǎn)化成八進(jìn)制： 以小數(shù)點(diǎn)為中心向兩邊分組,每三位一組.整數(shù)部分不足位數(shù)左補(bǔ)0，小數(shù)部分不足位數(shù)右補(bǔ)轉(zhuǎn)化成十六進(jìn)制：以小數(shù)點(diǎn)為中心向兩邊分組,每四位一組.整數(shù)部分不足位數(shù)左補(bǔ)0，小數(shù)部分不足位數(shù)右補(bǔ)0 4.八進(jìn)

9、制和十六進(jìn)制轉(zhuǎn)化成二進(jìn)制八進(jìn)制轉(zhuǎn)化成二進(jìn)制： 一位八進(jìn)制數(shù)對(duì)應(yīng)三位二進(jìn)制數(shù)十六進(jìn)制轉(zhuǎn)化成二進(jìn)制：一位十六進(jìn)制數(shù)對(duì)應(yīng)四位二進(jìn)制數(shù)144(O)=001 100 100(B)64(H)=0110 0100(B) 6 4 二進(jìn)制、八進(jìn)制、十六進(jìn)制數(shù)間的關(guān)系 八進(jìn)制 對(duì)應(yīng)二進(jìn)制 十六進(jìn)制對(duì)應(yīng)二進(jìn)制十六進(jìn)制 對(duì)應(yīng)二進(jìn)制0000000008100010011000191001201020010A1010301130011B1011410040100C1100510150101D1101611060110E1110711170111F11113位對(duì)應(yīng)位對(duì)應(yīng)1位位4位對(duì)應(yīng)位對(duì)應(yīng)1位位八進(jìn)制八進(jìn)制二進(jìn)制二進(jìn)制十六

10、進(jìn)制十六進(jìn)制1位對(duì)應(yīng)位對(duì)應(yīng)3位位1位對(duì)應(yīng)位對(duì)應(yīng)4位位二進(jìn)制二進(jìn)制十進(jìn)制十進(jìn)制八進(jìn)制八進(jìn)制十六進(jìn)制十六進(jìn)制基數(shù)乘除法按權(quán)展開求和1.2.21.2.2計(jì)算機(jī)中數(shù)據(jù)的表示方法計(jì)算機(jī)中數(shù)據(jù)的表示方法 例如，在機(jī)器中用8位二進(jìn)制表示一個(gè)數(shù)90，其格式為：01011010符號(hào)位符號(hào)位 0表示正表示正在計(jì)算機(jī)中數(shù)據(jù)都是采用二進(jìn)制表示，對(duì)于數(shù)的符號(hào)，也用“0”或“1”表示，“0”表示正，“1”表示負(fù)；數(shù)的最高位為符號(hào)位。 在機(jī)器內(nèi)存放的正負(fù)號(hào)符號(hào)化的數(shù)稱為機(jī)器數(shù)機(jī)器數(shù)，把機(jī)器外存放的由正負(fù)號(hào)表示的數(shù)稱作真值真值。例：-0101100 真值 -76 機(jī)器數(shù)10101100 機(jī)器數(shù)在運(yùn)算時(shí)必須考慮符號(hào)位的處理。為

11、了便于運(yùn)算，在機(jī)器中有三種表示數(shù)的方法： 1、原碼原碼的最高位為符號(hào)位，數(shù)值部分為原數(shù)的絕對(duì)值。 +105原=01101001 -105原=11101001 2、反碼正數(shù)的反碼與其原碼相同。而負(fù)數(shù)的反碼等于其絕對(duì)值各位求反。+105反=01101001 -105反=10010110 3、補(bǔ)碼正數(shù)的補(bǔ)碼與其原碼相同。負(fù)數(shù)的補(bǔ)碼是把其原碼除符號(hào)位外的各位先求其反碼，然后在最低位加1。+105補(bǔ)=01101001 -105補(bǔ)=10010111 0100000010000011定點(diǎn)小數(shù)：定點(diǎn)小數(shù)：小數(shù)點(diǎn)固定在數(shù)值部分最高位的左邊小數(shù)點(diǎn)固定在數(shù)值部分最高位的左邊定點(diǎn)整數(shù)：定點(diǎn)整數(shù)：小數(shù)點(diǎn)固定在數(shù)值部分最

12、低位的左邊小數(shù)點(diǎn)固定在數(shù)值部分最低位的左邊定定點(diǎn)點(diǎn)數(shù)數(shù)符號(hào)位符號(hào)位隱含小數(shù)位（隱含小數(shù)位（+0.5)符號(hào)位符號(hào)位隱含小數(shù)位（隱含小數(shù)位（-3)31 30 24 23 22 31 30 24 23 22 0 0浮浮點(diǎn)點(diǎn)數(shù)數(shù)階符階符 階碼階碼 數(shù)符數(shù)符 尾數(shù)尾數(shù) 階碼部分階碼部分 尾數(shù)部分尾數(shù)部分 小數(shù)點(diǎn)浮動(dòng)-科學(xué)計(jì)數(shù)法 123.456=0.123456103浮點(diǎn)數(shù)分為階碼階碼( (指數(shù)指數(shù)) )和尾數(shù)尾數(shù)兩部分例：二進(jìn)制數(shù)0.110111*26 在計(jì)算機(jī)中以浮點(diǎn)格式存放1.2.3 1.2.3 常用信息編碼常用信息編碼 ACSII碼碼(American Standard Code for Info

13、rmation Interchange) 128個(gè)常用字符，個(gè)常用字符，用用7位二進(jìn)制編碼位二進(jìn)制編碼，從，從0到到127 控制字符：控制字符：032，127；普通字符：；普通字符：94個(gè)。個(gè)。 例如：例如：“a”字符的編碼為字符的編碼為1100001，對(duì)應(yīng)的十進(jìn)制數(shù)是，對(duì)應(yīng)的十進(jìn)制數(shù)是97； 換行換行 0AH 10 回車回車 0DH 13 空格空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122漢字編碼漢字編碼 輸入碼 國(guó)標(biāo)碼 字形碼 機(jī)內(nèi)碼 地址碼 漢字輸出 漢字輸入 (1) 漢字輸入碼 音碼類 全拼、雙拼、微軟拼音、智能ABC等

14、形碼類 五筆字型法、鄭碼輸入法等 。(2) 漢字國(guó)標(biāo)碼(GB231280)：每個(gè)漢字占兩個(gè)字節(jié)。 一級(jí)漢字：3755個(gè)；二級(jí)漢字：3008個(gè)。 漢字分區(qū)，每個(gè)區(qū)94個(gè)漢字。(3)機(jī)內(nèi)碼漢字在設(shè)備或信息處理系統(tǒng)內(nèi)部最基本的表達(dá)形式。漢字 國(guó)標(biāo)碼 漢字內(nèi)碼中 8680(01010110 01010000)B (11010110 11010000)B 華 5942(00111011 00101010)B (10111011 10101010)B 漢字漢字（4）字形碼點(diǎn)陣：漢字字形點(diǎn)陣的代碼 矢量：存儲(chǔ)的是描述漢字字形的輪廓特征 1.1.2 2.4 .4 計(jì)算機(jī)中信息單位計(jì)算機(jī)中信息單位位（Bit）：

15、二進(jìn)制數(shù)的最小單位，通常用“b”表示。字節(jié)（Byte）：以8位二進(jìn)制數(shù)組成1個(gè)字節(jié)，通常用“B”表示。最常用的基本單位K 字節(jié)1K = 1024 byteM（兆）字節(jié) 1M = 1024 KG（吉） 字節(jié) 1G = 1024 M T（太）字節(jié)1T = 1024 G字（ word ）：由若干個(gè)字節(jié)組成，通常我們把計(jì)算機(jī)一次所能處理的數(shù)據(jù)的最大位數(shù)稱為該機(jī)器的字長(zhǎng)。 著名計(jì)算機(jī)科學(xué)家沃思(Nikiklaus Wirth)提出一個(gè)公式： 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序數(shù)據(jù)結(jié)構(gòu):對(duì)數(shù)據(jù)的描述。在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式算法:對(duì)操作的描述。即要求計(jì)算機(jī)進(jìn)行操作的步驟1.3

16、 一個(gè)程序除了算法和數(shù)據(jù)結(jié)構(gòu)這主要要素外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語(yǔ)言表示 算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語(yǔ)言工具是一個(gè)程序設(shè)計(jì)人員應(yīng)具備的知識(shí) 廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為“算法” 計(jì)算機(jī)算法可分為兩大類別：數(shù)值運(yùn)算算法：求數(shù)值解非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域例：圖書檢索，人事管理等例： 求12345 可以用最原始的方法進(jìn)行：步驟1：先求1*2，得到結(jié)果2。步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這就是最后的結(jié)果。例：例： 求求12345 1000太繁瑣太繁瑣 改

17、進(jìn)的算法：設(shè)變量t為被乘數(shù)變量i為乘數(shù)用循環(huán)算法求結(jié)果 S1：使t=1，或?qū)懗?=t S2：使i=2，或?qū)懗? = i S3：使t與i相乘，乘積仍放在變量t中，可表示為：t*i =t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結(jié)束 最后得到t的值就是 5!的值若是若是1000？ S1：使t=1，或?qū)懗?=t S2：使i=2，或?qū)懗? = i S3：使t與i相乘，乘積仍放在變量t中，可表示為：t*i = t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結(jié)束 最后得到t的值就是 5!的值若求若求1357911

18、33221111相當(dāng)于相當(dāng)于i 11 一個(gè)有效算法應(yīng)該具有以下特點(diǎn)：(1) 有窮性。一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。(2) 確定性。算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。 一個(gè)有效算法應(yīng)該具有以下特點(diǎn)：(3) 有零個(gè)或多個(gè)輸入。所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。(4) 有一個(gè)或多個(gè)輸出。算法的目的是為了求解，“解” 就是輸出。沒(méi)有輸出的算法是沒(méi)有意義的。(5) 有效性。算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。 常用的方法有：自然語(yǔ)言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖偽代碼 用自然語(yǔ)言表示通俗易懂，但文字冗長(zhǎng)，容易出現(xiàn)歧義性 用自然語(yǔ)言

19、描述包含分支和循環(huán)的算法，不很方便 除了很簡(jiǎn)單的問(wèn)題外，一般不用自然語(yǔ)言 流程圖是用一些圖框來(lái)表示各種操作 用圖形表示算法，直觀形象，易于理解起止框起止框輸入輸出框輸入輸出框處理框處理框判斷框判斷框流程線流程線連接點(diǎn)連接點(diǎn)x0YN一個(gè)入口一個(gè)入口兩個(gè)出口兩個(gè)出口 流程圖是用一些圖框來(lái)表示各種操作 用圖形表示算法，直觀形象，易于理解起止框起止框輸入輸出框輸入輸出框判斷框判斷框流程線流程線連接點(diǎn)連接點(diǎn)位置不夠位置不夠 例：求5！的算法用流程圖表示。 求123451 = t輸出輸出ti5開始開始2 = it*i = ti+1 = i結(jié)束結(jié)束NY1.傳統(tǒng)流程圖的弊端 傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制 使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去，使人難以理解算法的邏輯2.三種基本結(jié)構(gòu)(1) 順序結(jié)構(gòu)AB2.三種基本結(jié)構(gòu)(2) 選擇結(jié)構(gòu)ABYpNAYpN2.三種基本結(jié)構(gòu)(3)