第1章 計算思維-導(dǎo)論

計算機思維與程序設(shè)計（c）趙治國南華大學(xué)計算機學(xué)院導(dǎo)論說明教材

大學(xué)計算機基礎(chǔ)自學(xué)為主

大學(xué)C/C++語言程序設(shè)計基礎(chǔ)課時第1學(xué)期：2(導(dǎo)論)+26(C、理論)+20(上機)考試第1、2學(xué)期末分別考試，筆試成績筆試×70%+平時成績×30%

具體要求了解計算機的組成、工作原理了解計算機的軟、硬件系統(tǒng)掌握OS和Office辦公軟件的使用掌握一種程序設(shè)計語言的語法和基本的編程方法掌握一種程序設(shè)計工具的應(yīng)用了解常用的算法和數(shù)據(jù)結(jié)構(gòu)了解軟件的基本開發(fā)過程和方法第一章計算思維與程序設(shè)計1.1計算思維1.2算法1.3程序設(shè)計1.4數(shù)制轉(zhuǎn)換計算某海軍陸戰(zhàn)隊在原始森林進行為時一個月左右的生存實驗，要求：一，每個隊員除了身上穿的衣服外，隨身只能帶三件物品，每件物品不能超過二公斤；二，隊員都是由飛機空降到半徑為1000公里原始森林的中心地帶，要求在一個月時間內(nèi)從森林里走出來。問題：隊員帶哪三件物品合適？想一想：理想的答案：鋼刀、火石、指南針人類要在世界上生存與發(fā)展要獲取物質(zhì)、能量、信息三大要素。在農(nóng)業(yè)社會和工業(yè)社會中，物質(zhì)和能源是主要資源，所從事的是大規(guī)模的物質(zhì)生產(chǎn)。

20世紀(jì)50年代，信息趕超上材料、能源成為影響人類社會發(fā)展的決定性力量。在信息社會中，信息成為比物質(zhì)和能源更為重要的資源，生成、發(fā)布和使用信息成為重要的經(jīng)濟和文化行為。數(shù)字化生存尼葛洛龐帝（Negroponte）：美國麻省理工學(xué)院教授及媒體實驗室的創(chuàng)辦人。1996年7月被《時代》周刊列為當(dāng)代最主要的未來學(xué)家之一。計算不再只和計算機有關(guān)，它決定我們的生存數(shù)字化生存的智慧：計算思維一、計算改變了什么？二、什么是計算？三、什么是計算思維？1.計算改變科學(xué)家的思考方式計算生物學(xué)改變著生物學(xué)家的思考方式計算博弈理論改變著經(jīng)濟學(xué)家的思考方式納米計算改變著化學(xué)家的思考方式計算物理學(xué)改變著物理學(xué)家的思考方式數(shù)學(xué)機械化改變數(shù)學(xué)家的思考方式社會計算改變社會學(xué)家的思考方式……計算生物學(xué)應(yīng)用數(shù)據(jù)分析及理論的方法、數(shù)學(xué)建模和計算機仿真技術(shù)，來研究生物學(xué)、行為學(xué)和社會群體系統(tǒng)。計算經(jīng)濟學(xué)運用計算思想分析和綜合經(jīng)濟問題分析、模型、決策計算思想在諾貝爾獎獲獎理論中占到70%以上的比例計算考古學(xué)--人臉復(fù)原2000年前的馬王堆辛追夫人與3500年前的古埃及最美麗的王妃：妮菲蒂蒂2.計算改變工作方式：數(shù)字化會議數(shù)字化醫(yī)療數(shù)字化教學(xué)數(shù)字化制造管路設(shè)計強度分析結(jié)構(gòu)分析數(shù)字預(yù)裝配CAM裝配過程仿真裝配過程仿真富士康的轉(zhuǎn)型之路--機器人來了富士康“百萬機器人”計劃

3.計算改變生活方式:智能家居

