計算思維復習大綱課件

期末復習－及考試相關(guān)關(guān)于考試考試時間：1月4號8:00-9:50考試形式：閉卷筆試考試題型：50個單選題（每個1分） 10個填空題（每空1分）

10個判斷題（每個1分）

6個綜合題（每個5分）考試范圍：第1、2、3、4、5章全部內(nèi)容注意:開考后40分鐘后方可交卷,答題紙上印有"座號"字樣,請按本班學號排序號填寫第一章計算、計算工具的歷史沿革：

在電腦史前史里，帕斯卡被公認為制造出機械計算機的第一人。P7

巴貝奇耗費了整整１０年時間，于１８２２年完成了第一臺差分機。P9

楚澤的繼電器計算機是世界上第一臺二進制電子運算機器。P11

美國賓夕法尼亞大學和有關(guān)單位在１９４６年制成了第一臺電子計算機——電子數(shù)字積分儀與計算機”ＥＮＩＡＣ。P11-12計算與學科滲透：P13

隨著當代科學技術(shù)的發(fā)展，不同學科之間的相互滲透、交叉和綜合已成為當今科技發(fā)展的一個重要趨勢。計算機科學并不是一門獨立的學科，它在學科融合、滲透中獨占鰲頭。當前熱點計算：云計算：云計算是一種按使用量付費的模式，這種模式提供可用的、便捷的、按需的網(wǎng)絡訪問，進入可配置的計算資源共享池(資源包括網(wǎng)絡、服務器、存儲、應用軟件、服務)，這些資源能夠被快速提供，只需投入很少的管理工作或與服務供應商進行很少的交互。

P24

特點：虛擬化技術(shù)、靈活定制、動態(tài)可擴展性、高可靠性和安全性、高性價比。物聯(lián)網(wǎng)：廣義的物聯(lián)網(wǎng)定義認為物聯(lián)網(wǎng)是在互聯(lián)網(wǎng)的基礎上，借助各種信息傳感設備，通過各種接入網(wǎng)絡實現(xiàn)物體與互聯(lián)網(wǎng)連接，形成人與物、物與物互聯(lián)的巨大智能網(wǎng)絡。

廣泛應用于航天、交通、農(nóng)業(yè)、物流等領域。P27

大數(shù)據(jù)：指需要新處理模式才能具有更強的決策力、洞察發(fā)現(xiàn)力和流成優(yōu)化能力的海量、高增長率和多樣化的信息資產(chǎn)。P30

特點：數(shù)據(jù)體量巨大、數(shù)據(jù)種類繁多、流動速度快、價值密度低。P31

可穿戴計算：智慧城市：思維與計算思維：常見的思維模式分為３種：P38①以觀察和歸納自然(包括人類社會活動)規(guī)律為特征的實證思維；②以推理和演繹為特征的邏輯思維；③以抽象化和自動化為特征的計算思維；第二章計算機概述：P45-46

1、世界上第一臺電子計算機，1946年2月在美國賓夕法尼亞大學誕生,取名為ＥＮＩＡＣ。2、電子計算機的發(fā)展按構(gòu)成計算機的電子器件來劃分，至今已經(jīng)歷了４代：第一代電子管計算機，主要用于科學計算；第二代晶體管計算機，提出操作系統(tǒng)概念，出現(xiàn)FORTRAN等高級語言；第三代集成電路計算機；第四代大規(guī)模和超大規(guī)模集成電路計算機時代，微型計算機開始出現(xiàn)。圖靈與圖靈機：P55圖靈機是英國數(shù)學家阿蘭圖靈于１９３６年提出的一種抽象計算模型。計算機的基本組成及工作原理：

馮諾依曼原理：

P57現(xiàn)代計算機是一個自動化的信息處理裝置，而它之所以能實現(xiàn)自動化信息處理，是因為采用了“存儲程序”工作原理。這一原理是１９４６年由馮諾依曼提出并論證的，這一原理確立了現(xiàn)代計算機的基本組成和工作方式：①計算機硬件由５個基本部分組成:運算器、控制器、存儲器、輸入設備和輸出設備；②計算機內(nèi)部采用二進制來表示程序和數(shù)據(jù)；③采用“存儲程序”的方式，將程序和數(shù)據(jù)放入同一個存儲器中，計算機能夠自動高速地從存儲器中取出指令加以執(zhí)行。五大部件在控制器的控制下協(xié)調(diào)統(tǒng)一地工作。首先，把表示計算步驟的程序和計算中需要的原始數(shù)據(jù)在控制器輸入命令的控制下，通過輸入設備送入計算機的存儲器進行存儲；

