算法設(shè)計(jì)與分析第一章算法設(shè)計(jì)基礎(chǔ)1234算法的基本概念為什么學(xué)習(xí)和研究算法重要的問題類型小結(jié)１.１算法及其特性算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。1.算法的特性4輸出2可行性30個(gè)或多個(gè)輸入1確定性5有窮性算法：操作步驟滿足確定性、有窮性、可行性輸入輸出11一月2023

5).有窮性finiteness

算法必須在執(zhí)行有窮步后終止,且每一步均在有限時(shí)間內(nèi)完成。

1).確定性definiteness

算法的每個(gè)步驟必須有明確的意義,對(duì)每種可能的情況,算法都要給出確定的操作。(執(zhí)行的動(dòng)作是相當(dāng)清楚的、無二義性的)2).能行性effectiveness

算法中的每個(gè)步驟是能夠相當(dāng)基本的，是可實(shí)現(xiàn)的。算法執(zhí)行結(jié)果能達(dá)到預(yù)期目的。（原理上能由人用紙和筆在有限的時(shí)間內(nèi)完成）

3).有0個(gè)或多個(gè)輸入項(xiàng)

即執(zhí)行算法時(shí)所需要的初始數(shù)據(jù)，這些輸入取自特定的對(duì)象集合。4).至少有一個(gè)輸出項(xiàng)

它是執(zhí)行算法的結(jié)果。這些輸出是同輸入有某種特定關(guān)系的量。

(沒有輸出的算法是沒有意義的)

算法分類數(shù)值計(jì)算方法（求解數(shù)值問題，插值計(jì)算、數(shù)值積分等）非數(shù)值計(jì)算方法（求解非數(shù)值問題，主要進(jìn)行判斷比較）處理方式上串行算法:串行計(jì)算機(jī)上執(zhí)行的算法.并行算法:并行計(jì)算機(jī)上執(zhí)行的算法.解法上

算法的三個(gè)要素1).數(shù)據(jù):

運(yùn)算序列中作為運(yùn)算對(duì)象和結(jié)果的數(shù)據(jù).2).運(yùn)算:

運(yùn)算序列中的各種運(yùn)算:賦值,算術(shù)和邏輯運(yùn)算

3).控制和轉(zhuǎn)移:

運(yùn)算序列中的控制和轉(zhuǎn)移.問題—Problem

規(guī)定了輸入與輸出之間的關(guān)系，可以用通用語言來描述；問題實(shí)例—InstanceofaProblem

某一個(gè)問題實(shí)例包含了求解該問題所需輸入；輸入:由n個(gè)數(shù)組成的一個(gè)序列<a1,a2,,an>輸出:對(duì)輸入系列的一個(gè)排列(重排）

<a1’,a2’,,an’>，使得<a1’a2’

an’>排序問題的一個(gè)實(shí)例輸入:<31,41,59,26,41,58>——

輸出:<26,31,41,41,58,59>算法概念理解:問題及問題實(shí)例算法的其他特性p54抽象分級(jí)2健壯性3可理解性1正確性5高效性

算法的描述方法4程序設(shè)計(jì)語言2程序流程圖3偽代碼1自然語言

算法設(shè)計(jì)的一般過程滿意待求解的問題選擇算法設(shè)計(jì)技術(shù)設(shè)計(jì)并描述算法手工運(yùn)行算法根據(jù)算法編寫代碼分析算法的效率分析問題不滿意１.2為什么要學(xué)習(xí)和研究算法算法在問題求解中的地位書例算法訓(xùn)練能夠提高計(jì)算思維能力計(jì)算思維能力（形式化、模式化、抽象思維與邏輯思維）算法設(shè)計(jì)與分析能力程序設(shè)計(jì)與實(shí)現(xiàn)能力和系統(tǒng)能力算法研究是推動(dòng)計(jì)算機(jī)技術(shù)發(fā)展的關(guān)鍵1.檢索技術(shù)2.壓縮與解壓縮3.信息安全與數(shù)據(jù)加密1.3重要的問題類型1）查找問題2）排序問題3）圖問題4）組合問題5）幾何問題案例一——查找問題231333231788131723233313233323178132333231781323233317813172323338案例二——排序問題voidinsertSort(intr[],intn){ for(i=2;i<=n;i++){r[0]=r[i];

//把要比較的數(shù)據(jù)暫存r0

j=i-1;//記錄排序好的位置

for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j]; j=j-1; } r[j+1]=r[0]; }}案例二——排序問題r[0]r[1]r[2]r[i]N個(gè)案例三——圖問題案例四——組合問題最小乘車費(fèi)用假設(shè)12345678910費(fèi)用122131404958697990101而任意一輛汽車從不行駛超過10公里。某人想行駛n公里，假設(shè)他可以任意次換車，請(qǐng)你幫他找到一種乘車方案，使得總費(fèi)用最小。案例五——幾何問題怎么修圍墻滿足利用最大化？閱讀材料——算法研究與圖靈獎(jiǎng)習(xí)題用計(jì)算機(jī)求解任何問題離不開程序設(shè)計(jì)，而程序設(shè)計(jì)的核心是算法設(shè)計(jì)。算法對(duì)程序設(shè)計(jì)的指導(dǎo)可以延續(xù)幾年甚至