資源簡(jiǎn)介

浙教版信息技術(shù)必修一《數(shù)據(jù)與計(jì)算》
第二章 算法與問題解決
【知識(shí)結(jié)構(gòu)體系】
【知識(shí)梳理】
一、算法的概念
（一）算法的定義
1. 廣義定義
“算法”指的是解決問題或完成任務(wù)的一系列步驟。廣義的算法中，需要解決的問題不僅僅指?jìng)鹘y(tǒng)意義上的計(jì)算任務(wù)（算術(shù)），也可以是社會(huì)生活中各種事務(wù)的處理。
2. 計(jì)算機(jī)科學(xué)領(lǐng)域定義
“算法”指的是用計(jì)算機(jī)解決問題的步驟，是為了解決問題而需要讓計(jì)算機(jī)有序執(zhí)行的、無(wú)歧義的、有限步驟的集合。這些需要解決的問題不僅包含了數(shù)值計(jì)算，還包含了非數(shù)值計(jì)算的數(shù)據(jù)處理。
（二）算法的特征
1.有窮性：一個(gè)算法的處理步驟必須是有限的。
2.可行性：每一步的操作與要求都是可行的，并且能夠在有限時(shí)間內(nèi)完成。
3.確定性：每一步的執(zhí)行描述必須是明確的
4.0個(gè)或多個(gè)輸入
5.1個(gè)或多個(gè)輸出
（三）算法的要素
1.數(shù)據(jù)
用算法解決問題時(shí)，必須明確參與運(yùn)算的初始數(shù)據(jù)、運(yùn)算時(shí)產(chǎn)生的中間數(shù)據(jù)以及代表問題解決的結(jié)果數(shù)據(jù)。
2.運(yùn)算
在對(duì)數(shù)據(jù)進(jìn)行運(yùn)算時(shí)，必須明確每一步的運(yùn)算是什么、對(duì)哪些數(shù)據(jù)進(jìn)行運(yùn)算等。
3.控制轉(zhuǎn)移
在算法執(zhí)行過(guò)程中，有時(shí)需要根據(jù)數(shù)據(jù)或運(yùn)算結(jié)果的特點(diǎn)進(jìn)行不同的處理，這時(shí)就需要運(yùn)用控制轉(zhuǎn)移來(lái)執(zhí)行不同的操作。
二、算法的描述
（一）自然語(yǔ)言
1.定義：自然語(yǔ)言是人們?cè)谌粘Ｉ钪薪涣魇褂玫恼Z(yǔ)言，通俗易懂
2.變量：數(shù)據(jù)會(huì)發(fā)生改變，由字母、數(shù)字、下劃線等組成的一串字符表示
3.輸入：參與算法運(yùn)算的數(shù)據(jù)可通過(guò)“輸入”獲得
（二）流程圖
1.流程圖描述算法結(jié)構(gòu)清晰、寓意明確。
2.常用的流程圖基本圖形
（三）偽代碼描述算法
偽代碼由于語(yǔ)法比較接近計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，所以描述的算法更加緊湊簡(jiǎn)練，也便于進(jìn)一步轉(zhuǎn)化為相應(yīng)的計(jì)算機(jī)程序。
（四）計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述
為了讓計(jì)算機(jī)幫助人們真正解決問題，需要將算法用某種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)描述，這個(gè)過(guò)程稱為程序編寫（或稱代碼編寫）。
計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言經(jīng)歷了“機(jī)器語(yǔ)言→匯編語(yǔ)言→高級(jí)語(yǔ)言”的發(fā)展歷程。
1.機(jī)器語(yǔ)言：用“0”“1”組成，機(jī)器執(zhí)行效率高但可讀性差、維護(hù)性差。
2.匯編語(yǔ)言：用特定的助記符表示各個(gè)機(jī)器指令，提升效率。
3.高級(jí)語(yǔ)言：接近人們?nèi)粘Ｓ谜Z(yǔ)的符號(hào)來(lái)表示各類指令，如Basic、C、C++、Java等。
三、算法的控制結(jié)構(gòu)
（一）順序結(jié)構(gòu)
1.每個(gè)步驟按照算法中出現(xiàn)的順序依次執(zhí)行。
2.每個(gè)步驟一定會(huì)被執(zhí)行一次，而且只執(zhí)行一次。
（二）分支結(jié)構(gòu)
1.首先進(jìn)行條件判斷，根據(jù)條件滿足與否來(lái)決定執(zhí)行哪個(gè)分支。
2.在一個(gè)分支結(jié)構(gòu)中，必定有一個(gè)分支被執(zhí)行，其他的分支則被忽略。
（三）循環(huán)結(jié)構(gòu)
算法執(zhí)行過(guò)程中，在條件控制下，某些操作步驟需要重復(fù)執(zhí)行（循環(huán)）的控制結(jié)構(gòu)稱為循環(huán)結(jié)構(gòu)。
循環(huán)結(jié)構(gòu)的重復(fù)執(zhí)行（循環(huán)）并不是沒有限制的，而是在條件控制下的一種可控的重復(fù)。當(dāng)需要重復(fù)處理的條件不滿足時(shí)，重復(fù)處理必須能及時(shí)結(jié)束。這樣才符合算法的有窮性特征。
四、用算法解決問題的過(guò)程
（一）抽象與建模
1.提煉核心要素并加以確定或假設(shè)
2.用數(shù)學(xué)符號(hào)描述解決問題的計(jì)算模型
（二）設(shè)計(jì)算法
1.設(shè)計(jì)原則：遵循算法的特征、圍繞算法的要素設(shè)計(jì)算法
2.步驟：輸入數(shù)據(jù)——處理數(shù)據(jù)——輸出處理結(jié)果
（三）描述算法
用流程圖描述算法
【典型例題】
1．某算法的流程圖如圖所示，執(zhí)行這部分流程，若輸入的值為59，則輸出s的值為（ ）
A．000100 B．111011 C．001000 D．110111
2．設(shè)計(jì)算法時(shí)，我們通常采用哪種方法來(lái)確保算法的正確性（ ）
A．代碼審查 B．?dāng)?shù)學(xué)證明 C．測(cè)試 D．用戶反饋
3．某算法的部分流程圖如圖所示
執(zhí)行這部分流程，輸入m，n的值為21、14，則變量n的值是（ ）
A．4 B．7 C．12 D．18
4．設(shè)計(jì)算法時(shí)，以下哪個(gè)不是重要的考慮因素（ ）
A．算法的時(shí)間復(fù)雜度 B．算法的空間復(fù)雜度
C．算法的顏色編碼 D．算法的可擴(kuò)展性
5．在算法描述中，哪種方式最適合用于表達(dá)算法的步驟（ ）
A．流程圖 B．偽代碼 C．自然語(yǔ)言 D．?dāng)?shù)學(xué)公式
6．以下哪種算法設(shè)計(jì)方法適用于解決“排序”問題（ ）
A．分治法 B．動(dòng)態(tài)規(guī)劃 C．貪心算法 D．回溯法
7．在算法設(shè)計(jì)中，哪種方法可以幫助我們避免重復(fù)計(jì)算（ ）
A．使用遞歸 B．使用循環(huán)
C．使用備忘錄技術(shù) D．使用并行計(jì)算
8．算法是解決問題的一系列明確步驟，它具有以下哪些特性（ ）
A．有窮性 B．確定性 C．可行性 D．輸入/輸出
題號(hào) 1 2 3 4 5 6 7 8
答案 A C B C B A C ABCD
【參考答案】

展開更多......

收起↑