其次當計算開始時，在取指令作用下把程序指令逐條送入控制器，控制器對指令進行譯碼，并根據(jù)指令的操作要求向存儲器和運算器發(fā)出存儲、取數(shù)命令和運算命令，經(jīng)過運算器計算并把結(jié)果存放在存儲器內(nèi)，

最后在控制器的取數(shù)和輸出命令作用下，通過輸出設備輸出計算結(jié)果。

1、通常將運算器和控制器統(tǒng)稱為中央處理器(ＣＰＵ)，它是整個計算機的核心部件，是計算機的“大腦”，它控制了計算機的運算、處理、輸入和輸出等工作。）2、存儲容量的大小以字節(jié)為單位來度量，經(jīng)常使用ＫＢ(千字節(jié))、ＭＢ(兆字節(jié))、ＧＢ(千兆字節(jié))和ＴＢ(兆兆字節(jié))來表示。它們之間的關(guān)系是:１ＫＢ＝１０２４Ｂ；１ＭＢ＝１０２４ＫＢ；１ＧＢ＝１０２４ＭＢ；１ＴＢ＝１０２４ＧＢ。3、存儲器分為內(nèi)存儲器(主存儲器)和外存儲器(輔助存儲器)兩大類。P59

內(nèi)存在計算機主機內(nèi)，它直接與運算器、控制器交換信息，容量雖小，但存取速度快，一般只存放那些正在運行的程序和待處理的數(shù)據(jù)。

內(nèi)存分為RAM(可隨機讀寫，斷電后數(shù)據(jù)消失)和ROM（它只能讀出信息，不能寫入信息，斷電后仍能保存數(shù)據(jù))

外存儲器是指除計算機內(nèi)存及ＣＰＵ緩存（高速緩存讀取速度相對更快）以外的存儲器，外存中的程序和數(shù)據(jù)必須先送入內(nèi)存才能被計算機執(zhí)行，外存存取速度慢，但容量很大，此類存儲器一般斷電后仍然能保存數(shù)據(jù)。常見的外存儲器有硬盤、軟盤、光盤、Ｕ盤等。

4、常用的輸入設備有鍵盤、鼠標、光筆、掃描儀、數(shù)字化儀、條形碼閱讀器等；常用的輸出設備有顯示器、打印機、繪圖儀等。

5、沒有安裝軟件的計算機稱為“裸機”。

6、計算機軟件可分為系統(tǒng)軟件和應用軟件兩大類。P61

系統(tǒng)軟件包括操作系統(tǒng)、數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)、程序設計語言及其解釋編譯程序、網(wǎng)絡管理軟件等；

應用軟件包括文字處理、圖形圖像處理、音頻視頻處理、殺毒類等。7、操作系統(tǒng)是計算機系統(tǒng)中必不可少的軟件，是用戶和計算機之間的接口，任何一個用戶要使用計算機都必須首先安裝操作系統(tǒng)。操作系統(tǒng)是一個管理電腦硬件與軟件資源的程序，同時也是計算機系統(tǒng)的內(nèi)核與基石。目前常見的操作系統(tǒng)有ＤＯＳ、ＯＳ/２、ＵＮＩＸ、Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ系列、Ｎｅｔｗａｒｅ等8、主板(又稱主機板ＭａｉｎＢｏａｒｄ或系統(tǒng)板ＳｙｓｔｅｍＢｏａｒｄ等)是微機內(nèi)最大的一塊集成電路板。計算機問題求解：P68精確問題也可稱為界定清晰的問題，是指初始狀態(tài)、目標狀態(tài)以及由初始狀態(tài)如何達到目標狀態(tài)的一系列過程都很清楚的問題。例如：已知Ａ>Ｂ，Ｂ<Ｃ，問Ａ與Ｃ哪個大？這是一個目的非常明確的問題。模糊問題也稱界定含糊的問題，是指那些對問題的初始狀態(tài)或目標狀態(tài)沒有清楚的說明，或者對二者都沒有明確說明的問題，這些問題具有很大的不確定性。例如“如何寫一篇論文”這個問題的初始狀態(tài)和目標狀態(tài)都是不清楚的。計算機求解問題過程首先是分析問題并建立數(shù)學模型