網(wǎng)絡(luò)冰箱監(jiān)測食物收集菜譜知道你喜歡吃什么20從家信到視頻聊天的變遷烽火連三月，家書抵萬金。海內(nèi)存知己，天涯若比鄰。拜年方式悄然演變?nèi)祟惖闹橇γ媾R挑戰(zhàn)15年前IBM的超級電腦“深藍”擊敗世界國際象棋冠軍加里·卡斯帕羅夫，這次IBM向人類的冠軍發(fā)出挑戰(zhàn)的超級電腦名叫“沃森”。這部以IBM公司創(chuàng)始人名字命名的計算機，具備非常強大的計算功能，它登上了美國著名老牌智力游戲節(jié)目《危險邊緣》挑戰(zhàn)人類智力。挑戰(zhàn)該節(jié)目的兩名總冠軍肯-詹寧斯和布拉德-魯特爾，實現(xiàn)有史以來首次人機智力問答對決?！吧钏{”與“沃森”二、什么是計算計算是人類文明最古老而又最時新的成就之一計算方法及計算工具不斷地發(fā)展，對推動社會進步發(fā)揮了巨大作用計算的本質(zhì)就是基于規(guī)則的符號串變換手動計算工具時代手動式計算工具——算籌圖

1.3手動式計算工具——算盤

機械式計算工具時代法國著名數(shù)學(xué)家、物理學(xué)家、近代概率論的奠基者和他的計算工具——帕斯卡加法器1642年機電計算工具時代美國哈佛大學(xué)應(yīng)用數(shù)學(xué)教授霍華德·艾肯和他的機電式計算機——MARKI

電子計算機時代第一臺電子數(shù)字計算機ENIAC

阿塔納索夫莫齊利?？颂谽NIAC的發(fā)明人與制作人阿塔納索夫、莫齊利、?？颂亍疤旌右惶枴笔俏覈着_千萬億次超級計算機計算是基于規(guī)則的符號串變換1+2+3

→（1+2）+3 ：結(jié)合律

→

3+3 ：加法口訣，替換規(guī)則

→

6 ：加法口訣從一個已知的符號串開始，按照一定的規(guī)則，一步一步地改變符號串，經(jīng)過有限步驟，最后得到一個滿足預(yù)先規(guī)定的符號串，這種變換過程就是計算。三、什么是計算思維笛卡爾（ReneDescartes）：解析幾何之父

我思故我在思維是對某個問題或事物的思考過程以及產(chǎn)生的想法或見解思維是人腦對客觀現(xiàn)實概括的和間接的反映，它反映的是事物的本質(zhì)和事物間規(guī)律性的聯(lián)系思維是與時俱進的人類的思維水平也必然隨著認(rèn)識工具的進步而逐步地由淺入深、由單純到復(fù)雜、由片面至全面發(fā)展我們所使用的工具影響著我們的思維方式和思維習(xí)慣，從而也將深刻地影響著我們的思維能力計算無處不在的時代思維：計算思維艾茲格·W·迪科斯徹（1930~2002）（EdsgerWybeDijkstra，）荷蘭計算機科學(xué)家，荷蘭Leiden大學(xué)1972年獲得圖靈獎【例】在中央電視臺的《幸運52》節(jié)目中，要求參與者快速猜出物品的價格。主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答高了、低了或者正確。在某次節(jié)目中，主持人出示了一臺價值在1000元以內(nèi)的隨身聽，并開始了競猜。下面是主持人和參與者的一段對話：….如果你是參與者，你接下來會怎么猜？800元！高了400元！600元！低了高了參與者主持人：李詠計算思維—猜猜猜計算思維的定義運用計算機科學(xué)的思想、方法和技術(shù)進行問題求解、系統(tǒng)設(shè)計、以及人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動周以真（JeannetteM.Wing）美國計算機科學(xué)家卡內(nèi)基-梅隆大學(xué)教授ACM與IEEE會士計算思維的核心是算法思維

為解決一個問題而采取的方法和步驟，就稱為算法。

算法

一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河南岸，要把東西全部運到北岸。約束條件是只有一條能容下他和一件物品的小船，只有農(nóng)夫能撐船。不能單獨留下羊和白菜，也不能單獨留下羊和狼。例如：農(nóng)夫過河算法帶羊到對岸空手回本岸帶菜到對岸帶羊回本岸帶狼到對岸空手回本岸帶羊到對岸帶羊到對岸空手回本岸帶狼到對岸帶羊回本岸帶菜到對岸空手回本岸帶羊到對岸或計算機算法的特性（1）有窮性：一個算法在執(zhí)行有窮步之后必須結(jié)束。也就是說，一個算法，它所包含的計算步驟是有限的。（2）確定性：算法的每一個步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴(yán)格而不含混地進行規(guī)定，不能有歧義性。（3）輸入：算法有零個或多個的輸入，即在算法開始之前，對算法最初給出的量。（4）輸出：算法有一個或多個的輸出，即與輸入有某個特定關(guān)系的量，簡單地說就是算法的最終結(jié)果。（5）可操作性：算法上描述的操作在計算機上都是可以實現(xiàn)的。算法效率算法的效率可以通過復(fù)雜度來說明，分為時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度：執(zhí)行該算法所需要的計算工作量，一般用所需基本運算的執(zhí)行次數(shù)來度量?？臻g復(fù)雜度：執(zhí)行該算法所需的內(nèi)存空間，問題：在242356768794129140有序數(shù)列中插入數(shù)據(jù)90使之依然保持有序需要多少次？采用算法思維求解問題分為以下幾個基本步驟：①問題的抽象。②問題的符號化表示。③問題求解的算法。④算法的實現(xiàn)。

計算思維，籠統(tǒng)地講，是像計算機科學(xué)家一樣思維，即像計算機科學(xué)家一樣發(fā)現(xiàn)問題、分析問題并最終解決問題。其核心是算法思維，算法思維的最后一個步驟是實現(xiàn)算法。

算法的實現(xiàn)是需要一定的步驟，程序就是算法步驟的一種體現(xiàn)。什么是程序？

程序一詞源于生活。做任何一件事情，都是有程序的。

例如，頒獎大會的程序；做菜的程序等等。把做菜的步驟用大家看得懂的方式記錄下來，其他人可以按這些步驟順序?qū)嵤┚屯瓿闪嗽撌虑?。程序（Program）程序是為實現(xiàn)特定目標(biāo)或解決特定問題而用計算機語言編寫的指令序列。平常所說的各種軟件就是由程序和數(shù)據(jù)構(gòu)成的。程序設(shè)計程序設(shè)計(Programming)是給出解決特定問題程序的過程，是軟件構(gòu)造活動中的重要組成部分。程序設(shè)計往往以某種程序設(shè)計語言為工具，給出這種語言下的程序。程序設(shè)計語言第一代機器語言；第二代匯編語言；第三代高級語言：VB，C，C++，Java；第四代應(yīng)用語言：PowerBuilder、Delphi，INFORMOX-4GL；第五代自然語言。

