程序算法描述流程圖
程序算法描述流程圖
算法是指解題方案的準(zhǔn)確而完整的描述,是一系列解決問(wèn)題的清晰指令,算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。以下是學(xué)習(xí)啦小編為大家整理的關(guān)于程序算法描述流程圖,給大家作為參考,歡迎閱讀!
程序算法描述流程圖
算法的方法
遞推法
遞推是序列計(jì)算機(jī)中的一種常用算法。它是按照一定的規(guī)律來(lái)計(jì)算序列中的每個(gè)項(xiàng),通常是通過(guò)計(jì)算機(jī)前面的一些項(xiàng)來(lái)得出序列中的指定項(xiàng)的值。其思想是把一個(gè)復(fù)雜的龐大的計(jì)算過(guò)程轉(zhuǎn)化為簡(jiǎn)單過(guò)程的多次重復(fù),該算法利用了計(jì)算機(jī)速度快和不知疲倦的機(jī)器特點(diǎn)。
遞歸法
程序調(diào)用自身的編程技巧稱(chēng)為遞歸(recursion)。一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法,它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解,遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算,大大地減少了程序的代碼量。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。一般來(lái)說(shuō),遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿(mǎn)足時(shí),遞歸前進(jìn);當(dāng)邊界條件滿(mǎn)足時(shí),遞歸返回。
注意:
(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身;
(2) 在使用遞歸策略時(shí),必須有一個(gè)明確的遞歸結(jié)束條件,稱(chēng)為遞歸出口。
窮舉法
窮舉法,或稱(chēng)為暴力破解法,其基本思路是:對(duì)于要解決的問(wèn)題,列舉出它的所有可能的情況,逐個(gè)判斷有哪些是符合問(wèn)題所要求的條件,從而得到問(wèn)題的解。它也常用于對(duì)于密碼的破譯,即將密碼進(jìn)行逐個(gè)推算直到找出真正的密碼為止。例如一個(gè)已知是四位并且全部由數(shù)字組成的密碼,其可能共有10000種組合,因此最多嘗試10000次就能找到正確的密碼。理論上利用這種方法可以破解任何一種密碼,問(wèn)題只在于如何縮短試誤時(shí)間。因此有些人運(yùn)用計(jì)算機(jī)來(lái)增加效率,有些人輔以字典來(lái)縮小密碼組合的范圍。
貪心算法
貪心算法是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。
用貪心法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行,常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇,而不考慮各種可能的整體情況,它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間,它采用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題, 通過(guò)每一步貪心選擇,可得到問(wèn)題的一個(gè)最優(yōu)解,雖然每一步上都要保證能獲得局部最優(yōu)解,但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的,所以貪婪法不要回溯。
貪婪算法是一種改進(jìn)了的分級(jí)處理方法,其核心是根據(jù)題意選取一種量度標(biāo)準(zhǔn),然后將這多個(gè)輸入排成這種量度標(biāo)準(zhǔn)所要求的順序,按這種順序一次輸入一個(gè)量,如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最佳解加在一起不能產(chǎn)生一個(gè)可行解,則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優(yōu)解的分級(jí)處理方法稱(chēng)為貪婪算法。
對(duì)于一個(gè)給定的問(wèn)題,往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來(lái),這些量度標(biāo)準(zhǔn)似乎都是可取的,但實(shí)際上,用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問(wèn)題的最優(yōu)解,而是次優(yōu)解。因此,選擇能產(chǎn)生問(wèn)題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。
一般情況下,要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事,但對(duì)某問(wèn)題能選擇出最優(yōu)量度標(biāo)準(zhǔn)后,用貪婪算法求解則特別有效。
分治法
分治法是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題,再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解,原問(wèn)題的解即子問(wèn)題的解的合并。
分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征:
(1) 該問(wèn)題的規(guī)??s小到一定的程度就可以容易地解決;
(2) 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題,即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì);
(3) 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解;
(4) 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的,即子問(wèn)題之間不包含公共的子子問(wèn)題。
動(dòng)態(tài)規(guī)劃法
動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的,用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題的方法。其基本思想是,將原問(wèn)題分解為相似的子問(wèn)題,在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ),被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。
動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法,而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計(jì)算那樣,具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對(duì)一種最優(yōu)化問(wèn)題,由于各種問(wèn)題的性質(zhì)不同,確定最優(yōu)解的條件也互不相同,因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問(wèn)題,有各具特色的解題方法,而不存在一種萬(wàn)能的動(dòng)態(tài)規(guī)劃算法,可以解決各類(lèi)最優(yōu)化問(wèn)題。因此讀者在學(xué)習(xí)時(shí),除了要對(duì)基本概念和方法正確理解外,必須具體問(wèn)題具體分析處理,以豐富的想象力去建立模型,用創(chuàng)造性的技巧去求解。
迭代法
迭代法也稱(chēng)輾轉(zhuǎn)法,是一種不斷用變量的舊值遞推新值的過(guò)程,跟迭代法相對(duì)應(yīng)的是直接法(或者稱(chēng)為一次解法),即一次性解決問(wèn)題。迭代法又分為精確迭代和近似迭代。“二分法”和“牛頓迭代法”屬于近似迭代法。迭代算法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn),讓計(jì)算機(jī)對(duì)一組指令(或一定步驟)進(jìn)行重復(fù)執(zhí)行,在每次執(zhí)行這組指令(或這些步驟)時(shí),都從變量的原值推出它的一個(gè)新值。
分支界限法
分枝界限法是一個(gè)用途十分廣泛的算法,運(yùn)用這種算法的技巧性很強(qiáng),不同類(lèi)型的問(wèn)題解法也各不相同。
分支定界法的基本思想是對(duì)有約束條件的最優(yōu)化問(wèn)題的所有可行解(數(shù)目有限)空間進(jìn)行搜索。該算法在具體執(zhí)行時(shí),把全部可行的解空間不斷分割為越來(lái)越小的子集(稱(chēng)為分支),并為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界(稱(chēng)為定界)。在每次分支后,對(duì)凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支,這樣,解的許多子集(即搜索樹(shù)上的許多結(jié)點(diǎn))就可以不予考慮了,從而縮小了搜索范圍。這一過(guò)程一直進(jìn)行到找出可行解為止,該可行解的值不大于任何子集的界限。因此這種算法一般可以求得最優(yōu)解。
與貪心算法一樣,這種方法也是用來(lái)為組合優(yōu)化問(wèn)題設(shè)計(jì)求解算法的,所不同的是它在問(wèn)題的整個(gè)可能解空間搜索,所設(shè)計(jì)出來(lái)的算法雖其時(shí)間復(fù)雜度比貪婪算法高,但它的優(yōu)點(diǎn)是與窮舉法類(lèi)似,都能保證求出問(wèn)題的最佳解,而且這種方法不是盲目的窮舉搜索,而是在搜索過(guò)程中通過(guò)限界,可以中途停止對(duì)某些不可能得到最優(yōu)解的子空間進(jìn)一步搜索(類(lèi)似于人工智能中的剪枝),故它比窮舉法效率更高。
回溯法
回溯法(探索與回溯法)是一種選優(yōu)搜索法,按選優(yōu)條件向前搜索,以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí),發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo),就退回一步重新選擇,這種走不通就退回再走的技術(shù)為回溯法,而滿(mǎn)足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為“回溯點(diǎn)”。
其基本思想是,在包含問(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)不包含問(wèn)題的解,則逐層向其祖先結(jié)點(diǎn)回溯。(其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法)。 若用回溯法求問(wèn)題的所有解時(shí),要回溯到根,且根結(jié)點(diǎn)的所有可行的子樹(shù)都要已被搜索遍才結(jié)束。 而若使用回溯法求任一個(gè)解時(shí),只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。
程序算法描述流程圖相關(guān)文章:
1.程序算法流程圖