二進制：進制之間的轉(zhuǎn)換：

十－二進制轉(zhuǎn)換：整數(shù)部分，除2取余法；小數(shù)部分，乘2取整法。二－八進制轉(zhuǎn)換：整數(shù)部分，三位一組，從右往左；小數(shù)部分，三位一組，從左往右數(shù)值信息的表示與運算：在計算機中數(shù)值型的數(shù)據(jù)有兩種表示方法，一種叫做定點數(shù)，另一種叫做浮點數(shù)。原碼、反碼、補碼

第三章非數(shù)值型數(shù)據(jù)：1、非數(shù)值信息包括文字、圖形、圖像、聲音等，在計算機中采用編碼的方式來表示。2、目前計算機中采用的字符編碼主要是ASCII碼，它是ＡmericanStandardCodeforInformationInterchange（美國標準信息交換代碼)的縮寫，已被國際標準化組織(ISO)采納，作為國際通用的信息交換標準代碼。ASCII碼有７位ASCII碼和８位ASCII碼兩種編碼方式。

７位ASCII

碼稱為標準ASCII碼，用一個字節(jié)(８位)表示一個字符，并規(guī)定其最高位為０，可表示128個不同字符。

８位ASCII

碼稱為擴展ASCII碼，用８位二進制進行編碼，最高位恒為１。擴展部分的范圍為128-255，代表128個擴展字符。８位ASCII

碼總共可以代表256個字符。

會使用標準ASCII碼字符表P98

漢字編碼：P99

漢字處理過程：在計算機中輸入漢字時，操作者在鍵盤上輸入“輸入碼”，通過“輸入碼”找到漢字的國標區(qū)位碼(也稱為交換碼)，再計算出漢字的機內(nèi)碼后存儲，而當顯示或打印漢字時，則首先從指定地址取出漢字內(nèi)碼，根據(jù)內(nèi)碼從字模庫中取出漢字的字形碼，并以漢字字形碼輸出到屏幕或打印機上。

1、輸入碼是用鍵盤上的字母符號編碼組合來表示每一個漢字的編碼，它使人們通過鍵入字母符號代替鍵入漢字，也稱為漢字外部碼(簡稱外碼)。

2、漢字交換碼是指具有漢字處理功能的不同計算機系統(tǒng)之間在交換漢字信息時所使用的代碼標準，也稱國標碼。為了能區(qū)分漢字與ASCII碼，在計算機內(nèi)部表示漢字時把交換碼(國標碼)兩個字節(jié)的最高位改為１，稱為機內(nèi)碼。在漢字信息系統(tǒng)內(nèi)部對漢字信息的采集、傳輸、存儲、加工運算的各個過程都要用到機內(nèi)碼，機內(nèi)碼是計算機內(nèi)部真正用來存儲和處理漢字信息的代碼。

3、字形碼記錄漢字的外形，用來將漢字顯示到屏幕上或打印到紙上，是漢字的輸出形式。記錄漢字字形通常有點陣法和矢量法兩種方法，其中點陣規(guī)模越大，字形越清晰美觀，在字模庫中所占用的空間也越大?！按蟆雹蹤C內(nèi)碼：漢字在計算機內(nèi)部采用漢字內(nèi)碼存儲，每個漢字占兩字節(jié)且最高位均為1的0，1型編碼。計算機內(nèi)部由外到內(nèi)由內(nèi)到外b7

b6b5b4b3b2b1b0

b7

b6b5b4b3b2b1b0

0011010001110011國標碼1011010011110011(機)內(nèi)碼“大”漢字字形碼是一種字模點陣碼。也有不同的處理漢字點陣信息的編碼，如向量編碼等oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11ooooo1oo1111111111111111oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo111oooooooooooo11oo1oooooooooo11oooo1oooooooo11ooooo11ooooooo1ooooooo11ooooo1ooooooooo111o