計算5*6+8？00000001000000001000數(shù)據(jù)5裝入寄存器000000001000100001010數(shù)據(jù)6裝入寄存器100000101000000000001寄存器0與1的數(shù)據(jù)乘00000001000100001001數(shù)據(jù)8裝入寄存器100000100000000000001寄存器0與1的數(shù)據(jù)加00000010000000001110保存寄存器0里的數(shù)38難寫難讀，使用不便，程序開發(fā)效率極低。最初的語言是機器語言，是二進制編碼，機器可直接執(zhí)行。匯編語言

用簡潔的英文字母、符號串替代一個特定的指令的二進制串，比如，用“ADD”代表加法，“MOV”代表數(shù)據(jù)傳遞等等。

例：Load0,5將單元5的數(shù)據(jù)裝入寄存器0Load1,6將單元6的數(shù)據(jù)裝入寄存器1Mult0,1寄存器0與1的數(shù)據(jù)乘

Load1,8將單元8的數(shù)據(jù)裝入寄存器1Add0,1寄存器0與1的數(shù)據(jù)加

Save0,d將寄存器0里的數(shù)存入單元d=38高級語言實現(xiàn)一條語句：例：d=5*6+8

高級語言程序必須經(jīng)過翻譯變成機器語言程序。翻譯有兩種做法：編譯和解釋，相應(yīng)的翻譯工具分別叫做編譯器和解釋器。四數(shù)制轉(zhuǎn)換計算位（bit）字節(jié)(byte)：計算機存儲容量的基本單位。計算機內(nèi)部,一個字節(jié)可以表示一個數(shù)據(jù)、一個英文字母，兩個字節(jié)可以表示一個漢字。

