等級(jí)考試公共基礎(chǔ)考點(diǎn)分析之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(1)

字號(hào):

1.1 算法
    考點(diǎn)1 算法的基本概念
    計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法,這種算法稱為計(jì)算機(jī)算法。
    算法(algorithm)是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,并且每一個(gè)規(guī)則都是有效的,同時(shí)是明確的;此順序?qū)⒃谟邢薜拇螖?shù)后終止。算法是對(duì)特定問(wèn)題求解步驟的一種描述,它是指令的有限序列,其中每一條指令表示一個(gè)或多個(gè)操作。
    1算法的基本特征
     (1)可行性(effectiveness):針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法,執(zhí)行后能夠得到滿意的結(jié)果。
     (2)確定性(definiteness):算法中的每一個(gè)步驟都必須有明確的定義,不允許有模棱兩可的解釋和多義性。
        (3)有窮性(finiteness):算法必需在有間內(nèi)做完,即算法必需能在執(zhí)行有限個(gè)步驟之后終止。
       (4)擁有足夠的情報(bào):要使算法有效必需為算法提供足夠的情報(bào)當(dāng)算法擁有足夠的情報(bào)時(shí),此算法才的;而當(dāng)提供的情報(bào)不夠時(shí),算法可能無(wú)效。
    2算法的基本要素
       (1)算法中對(duì)數(shù)據(jù)的運(yùn)算和操作:每個(gè)算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列。
    計(jì)算機(jī)可以執(zhí)行的基本操作是以指令的形式描述的。一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合,稱為該計(jì)算機(jī)系統(tǒng)的指令系統(tǒng)。計(jì)算機(jī)程序就是按解題要求從計(jì)算機(jī)指令系統(tǒng)中選擇合適的指令所組成的指令序列在一般的計(jì)算機(jī)系統(tǒng)中,基本的運(yùn)算和操作有以下4類:
        ①算術(shù)運(yùn)算:主要包括加、減、乘、除等運(yùn)算;
        ②邏輯運(yùn)算:主要包括“與”、“或”、“非”等運(yùn)算;
        ③關(guān)系運(yùn)算:主要包括“大于”、“小于”、“等于”、“不等于”等運(yùn)算;
       ④數(shù)據(jù)傳輸:主要包括賦值、輸入、輸出等操作。
       (2)算法的控制結(jié)構(gòu):一個(gè)算法的功能不僅僅取決于所選用的操作,而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。
    算法的控制結(jié)構(gòu)給出了算法的基本框架,它不僅決定了算法中各操作的執(zhí)行順序,而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等。一個(gè)算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。
        (3)算法設(shè)計(jì)的基本方法
    計(jì)算機(jī)算法不同于人工處理的方法,下面是工程上常用的幾種算法設(shè)計(jì),在實(shí)際應(yīng)用時(shí),各種方法之間往往存在著一定的聯(lián)系。
        (1)列舉法
    列舉法是計(jì)算機(jī)算法中的一個(gè)基礎(chǔ)算法。列舉法的基本思想是,根據(jù)提出的問(wèn)題,列舉所有可能的情況,并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?,哪些是不需要的?BR>    列舉法的特點(diǎn)是算法比較簡(jiǎn)單。但當(dāng)列舉的可能情況較多時(shí),執(zhí)行列舉算法的工作量將會(huì)很大。因此,在用列舉法設(shè)計(jì)算法時(shí),使方案優(yōu)化,盡量減少運(yùn)算工作量,是應(yīng)該重點(diǎn)注意的。
        (2)歸納法
    歸納法的基本思想是,通過(guò)列舉少量的特殊情況,經(jīng)過(guò)分析,最后找出一般的關(guān)系。從本質(zhì)上講,歸納就是通過(guò)觀察一些簡(jiǎn)單而特殊的情況,最后總結(jié)出一般性的結(jié)論。
        (3)遞推
     遞推是指從已知的初始條件出發(fā),逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定,或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而確定。遞推本質(zhì)上也屬于歸納法,工程上許多遞推關(guān)系式實(shí)際上是通過(guò)對(duì)實(shí)際問(wèn)題的分析與歸納而得到的,因此,遞推關(guān)系式往往是歸納的結(jié)果。對(duì)于數(shù)值型的遞推算法必須要注意數(shù)值計(jì)算的穩(wěn)定性問(wèn)題。
        (4)遞歸
    人們?cè)诮鉀Q一些復(fù)雜問(wèn)題時(shí),為了降低問(wèn)題的復(fù)雜程度(如問(wèn)題的規(guī)模等),一般總是將問(wèn)題逐層分解,最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程,實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解,而只是當(dāng)解決了最后那些最簡(jiǎn)單的問(wèn)題后,再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合,這就是遞歸的基本思想。
    遞歸分為直接遞歸與間接遞歸兩種。
        (5)減半遞推技術(shù)
    實(shí)際問(wèn)題的復(fù)雜程度往往與問(wèn)題的規(guī)模有著密切的聯(lián)系。因此,利用分治法解決這類實(shí)際問(wèn)題是有效的。工程上常用的分治法是減半遞推技術(shù)。
    所謂“減半”,是指將問(wèn)題的規(guī)模減半,而問(wèn)題的性質(zhì)不變;所謂“遞推”,是指重復(fù)“減半”的過(guò)程。
       (6)回溯法
    在工程上,有些實(shí)際問(wèn)題很難歸納出一組簡(jiǎn)單的遞推公式或直觀的求解步驟,并且也不能進(jìn)行無(wú)限的列舉。對(duì)于這類問(wèn)題,一種有效的方法是“試”。通過(guò)對(duì)問(wèn)題的分析,找出一個(gè)解決問(wèn)題的線索,然后沿著這個(gè)線索逐步試探,若試探成功,就得到問(wèn)題的解,若試探失敗,就逐步回退,換別的路線再逐步試探。