11ooooooooooo1oo計算機內(nèi)部由外到內(nèi)由內(nèi)到外大④字形碼是用0和1編碼有、無亮點像素，形成一種點陣形式的漢字字形編碼，通過顯示器或打印機輸出漢字。0和1與字母符號---編碼(6)漢字如何進行處理?為什么會有那么多種漢字編碼?簡易１６Ｘ１６，普及２４Ｘ２４，提高３２Ｘ３２，精密４８Ｘ４８，點陣規(guī)模越大，字形越清晰美觀，在字模庫中所戰(zhàn)勝的空間也越大。多媒體信息的表示和處理：1、圖像是由掃描儀、照相機等輸入設備捕捉實際的畫面產(chǎn)生的數(shù)字化文件，由像素點陣構(gòu)成。圖像中的每個像素點用二進制位表示，位數(shù)越高，所表示的圖像越接近自然影像，所以圖像又稱為位圖。

常用的圖像文件格式有:BMP、GIF、JPEG、TIFF、PNG、WMF、PSD、PDF等

2、圖形是由一組存儲在計算機中的指令組成的，這些指令描述點、線、面等大小形狀及其位置、維數(shù)，計算機通過讀取這些指令并將其轉(zhuǎn)換為屏幕上所顯示的形狀和顏色的方式來顯示的圖像，又稱為矢量圖，如office中的剪貼畫。總的來說，由于矢量圖像存儲的是指令，所以要比位圖圖像文件小得多。

3、音頻文件：常用的聲音文件格式有：WAV、MP3、MIDI等。

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。邏輯結(jié)構(gòu)是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系。包括以下四種：集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)物理結(jié)構(gòu)是指數(shù)據(jù)對象在計算機中的存儲形式。

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)、數(shù)據(jù)之間的關(guān)系第四章四種邏輯結(jié)構(gòu)：每個數(shù)據(jù)元素看做是一個結(jié)點，用圓圈表示。元素之間的關(guān)系用連線表示。281954736集合：數(shù)據(jù)元素除了同屬于一個集合外，它們之間沒有什么關(guān)系。各元素是平等的。123456789線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對一關(guān)系。數(shù)據(jù)元素之間存在線性關(guān)系，也稱先后關(guān)系，每個元素都有一個唯一的前導元素和一個唯一的后繼元素，第一個元素沒有前導，最后一個元素沒有后繼。四種邏輯結(jié)構(gòu)：樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對多的層次關(guān)系。1234567圖結(jié)構(gòu)：數(shù)據(jù)元素之間是任意（孤立點、一對一，一對多，多對多）關(guān)系。281954736數(shù)據(jù)元素之間呈現(xiàn)層次關(guān)系，在樹形結(jié)構(gòu)中，每一個元素通常稱為一個結(jié)點，每個結(jié)點（根結(jié)點除外）有一個父結(jié)點，一個結(jié)點可以有多個子結(jié)點在圖狀結(jié)構(gòu)中每個元素稱為一個結(jié)點，圖狀結(jié)構(gòu)又稱網(wǎng)狀結(jié)構(gòu)。圖結(jié)構(gòu)可表達元素之間的任意關(guān)系。物理結(jié)構(gòu)：也稱為存儲結(jié)構(gòu)，即如何把數(shù)據(jù)元素存儲到計算機的存儲器中（主要指內(nèi)存，外存通常用文件來描述）。物理結(jié)構(gòu)應正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。兩種存儲結(jié)構(gòu)：順序結(jié)構(gòu)：邏輯上相鄰的元素存儲在連續(xù)的存儲單元里。用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)集合中的元素。

借助于數(shù)據(jù)在存儲器中的相對位置表示數(shù)據(jù)之間的關(guān)系。鏈式結(jié)構(gòu)：數(shù)據(jù)元素可存放在任意存儲單元里，數(shù)據(jù)元素之間的關(guān)系用箭頭（指針）表示。用一個指針表示結(jié)點（數(shù)據(jù)元素）之間的邏輯關(guān)系。每個結(jié)點之間沒有對應的物理關(guān)系