8(Bit)=1(Byte)Byte--字節(jié)

1024(Byte)=1(Kb)Kb---千字節(jié)

1024(Kb)=1(Mb)Mb---兆字節(jié)

1024(Mb)=1(Gb)Gb---千兆字節(jié)二進制數(shù)的基本單位字（word）：計算機一次存取、加工、運算和傳送的數(shù)據(jù)長度，一個字的二進制位數(shù)稱為字長。字長一般為8的倍數(shù)。1、為什么字長一般為8的整數(shù)倍？

進制是一種“量”的表示方式十進制0~9“逢十進位”的規(guī)則和一個小數(shù)點構(gòu)成了一套完整的進制體系二進制“逢二進位”的進制0、1表示數(shù)據(jù)

數(shù)制表示

一個完整的數(shù)制是由基數(shù)、數(shù)位和權(quán)三要素構(gòu)成的。

基數(shù)指數(shù)制中用到的基本數(shù)字符號；

數(shù)位指數(shù)字符號在一個數(shù)中所處的位置；而權(quán)指的是對應(yīng)數(shù)位的基值。一個數(shù)據(jù)對應(yīng)的量是該數(shù)的每一數(shù)位按進制權(quán)展開的數(shù)量的和?；鶖?shù)

基數(shù)個數(shù)進位值十進制0～9,

10個10

二進制0和1,2個2

八進制0～7,8個8十六進制0～9及A～B,16個16R進制R個R(1999)10=1×103+9×102+9×101+9×100基數(shù)權(quán)(101.11)2=1×22+0×21+1×20+1×2-1+1×2-2權(quán)

