2022年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)學(xué)習(xí)教程算法

1、2022 年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)學(xué)習(xí)教程：算法（一）算法1算法的根本概念算法是指解題方案的精確而完整的描述。即是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算挨次的規(guī)章，并且每一個(gè)規(guī)章都是有效的，且是明確的，沒有二義性，同時(shí)該規(guī)章將在有限次運(yùn)算后可終止。算法的根本特征可行性由于算法的設(shè)計(jì)是為了在某一個(gè)特定的計(jì)算工具上解決某一個(gè)實(shí)際 的問題而設(shè)計(jì)的，因此，它總是受到計(jì)算工具的限制，使執(zhí)行產(chǎn)生偏差。如：計(jì)算機(jī)的數(shù)值有效位是有限的，當(dāng)大數(shù)和小數(shù)進(jìn)展運(yùn)算時(shí)，往往會(huì)由于有效位數(shù)的影響而使小數(shù)喪失，因此，在算法設(shè)計(jì)時(shí)，應(yīng)當(dāng)考慮到這一點(diǎn)。確定性算法的設(shè)計(jì)必需是每一個(gè)步驟都有明確的定義，不允許有模糊的解釋， 也不能有多義性。例如，一個(gè)

2、實(shí)際的問題，小寶和萍萍共有 12 個(gè)蘋果，小寶比萍萍多4 個(gè)，請(qǐng)問小寶和萍萍各有幾個(gè)蘋果？這個(gè)問題，我們可以立一個(gè)方程組x+y=12 和 x-y=4 來求解，要求 x 和 y 的值，公式是正確的，但如何讓計(jì)算能夠進(jìn)展計(jì)算，我們的算法不能把公式直接輸進(jìn)去，而應(yīng)當(dāng)設(shè)計(jì)出解題的步驟和過程。即設(shè)計(jì)的算法是計(jì)算工具所能夠正常解決問題的過程。有窮性算法的有窮性，即在肯定的時(shí)間是能夠完成的，即算法應(yīng)當(dāng)在計(jì)算有限個(gè)步驟后能夠正常完畢。例如，在數(shù)學(xué)中的無窮級(jí)數(shù)，在計(jì)算機(jī)中只能求有限項(xiàng)，即計(jì)算的過程是有窮的。擁有足夠的情報(bào)算法的執(zhí)行與輸入的數(shù)據(jù)和供應(yīng)的初始條件相關(guān)，不同的輸入或初始條件會(huì)有不同的輸出結(jié)果，供應(yīng)精確

3、的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。算法的根本要素一是數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的掌握構(gòu)造。算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法實(shí)際上是按解題要求從環(huán)境能進(jìn)展的全部操作中選擇適宜的操作所組成的一組指令序列。即算法是計(jì)算機(jī)所能夠處理的操作所組成的指令序列。算法的掌握構(gòu)造算法的功能不僅取決于所選用的操作，而且還與各操作之間的挨次有關(guān)。在算法中，操作的執(zhí)行挨次又稱算法的掌握構(gòu)造，一般的算法掌握構(gòu)造有三種：挨次構(gòu)造、選擇構(gòu)造和循環(huán)構(gòu)造。在算法描述是，有相關(guān)的工具對(duì)這三種構(gòu)造進(jìn)展描述，常用的描述工具有：流程圖、N-S 構(gòu)造圖和算法描述語言等。算法設(shè)計(jì)的根本方法為用計(jì)算機(jī)解決實(shí)際問題而設(shè)計(jì)的算法，即是計(jì)算機(jī)

