計算機思維與程序設計（c）趙治國南華大學計算機學院導論說明教材

大學計算機基礎自學為主

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

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

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

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

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

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

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

電子計算機時代第一臺電子數字計算機ENIAC

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

→（1+2）+3 ：結合律

→

3+3 ：加法口訣，替換規則

→

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

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

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

算法

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

計算思維，籠統地講，是像計算機科學家一樣思維，即像計算機科學家一樣發現問題、分析問題并最終解決問題。其核心是算法思維，算法思維的最后一個步驟是實現算法。

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

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

例如，頒獎大會的程序；做菜的程序等等。把做菜的步驟用大家看得懂的方式記錄下來，其他人可以按這些步驟順序實施就完成了該事情。程序（Program）程序是為實現特定目標或解決特定問題而用計算機語言編寫的指令序列。平常所說的各種軟件就是由程序和數據構成的。程序設計程序設計(Programming)是給出解決特定問題程序的過程，是軟件構造活動中的重要組成部分。程序設計往往以某種程序設計語言為工具，給出這種語言下的程序。程序設計語言第一代機器語言；第二代匯編語言；第三代高級語言：VB，C，C++，Java；第四代應用語言：PowerBuilder、Delphi，INFORMOX-4GL；第五代自然語言。

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

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

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

Load1,8將單元8的數據裝入寄存器1Add0,1寄存器0與1的數據加

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

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

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

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

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

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

進制是一種“量”的表示方式十進制0~9“逢十進位”的規則和一個小數點構成了一套完整的進制體系二進制“逢二進位”的進制0、1表示數據

數制表示

一個完整的數制是由基數、數位和權三要素構成的。

基數指數制中用到的基本數字符號；

數位指數字符號在一個數中所處的位置；而權指的是對應數位的基值。一個數據對應的量是該數的每一數位按進制權展開的數量的和?；鶖?/p>

基數個數進位值十進制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基數權(101.11)2=1×22+0×21+1×20+1×2-1+1×2-2權

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

812

402

202

1012

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

148

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

r進制轉化成十進制r進制轉化成十進制：數碼乘以各自的權的累加

例：

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進制轉化成十進制練習：(365.2)8=(？)10

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

＋2×8－1

=(245.25)10

十

0123456789二0000000100100011010001010110011110001001八

00000001001000110100010101100111十

0000000100100011010001010110011110001001六

101010111100110111101111

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

0100(B)

64144(O)=001

100

100(B)

144舉例說明：八進制和十六進制轉化成二進制

練習：

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

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

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

二進制轉化成八進制和十六進制后邊補兩個零，變成0100前邊補兩個零，變成001轉換表八進制數二進制數八進制數二進制數

00004100100151012010611030117111二進制數轉換為八進制數舉例：

（001101001110.110100）B→（1516.64）O八進制數轉換為二進制數舉例：

(2467.32)O

→(010100110111.011010)B

八進制數與二進制數的轉換十六進制數與二進制數的轉換轉換表十六進制數二進制數十六進制數二進制數

0000081000

1000191001

20010A1010

30011B1011

40100C1100 50101D1101 60110E1110 70111F1111二進制數轉換為十六進制數舉例：

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

(35A2.CF)H

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

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

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

0D70011100D0+28=10011100-28=0表示正數1表示負數D7=

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

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

[X]反=10100100

負數的補碼規定為：先求負數的反碼，再把反碼的最低位加1。

[X]原=11011011

[X]反=10100100

[X]補=10100101

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

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

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

減法運算與加法類似，可以看成負數的加；

算術運算（加、減、乘、除）內在聯系：

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

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

65=[01000001]原=[01000001]補

54=[00110110]原=[00110110]補

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

ASCII碼即美國標準信息交換碼，我國根據它制定了國家標準，即GB1988。其中除了將貨幣符號轉換為人民幣符號外，其他相同