十進制數(shù)轉(zhuǎn)換為Ｒ進制數(shù)整數(shù)：除Ｒ取余法(先得最低位，后得最高位）小數(shù)：乘Ｒ取整法(先得最高位，后得最低位）3521712

812

402

202

1012

0最高位最低位轉(zhuǎn)換整數(shù)部分例：將十進制數(shù)35.625轉(zhuǎn)換為二進制數(shù)十進制轉(zhuǎn)換為二進制(35)10=(100011)2(.625)10=(.101)20.625×21.250×20.500×21.000最高位最低位轉(zhuǎn)換小數(shù)部分(35.625)10=(100011.101)2101十進制轉(zhuǎn)換為八進制10081248

148

01最高位最低位例：將十進制數(shù)100轉(zhuǎn)換為八進制數(shù)(100)10=(144)8練習(xí)：(19)10=()2(207)10=()810011317

r進制轉(zhuǎn)化成十進制r進制轉(zhuǎn)化成十進制：數(shù)碼乘以各自的權(quán)的累加

例：

10101(B)=24+22+1=21101.11(B)=22+1+2-1+2-2=5.75101(O)=82+1=65101A(H)=163+16+10＝4106進制表示符號B二進制O八進制D十進制H十六進制

r進制轉(zhuǎn)化成十進制練習(xí)：(365.2)8=(？)10

=3×82＋6×81＋5×80

＋2×8－1

=(245.25)10

十

0123456789二0000000100100011010001010110011110001001八

00000001001000110100010101100111十

0000000100100011010001010110011110001001六

101010111100110111101111

ABCDEF二、八、十、十六進制數(shù)的對照表轉(zhuǎn)換原則：一位八進制數(shù)對應(yīng)三位二進制數(shù)一位十六進制數(shù)對應(yīng)四位二進制數(shù)八進制和十六進制轉(zhuǎn)化成二進制64(H)=0110

0100(B)

64144(O)=001

100

100(B)

144舉例說明：八進制和十六進制轉(zhuǎn)化成二進制

練習(xí)：

(2C1D)H=()B2C1D(7123)O=()B71231110010100110010110000011101轉(zhuǎn)換方法：

整數(shù)部分：從右向左進行分組。小數(shù)部分：從左向右進行分組。轉(zhuǎn)化成八進制時三位一組。轉(zhuǎn)化成十六進制時四位一組，不足補零，然后將對應(yīng)的每一組轉(zhuǎn)換為一位八進制或十六進制數(shù)。

(1101101110.110101)B=(36F.D4)H36FD4(1101101110.110101)B=(1556.65)O155665

二進制轉(zhuǎn)化成八進制和十六進制后邊補兩個零，變成0100前邊補兩個零，變成001轉(zhuǎn)換表八進制數(shù)二進制數(shù)八進制數(shù)二進制數(shù)

00004100100151012010611030117111二進制數(shù)轉(zhuǎn)換為八進制數(shù)舉例：

（001101001110.110100）B→（1516.64）O八進制數(shù)轉(zhuǎn)換為二進制數(shù)舉例：

(2467.32)O

→(010100110111.011010)B

八進制數(shù)與二進制數(shù)的轉(zhuǎn)換十六進制數(shù)與二進制數(shù)的轉(zhuǎn)換轉(zhuǎn)換表十六進制數(shù)二進制數(shù)十六進制數(shù)二進制數(shù)

0000081000

1000191001

20010A1010

30011B1011

40100C1100 50101D1101 60110E1110 70111F1111二進制數(shù)轉(zhuǎn)換為十六進制數(shù)舉例：

(001101001110.11001100)B→(34E.CC)H十六進制數(shù)轉(zhuǎn)換為二進制數(shù)舉例：

(35A2.CF)H

→(0011010110100010.11001111)B（1100100）2=（）8（1100100）2=（）16144642數(shù)值數(shù)據(jù)的編碼和運算對于真值0，可認(rèn)為它是正零，也可認(rèn)為它是負(fù)零：

[+0]原=00000000[-0]原=100000001）機器數(shù)與真值

將數(shù)的符號也數(shù)值化的數(shù)據(jù)稱為機器數(shù)。而將原來由正負(fù)號表示的數(shù)值，稱為機器數(shù)的真值。

0D70011100D0+28=10011100-28=0表示正數(shù)1表示負(fù)數(shù)D7=

機器數(shù)的位數(shù)與字長有關(guān)：若字長為n位，符號占一位，數(shù)值部分為n-1位。機器數(shù)有原碼、反碼、補碼三種編碼形式。2）原碼、反碼、補碼［正數(shù)］原==［正數(shù)］反==［正數(shù)］補

負(fù)數(shù)的反碼規(guī)定為：把負(fù)數(shù)的原碼除符號位之外的其它各位按位取反。[X]原=11011011

[X]反=10100100

負(fù)數(shù)的補碼規(guī)定為：先求負(fù)數(shù)的反碼，再把反碼的最低位加1。

[X]原=11011011

[X]反=10100100

[X]補=10100101

特殊：[+0]反=00000000[-0]反=11111111

補碼表示的0有唯一的形式：

[+0]補=[-0]補=00000000

減法運算與加法類似，可以看成負(fù)數(shù)的加；

算術(shù)運算（加、減、乘、除）內(nèi)在聯(lián)系：

乘法可以看成是多次加法的運算和；

除法運算可以看成是多次減法運算。結(jié)論：機器運算只需要加法就行了減法運算化為補碼的相加。例：用補碼求：65+54=？，65-54=？

65=[01000001]原=[01000001]補

54=[00110110]原=[00110110]補

-54=[10110110]原=[11001010]補3字符信息的編碼字符的表示：ASCII碼

ASCII碼即美國標(biāo)準(zhǔn)信息交換碼，我國根據(jù)它制定了國家標(biāo)準(zhǔn)，即GB1988。其中除了將貨幣符號轉(zhuǎn)換為人民幣符號外，其他相同