4、算法。通常的算法設(shè)計(jì)有如下幾種：列舉法列舉法的根本思想是，依據(jù)提出的問題，列舉出全部可能的狀況，并用問題中給定的條件檢驗(yàn)?zāi)男┦菨M意條件的，哪些是不滿意條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問題。例如，我國古代的趣味數(shù)學(xué)題：“百錢買百雞”、“雞兔同籠”等，均可采納列舉法進(jìn)展解決。使用列舉法時(shí)，要對(duì)問題進(jìn)展具體的分析，將與問題有關(guān)的學(xué)問條理化、完備化、系統(tǒng)化，從中找出規(guī)律。歸納法歸納法的根本思想是，通過列舉少量的特別狀況，經(jīng)過分析，最終找出一般的關(guān)系。歸納是一種抽象，即從特別現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不行能對(duì)全部的狀況進(jìn)展列舉，因此，該方法得到的結(jié)論只是一種猜想，還需要

5、進(jìn)展證明。遞推遞推，即是從已知的初始條件動(dòng)身，逐次推出所要求的各個(gè)中間環(huán)節(jié)和最終結(jié)果。其中初始條件或問題本身已經(jīng)給定，或是通過對(duì)問題的分析與化簡而確定。遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。例如，裴波那契數(shù)列，是采納遞推的方法解決問題的。遞歸在解決一些簡單問題時(shí)，為了降低問題的簡單程序，通常是將問題逐層分解，最終歸結(jié)為一些最簡潔的問題。這種將問題逐層分解的過程，并沒有對(duì)問題進(jìn)展求解，而只是當(dāng)解決了最終的問題那些最簡潔的問題后， 再沿著原來分解的逆過程逐步進(jìn)展綜合，這就是遞歸的方法。遞歸分為直接遞歸和間接遞歸兩種方法。假如一個(gè)算法直接調(diào)用自己， 稱為直接遞歸調(diào)用；假如一個(gè)算法A 調(diào)

6、用另一個(gè)算法B，而算法B 又調(diào)用算法A，則此種遞歸稱為間接遞歸調(diào)用。減半遞推技術(shù)減半遞推馬上問題的規(guī)模減半，然后，重復(fù)一樣的遞推操作。例如，一元二次方程的求解?；厮莘ㄓ行?shí)際的問題很難歸納出一組簡潔的遞推公式或直觀的求解步驟， 也不能使用無限的列舉。對(duì)于這類問題，只能采納摸索的方法，通過對(duì)問題的分析，找出解決問題的線索，然后沿著這個(gè)線索進(jìn)展摸索，假如摸索勝利，就得到問題的解，假如不勝利，再逐步回退，換別的路線進(jìn)展摸索。這種方法，即稱為回溯法。如人工智能中的機(jī)器人下棋。2算法簡單度算法的簡單度包括時(shí)間簡單度和空間簡單度。1）時(shí)間簡單度即實(shí)現(xiàn)該算法需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的根本運(yùn)

7、算次數(shù)來計(jì)算。同一個(gè)問題規(guī)模下，假如算法執(zhí)行所需要的根本次數(shù)取決于某一特定輸入時(shí)，可以用以下兩種方法來分析算法的工作量：算法工作量=f(n)平均性態(tài)用各種特定輸入下的根本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。設(shè) x 是某個(gè)可能輸入中的某個(gè)特定輸入，p(x)是 x 消失的概率，t(x) 是算法在輸入為x 時(shí)所執(zhí)行的根本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為：Dn 表示當(dāng)規(guī)模為n 時(shí)，算法執(zhí)行時(shí)全部可能輸入的集合。最壞狀況簡單度指在規(guī)模為n 時(shí)，算法所執(zhí)行的根本運(yùn)算的次數(shù)。它定義為：例如，在具有n 個(gè)元素的數(shù)列中搜尋一個(gè)數(shù)x。平均性態(tài)：即該數(shù)在數(shù)列中任何位置消失的數(shù)列是一樣的，也有可能不存在，存在的概率為q。假如有一半的時(shí)機(jī)存在，則概率q 為 1/2，平均性態(tài)：假如查找的元素肯定在數(shù)列中，則每個(gè)數(shù)存在的概率即為1，則平均性態(tài)為：最壞狀況分析：即要查找的元素 X 在數(shù)列的最終或不在數(shù)列中，明顯， 它的最壞狀