線性結(jié)構(gòu)（棧、隊列、線性表）線性結(jié)構(gòu)是一種描述元素先后關(guān)系的數(shù)據(jù)結(jié)構(gòu)，也稱為線性表。線性表的順序存儲結(jié)構(gòu)可以用數(shù)組來表示。

a、元素存儲在一組地址連續(xù)的存儲單元；b、元素的物理順序和邏輯順序一致；c、線性表中的數(shù)據(jù)元素可以隨機存取。

d、不便于進行插入和刪除操作。

線性表的鏈式存儲：a、元素存儲在一組地址不連續(xù)的存儲單元；b、元素的物理順序和邏輯順序不一致；c、線性表中的數(shù)據(jù)元素不可以隨機存取。

d、便于進行插入和刪除操作。數(shù)據(jù)域指針域CBAbottomtop棧(Stack)是一種后進先出操作受限的線性表，它的插入和刪除操作只能在表的一端(表尾)進行。插入：入棧，把新元素放入棧頂top上移刪除：出棧，把棧頂?shù)脑貏h除top下移頭指針尾指針隊列（Queue）是一種先進先出（FirstInLastOut，F(xiàn)ILO）的線性表。只能在表的一端進行插入操作（頭指針改變），在另一端進行刪除操作（尾指針改變）?！纠恳阎€性表

(A，B，C，D，E，F(xiàn)，G)存儲地址如下表所示，頭指針是1438，填寫指針域中的指針并畫出單鏈表結(jié)構(gòu)圖。存儲地址數(shù)據(jù)域指針域1306F1320D1423C1438A1465G1489B1503EBLAMFECGIDHKJNO結(jié)點樹根葉子結(jié)點孩子雙親兄弟度深度樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對多的層次關(guān)系。樹形結(jié)構(gòu)a、數(shù)據(jù)元素之間呈現(xiàn)層次關(guān)系，b、在樹形結(jié)構(gòu)中，根結(jié)點除外，

每個結(jié)點有一個雙親結(jié)點。c、一個結(jié)點可以有多個子結(jié)點，

數(shù)據(jù)之間的關(guān)系是一對多的。d、

葉子結(jié)點沒有子結(jié)點。e、度是指節(jié)點的孩子的個數(shù)。f、深度是組成樹的結(jié)點的最大層數(shù)。2二叉樹二叉樹（BinaryTree）是n（n≥0）個結(jié)點的有限集合，或者是空集，或者是由一個根和分別稱為左子樹、右子樹的兩個不相交的二叉樹構(gòu)成。二叉樹的兩棵子樹有左右之分。樹中結(jié)點的度是任意的，二叉樹中每個結(jié)點的度不能大于2。BGAHEDCFI二叉樹的應用：二叉查找樹（二叉判定樹）二叉排序樹（中序遍歷）霍夫曼編碼（帶權(quán)的二叉樹）圖圖(Graph)是由頂點的有窮非空集合和頂點之間邊的集合組成。通常表示為：G(V,E)，其中：G表示一個圖；V是圖G中頂點的集合；E是圖G中邊的集合。圖的基本概念：頂點(Vertex)邊：無向邊、有向邊無向圖、有向圖權(quán)：與邊相關(guān)的數(shù)，如頂點之間的距離、花費等ABCD246254abcd貪心算法貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關(guān)。TSP問題，在下圖中，現(xiàn)要從濟南出發(fā)，依次旅行完每一個城市，且每個城市只去一次，最后回到濟南，用貪心算法，應按何種順序旅游？最短路程是多少？圖的應用數(shù)據(jù)管理技術(shù)(1)人工管理階段約20世紀50年代中期之前數(shù)據(jù)管理（DataManagement）:對數(shù)據(jù)進行高效地組織、編目、分類、定位、排序、存儲、檢索和維護等。(2)文件系統(tǒng)階段在20世紀50年代后期到60年代中期(3)數(shù)據(jù)庫系統(tǒng)階段

