計(jì)算機(jī)導(dǎo)論 第五章測(cè)驗(yàn)題答案

1、第五章測(cè)驗(yàn)題答案1.計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的分類(lèi)：(1)機(jī)器語(yǔ)言：由機(jī)器指令構(gòu)成的語(yǔ)言稱(chēng)機(jī)器語(yǔ)言，即用二進(jìn)制編碼組成。(如：onioioi)特點(diǎn)：費(fèi)時(shí)費(fèi)事；難懂容易錯(cuò)；只能在一種型號(hào)計(jì)算機(jī)上運(yùn)行；可以直接在計(jì)算機(jī)上運(yùn)行。(2)匯編語(yǔ)言：用容易記憶的符號(hào)來(lái)代替機(jī)器指令中操作碼和地址碼的一種 語(yǔ)言。(如:ADD代表“+” SUB代表 MOV代表“傳遞”)優(yōu)點(diǎn)：程序直觀容易閱讀；編程工作量相對(duì)小。缺點(diǎn)：只能在一種型號(hào)機(jī)器上運(yùn)行；不能直接在計(jì)算機(jī)上運(yùn)行。(3)高級(jí)程序設(shè)計(jì)語(yǔ)言：高級(jí)程序設(shè)計(jì)語(yǔ)言是一種面向過(guò)程或者面向?qū)ο蟮?語(yǔ)言，不面向機(jī)器，用一些符號(hào)或者數(shù)字對(duì)求解的問(wèn)題或者現(xiàn)實(shí)世界進(jìn)行描 述。特點(diǎn)： 直觀

2、、易寫(xiě)、易讀、工作量??；不依賴(lài)于具體的機(jī)器；便于程序交流；不可直接在計(jì)算機(jī)上運(yùn)行，經(jīng)編譯程序編譯成機(jī)器語(yǔ)言后方可運(yùn)行。.算法(Algorithm)是對(duì)特定問(wèn)題求解步驟準(zhǔn)確而完整的描述，它的表現(xiàn) 形式是計(jì)算機(jī)指令的有序系列，執(zhí)行這些指令就可解決特定問(wèn)題。一個(gè)好的算 法應(yīng)當(dāng)具有以下5個(gè)重要特性。(1)有限性：算法在執(zhí)行有限步之后必須終止，且每一步都應(yīng)在有限的時(shí)間 內(nèi)完成；(2)確定性：算法的每一步必須要有確切的含義，不能存在二義性；(3)可行性：算法的每一步都是可執(zhí)行的，可以通過(guò)有限次操作來(lái)完成其功 能；(4)輸入：一個(gè)算法具有。個(gè)或多個(gè)輸入；(5)輸出：一個(gè)算法具有1個(gè)或多個(gè)輸出。.常用算法的描

3、述方法有：自然語(yǔ)言法、流程圖法、N-S流程圖法、偽代 碼法等。(1)自然語(yǔ)言:就是采用人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，來(lái)描述解決問(wèn)題的方法和步 驟；這種描述方法通俗易懂，即使是不熟悉計(jì)算機(jī)語(yǔ)言的用戶也很容易理解程 序。(2)流程圖:流程圖是以特定的圖形符號(hào)加上說(shuō)明來(lái)表示算法，通常是用一 些圖框來(lái)表示各種操作。(3)N-S圖是在流程圖的基礎(chǔ)上完全去掉流程線，并將全部算法寫(xiě)在一個(gè)矩 形框內(nèi)，且框內(nèi)還可以包含其他框的表示形式。N-S圖包括順序、選擇和循環(huán)3 種基本結(jié)構(gòu)，如下列圖所示：當(dāng)條件為真時(shí)循環(huán)體循環(huán)結(jié)構(gòu)(4)偽代碼:偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào).偽代碼 通常采用自然語(yǔ)言、數(shù)學(xué)公式和符號(hào)

4、來(lái)描述算法的操作步驟，同時(shí)采用計(jì)算機(jī) 高級(jí)語(yǔ)言的控制結(jié)構(gòu)來(lái)描述算法步驟的執(zhí)行順序。在程序開(kāi)發(fā)期間，偽代碼經(jīng) 常用于“規(guī)劃” 一個(gè)程序，然后再轉(zhuǎn)換成某種高級(jí)語(yǔ)言程序。.計(jì)算機(jī)技術(shù)所涉及的算法比擬多，常用的算法有枚舉法、遞推法、遞歸 法、貪心算法、分治法、回溯法等.(1)枚舉法，或稱(chēng)為窮舉法，其基本思路是：對(duì)于要解決的問(wèn)題，列舉出它 所有可能的情況，逐個(gè)判斷哪些是符合問(wèn)題所要求的條件，從而得到問(wèn)題的 解；(2)遞推法:是按照一定的規(guī)律來(lái)計(jì)算序列中的某個(gè)項(xiàng)，通常是通過(guò)計(jì)算前 面的一些項(xiàng)來(lái)得出序列中指定項(xiàng)的值；(3)遞歸法:程序直接或間接自己調(diào)用自己的方法簡(jiǎn)稱(chēng)為遞歸，它通常是把 一個(gè)大型的、復(fù)雜的問(wèn)題

5、層層轉(zhuǎn)化為一個(gè)個(gè)與原問(wèn)題相似的、規(guī)模較小的問(wèn)題 來(lái)進(jìn)行求解；(4)貪心算法:貪心算法采用自頂向下，以迭代的方式做出相繼的貪心選 擇，每做一次貪心選擇就將所求解問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每 一步貪心選擇，就可得到問(wèn)題的一個(gè)最優(yōu)解。貪心算法的每一步都能獲得局部 最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)解，所以貪婪法不能回溯。(5)分治法：分治法是把一個(gè)復(fù)雜的問(wèn)題分解成兩個(gè)或更多個(gè)相同或相似的 子問(wèn)題，再把子問(wèn)題分解成更小的子問(wèn)題，直到最后的子問(wèn)題可以進(jìn)行簡(jiǎn)單的 直接求解，合并所有子問(wèn)題的解就可得到原問(wèn)題的解。(6)回溯法：回溯法的基本思想是，在包含問(wèn)題所有解的解空間樹(shù)中，按照 深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度搜索解空間樹(shù)；當(dāng)搜索到某一結(jié)點(diǎn) 時(shí)，要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果包含就從該結(jié)點(diǎn)出發(fā)繼續(xù)搜索下 去，否那么就逐層向其祖先結(jié)點(diǎn)