20世紀60年代后期以來數(shù)據(jù)庫數(shù)據(jù)庫(DB):DataBase數(shù)據(jù)庫管理員(DBA):DataBaseAdministrator數(shù)據(jù)庫管理系統(tǒng)(DBMS):DataBbaseManagementSystem數(shù)據(jù)庫應用(DBAP):DataBaseApplication數(shù)據(jù)庫管理系統(tǒng)（DBMS)的基本功能

a、數(shù)據(jù)庫定義：定義數(shù)據(jù)庫中數(shù)據(jù)表的名稱、標題等。

b、數(shù)據(jù)庫操作:向數(shù)據(jù)庫的Table中增加/刪除/更新數(shù)據(jù)及對數(shù)據(jù)進行查詢、檢索、統(tǒng)計等。c、數(shù)據(jù)庫管理控制:控制數(shù)據(jù)庫中數(shù)據(jù)的使用---哪些用戶可以使用,哪些不可以。常見的數(shù)據(jù)庫管理系統(tǒng)有:AccessSQLServerOracleMySQLFoxProSybase……數(shù)據(jù)模型數(shù)據(jù)庫常見的數(shù)據(jù)模型:層次模型：以樹的形式組織數(shù)據(jù)網(wǎng)狀模型：以圖/網(wǎng)的形式組織數(shù)據(jù)關(guān)系模型：以二維表格的形式組織數(shù)據(jù)面向?qū)ο竽Ｐ停翰捎妹嫦驅(qū)ο蟮姆椒▉碓O計數(shù)據(jù)庫其中關(guān)系模型是目前最常見的數(shù)據(jù)模型。數(shù)據(jù)模型是描述數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)的模式，是對客觀事物及其聯(lián)系的抽象化描述。集合運算RABCa12c32d32TABCb22c32d32(1)并R∪TABCa12b22c32d32(2)交R∩TABCc32d32集合運算RABCa12c32d32TABCb22c32d32(3)差R-TABCa12T-RABCb22集合運算RABCa12c32d32TABCb22c32d32(4)廣義笛卡爾積a12a12a12b22c32d32R×TR.AR.BR.CT.AT.BT.Cc32c32c32b22c32d32d32d32d32b22c32d32選擇(Selection)SnoSname95001李勇SsexSageSdept男20計算機95002劉琛女19計算機95003王敏女18信息95004章立男19機械Student查詢計算機系全體學生：查詢計算機系女同學：投影(Projection)SnoSname95001李勇SsexSageSdept男20計算機95002劉琛女19計算機95003王敏女18信息95004章立男19機械StudentSname李勇Sdept計算機劉琛計算機王敏信息章立機械b.查詢學生所在系：Sdept計算機信息機械查詢學生姓名和所在系：投影之后不僅取消了原關(guān)系中的某些列，而且還可能取消某些元組（避免重復行）計算機問題求解過程利用計算機求解問題是問題求解手段的改變，計算機求解問題的過程與人的計算過程不同。計算機問題求解過程包括數(shù)學建模、算法設計、程序設計，最后運行程序才能得到問題的解。數(shù)學建模算法設計程序設計問題的解問題分析運行程序問題數(shù)學建模：將問題抽象為一個數(shù)學問題，并給出求解該數(shù)學問題的數(shù)學模型。問題求解的第一步就是要數(shù)學建模百錢百雞問題、哥尼斯堡七橋問題、漢諾塔問題、TSP問題、阿基米德分牛問題等通過問題分析抽象或引入數(shù)學變量從而將一個具體問題的求解推廣為一類問題的求解。首要的和關(guān)鍵的一步就是建立研究對象的數(shù)學模型，然后才能借助計算機求解。第五章算法設計算法設計包括算法策略設計、數(shù)據(jù)結(jié)構(gòu)設計和控制結(jié)構(gòu)設計。(1)算法策略設計算法是解決問題的方法和步驟，算法設計即設計解決問題的算法策略。TSP問題的算法策略設計：

遍歷算法：出現(xiàn)的問題是：

組合爆炸！對于n個城市路徑組合數(shù)目：(n-1)!

貪心算法：則可以在局部最優(yōu)的基礎上找出可行路徑，但不一定是全局最優(yōu)解。(2)數(shù)據(jù)結(jié)構(gòu)設計算法的數(shù)據(jù)結(jié)構(gòu)設計是指與問題或算法相關(guān)的數(shù)據(jù)之間的邏輯關(guān)系及存儲關(guān)系的設計，即如何來組織數(shù)據(jù)，才能更高效的解決問題。TSP問題：城市映射為編號:A--1,B--2,C--3,D--4城市間距離關(guān)系:矩陣或二維數(shù)組D，用D[i][j]或D[i,j]來城市間的距離

訪問路徑/解:

一維數(shù)組S，用S[j]來按順序存放到過的城市(3)控制結(jié)構(gòu)設計算法的控制結(jié)構(gòu)設計即設計算法的計算步驟或計算規(guī)則，即如何構(gòu)造和表達處理的規(guī)則，以便能夠按規(guī)則逐步計算出結(jié)果?？刂平Y(jié)構(gòu)分為三種：①順序結(jié)構(gòu)：即按書寫的順序從上到下、從左到右執(zhí)行。假設a=5，b=10，如要交換a、b的值，則需按順序執(zhí)行語句：

temp=a;a=b;b=temp;②分支（選擇）結(jié)構(gòu)：根據(jù)條件，成立時執(zhí)行某些操作，不成立則執(zhí)行另一些操作，或者從多個分支中選擇一個來執(zhí)行。③循環(huán)結(jié)構(gòu)：根據(jù)條件，成立則重復執(zhí)行某些操作，不成立時則不再循環(huán)。sum=0;for(i=1;i<=n;i++)sum=sum+i;printf("%d",sum);程序設計程序設計是根據(jù)選定的算法策略和數(shù)據(jù)結(jié)構(gòu)、控制結(jié)構(gòu)設計結(jié)果，給出解決特定問題程序的過程。程序設計往往以某種計算機程序設計語言為工具，如C語言、C++語言、Java語言等，寫出這種語言下的程序。從發(fā)展歷程來看，程序設計語言一般分為機器語言、匯編語言和高級語言。

高級語言程序的通用性和可移植性大為提高。但高級語言所編制的程序不能直接被計算機識別，必須經(jīng)過翻譯才能被執(zhí)行，按照翻譯方式的不同，可將它們分為解釋和編譯兩類程序設計過程應當包括分析、設計、編碼、測試、排錯等不同階段。最后，運行程序，即可得到問題的解。

算法算法（Algorithm）是指解決問題的方案的準確而完整的描述，是一系列解決問題的清晰指令的計算序列。算法具有的５個重要特征：有窮性、確定性、0個或多個輸入、一個或多個輸出、可行性。

算法描述：自然語言、流程圖、N-S流程圖、偽代碼，掌握任意一種。算法的評價和分析算法設計首先要保證算法正確性。只有在算法正確的前提下，討論算法的優(yōu)劣才有意義。首先：要對算法進行正確性分析，這個算法是正確的嗎？算法的輸出是問題的解嗎？其次：算法的復雜性分析。最常見的是時間復雜度分析和空間復雜度分析。求的值，即表達式1+2+3+…+n的值。n為正整數(shù)，由鍵盤輸入。算法描述自然語言描述的算法如下：Step1：從鍵盤輸入正整數(shù)nStep2：設表達式的值用s表示，且s初始化為0，即s←0Step3：設變量i的初值為1，即i←1Step4：把i累加到s中，即s←s+iStep5：i的值增1，即i←i+1Step6：如果i<=n，則轉(zhuǎn)Step4；否則轉(zhuǎn)Step7Step7：輸出s的值Step8：結(jié)束開始輸入ns=0i=1i<=n?s=s+1i=i+1輸出s結(jié)束NY開始輸入nsum=0i=1i<=n?sum=sum+ii=i+1輸出sum結(jié)束偽代碼描述：begininputns=0i=1whilei<=ndobegins←s+ii←i+1endoutputsendN-S流程圖描述流程圖描述分析下列程序段的時間復雜度。temp=a;a=b;b=temp;上面3個語句均為賦值語句，都是元操作，執(zhí)行頻度均為1，因此該段代碼的執(zhí)行時間是與問題規(guī)模n無關(guān)的常數(shù)，即算法的時間復雜度為常數(shù)階，記作T(n)=O(1)。同理，如果算法中僅僅是執(zhí)行了若干條基本操作語句，即使有成千上萬條語句，執(zhí)行時間也不過是一個較大的常數(shù)，也不會隨著問題規(guī)模n的增加而有所增加，因此這類算法的時間復雜度都是O(1)，稱為常量階。分析下列程序段的時間復雜度。s=0;i=1;for(i=1;i<=n;i++)s=s+i;分析該算法，各行執(zhí)行的次數(shù)分別為1、1、n、n，因此時間復雜度為：T(n)=2n+2=O(n)，稱為線性階。

經(jīng)典問題的算法求解窮舉法：銀行密碼：n位0～9之間的任何數(shù)字，密碼有10n種可能。

0-1背包問題：如果有n件物品，所有可能解的情況則有：

要用一個n位二進制計數(shù)器，來表示n件物品放入背包的情況。

TSP旅行商問題：實際上就是路徑的遍歷，出現(xiàn)的問題是：

組合爆炸！對于n個城市路徑組合數(shù)目：(n-1)!貪心算法：0-1背包問題，為了使包內(nèi)物品的總價值最大，先計算出所有物品的單位價值，然后從單位價值由高到低的順序依次選擇物品放入背包，在不超過背包限重的情況下盡可能放更多的物品

TSP旅行商問題：依據(jù)貪心算法思想，每次在選擇下一個城市

的時候，只考慮當前情況，保證迄今為止所經(jīng)過的總路程最短。

經(jīng)典問題的算法求解遞推法：菲波那切數(shù)列

走樓梯：有一段樓梯有N級臺階，規(guī)定每一步只能跨一級或兩級，要登上第N級臺階有幾種不同的走法,臺階走法：f(1)=1f(2)=2f(N)=f(N-1)+f(N-2)

兔子繁殖：1-12月份：幼兔：f(1)=0f(2)=1f(n)=f(n-1)+f(n-2)1-12月份：成兔：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)

1-12月份：總兔：f(1)=1f(2)=2f(n)=f(n-1)+f(n-2)

遞歸法：菲波那切數(shù)列、自然數(shù)的定義自然數(shù)n的階乘定義：

漢諾塔的求解：對于n個金片，移動的次數(shù)是2n-1查找所謂查找，也稱為搜索，是指從若干個對象中，找出想要的對象。順序查找：就是在查找范圍內(nèi)，將給定值按順序逐個與查找對象進行比較，相等即為查找成功，如果全部比較完還沒有相等的則查找失敗。

查找成功的平均長度為：ASL=折半查找：（二分查找）線性表中的記錄是按照關(guān)鍵字有序的（升序或降序）排列。查找成功的平均長度為：ASL=

算法：首先選取表的中間元素，設序號為mid=(1+n)/2，元素Rmid將數(shù)據(jù)表分成大致相等的兩部分{R1,R2,…,Rmid-1}和{Rmid+1,Rmid+2,…,Rn}。先對Rmid和key作比較，假設序列升序有序，則比較結(jié)果有三種情況：首先，將表中間位置元素值與查找數(shù)據(jù)比較：key=Rmid：查找成功，返回元素序號mid。key<Rmid：折半查找前一子表{R1,R2,…,Rmid-1}。key>Rmid：折半查找后一子表{Rmid+1,Rmid+2,…,Rn}。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。折半查找算法演示：數(shù)據(jù)表（查找key=8）K1K2K3K4K5K6K7K8K9K10368121622304558633681216223045586336812162230455863結(jié)論：比較3次終于找到。問題：有哪些數(shù)需要比較1次、2次、3次或4次才能找到？16645382258123063排序：排序是對一組對象按照某種規(guī)則進行有序排列，通常是把一組對象整理成按關(guān)鍵字遞增(或遞減)的排列，關(guān)鍵字是指對象的一個用于排序的特性。選擇排序：首先在所有數(shù)據(jù)（保存于數(shù)組中）中找出最小值，放在第一個數(shù)組元素中；接著在不包含第一個數(shù)組元素的余下的數(shù)組元素中再找出最小值的元素，放置在第二個數(shù)組元素中；如此下去，一直到最后一個元素。冒泡