可計(jì)算性理論,亦稱(chēng)算法理論或能行性理論,計(jì)算機(jī)科學(xué)的理論基礎(chǔ)之一。是研究計(jì)算的一般性質(zhì)的數(shù)學(xué)理論??捎?jì)算性理論通過(guò)建立計(jì)算的數(shù)學(xué)模型,精確區(qū)分哪些是可計(jì)算的,哪些是不可計(jì)算的。計(jì)算的過(guò)程是執(zhí)行算法的過(guò)程。可計(jì)算性理論的重要課題之一,是將算法這一直觀概念精確化。算法概念精確化的途徑很多,其中之一是通過(guò)定義抽象計(jì)算機(jī),把算法看作抽象計(jì)算機(jī)的程序。通常把那些存在算法計(jì)算其值的函數(shù)叫做可計(jì)算函數(shù)。因此,可計(jì)算函數(shù)的精確定義為:能夠在抽象計(jì)算機(jī)上編出程序計(jì)算其值的函數(shù)。這樣就可以討論哪些函數(shù)是可計(jì)算的,哪些函數(shù)是不可計(jì)算的。
計(jì)算:核算數(shù)目,根據(jù)已知量算出未知量;運(yùn)算。
㈠進(jìn)位計(jì)數(shù)制表示方法 任意一個(gè)數(shù)N可以用下式表示: N=(dn-1 dn-2 …… d1 d0 d-1 …… d-m)r = dn-1 rn-1 + dn-2rn-2 + …… +d1r1 + d0r0 + d-1 r-1 + …… d-m r-m 其中:r為基數(shù) n、m為正整數(shù),分別代表整數(shù)和小數(shù)的位數(shù) di 為第i位的數(shù)碼,可以是0~(r-1)中的一個(gè) ri 為第i位的權(quán) ㈡不同進(jìn)位計(jì)數(shù)制的相互轉(zhuǎn)換 1.二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù) 1)按“權(quán)”展開(kāi)法 例(11011.1)2=1*24+1*23+0*22+1*21+1*20+1*2-1 =27.5 2)按基值重復(fù)相乘(除)法 (略) 2.十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù) 1)重復(fù)相除(乘)法 規(guī)則:① 整數(shù)部分除2取余數(shù),直到商為0; ② 小數(shù)部分乘2取整數(shù),直到小數(shù)部分為0。
例 將十進(jìn)制數(shù)123.6875轉(zhuǎn)換成二進(jìn)制數(shù) 解: ① 整數(shù)部分 重復(fù)除以2 得商 余數(shù) 123÷2 61 1 最低位 61÷2 30 1 30÷2 15 0 15÷2 7 1 7÷2 3 1 3÷2 1 1 1÷2 0 1 最高位 整數(shù)部分 (123)10 = 1111011 ② 小數(shù)部分 重復(fù)乘以2 得乘積 取整數(shù)部分 0.6875*2 1.3750 1 最高位 0.3750*2 0.7500 0 0.7500*2 1.5000 1 0.5000*2 1.0000 1 最低位 小數(shù)部分 (0.6875)10 = 1011 故(123.6875)10 = 1111011.1011 2)減權(quán)定位法 (略) 3.二進(jìn)制數(shù)與八進(jìn)制數(shù)、十六進(jìn)制數(shù)之間的轉(zhuǎn)換 ① 3位二進(jìn)制數(shù)對(duì)應(yīng)于1位八進(jìn)制數(shù) ② 4位二進(jìn)制數(shù)對(duì)應(yīng)于1位十六進(jìn)制數(shù) 例 將二進(jìn)制數(shù)(1111000010.01101)轉(zhuǎn)換成八進(jìn)制和十六進(jìn)制數(shù)。 解:① 轉(zhuǎn)換成八進(jìn)制數(shù) 以小數(shù)點(diǎn)為基準(zhǔn)點(diǎn),按3位為一組劃分二進(jìn)制數(shù),然后將每一組二進(jìn)制碼分別轉(zhuǎn)換成對(duì)應(yīng)的八進(jìn)制碼。
001,111,000,010.011,010 1 7 0 2 . 3 2 即1111000010.01101 = (1702.32)8 ② 轉(zhuǎn)換成十六進(jìn)制數(shù) 以小數(shù)點(diǎn)為基準(zhǔn)點(diǎn),按4位為一組劃分二進(jìn)制數(shù),然后將每一組二進(jìn)制碼分別轉(zhuǎn)換成對(duì)應(yīng)的八進(jìn)制碼。 0011,1100,0010.0110,1000 3 C 2 . 6 8 即1111000010.01101 = (3C2.68)16 反過(guò)來(lái),1位八進(jìn)制數(shù)對(duì)應(yīng)于3位二進(jìn)制數(shù),1位十六進(jìn)制數(shù)對(duì)應(yīng)于4位二進(jìn)制數(shù),如: (7652.342)8 = 111,110,101,010.011,100,010 (8CE4.D62)16 = 1000,1100,1110,0100.1101,0110,0010 2.2計(jì)算機(jī)中數(shù)值型數(shù)據(jù)的表示方法 2.2.1 無(wú)符號(hào)數(shù)和有符號(hào)數(shù) ㈠ 無(wú)符號(hào)數(shù) 無(wú)符號(hào)數(shù)是指沒(méi)有符號(hào)的數(shù),即正整數(shù),在機(jī)器字長(zhǎng)中的全部數(shù)位均用來(lái)表示數(shù)值的大小,相當(dāng)于數(shù)的絕對(duì)值。
例如10010110表示96H(十進(jìn)制數(shù)150)。 對(duì)于字長(zhǎng)為n位的無(wú)符號(hào)數(shù)的表示范圍是0~(2n-1)。
如機(jī)器字長(zhǎng)16位,無(wú)符號(hào)數(shù)的表示范圍為0~65535。 ㈡ 有符號(hào)數(shù) 1、機(jī)器真值 對(duì)有符號(hào)數(shù),在機(jī)器內(nèi)部用“1”表示“+”號(hào),用“0”表示“-”,即用數(shù)字來(lái)表示“+”、“-”號(hào),并規(guī)定放在有效數(shù)字的前面。
例如有符號(hào)數(shù)(小數(shù)): +0.1011 在機(jī)器中表示為 01011 ↑小數(shù)點(diǎn)位置 -0.1011 在機(jī)器中表示為 11011 ↑小數(shù)點(diǎn)位置 又如有符號(hào)數(shù)(整數(shù)): +1100 在機(jī)器中表示為 01100 ↑小數(shù)點(diǎn)位置 -1100 在機(jī)器中表示為 11100 ↑小數(shù)點(diǎn)位置 有符號(hào)數(shù)是指將符號(hào)數(shù)字化后放在有效數(shù)字的前面而組成的數(shù)。把符號(hào)“數(shù)字化”的數(shù)叫做機(jī)器數(shù),而把帶正、負(fù)號(hào)的數(shù)叫做真值。
2、原碼表示法 原碼表示法是一種最簡(jiǎn)單的機(jī)器數(shù)表示法,用最高位表示符號(hào)位,符號(hào)位為“O”表示該數(shù)為正,符號(hào)位為“I”表示該數(shù)為負(fù),數(shù)值部分就是原來(lái)的數(shù)值,即真值的絕對(duì)值,所以原碼表示又稱(chēng)作帶符號(hào)的絕對(duì)值表示。 為了書(shū)寫(xiě)方便,約定在整數(shù)的符號(hào)位和有效數(shù)值之間加“,”表示區(qū)分,對(duì)小數(shù),直接用小數(shù)點(diǎn)“.”來(lái)區(qū)分,如0.1011、1.1011、0,1100、1,1100。
整數(shù)原碼的定義為: 0,x 0≤x。
根據(jù)我個(gè)人的理解:算法就是解決問(wèn)題的具體的方法和步驟,所以具有以下性質(zhì):1、有窮性: 一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束(如果步驟無(wú)限,問(wèn)題就無(wú)法解決)2、確切性:步驟必須明確,說(shuō)清楚做什么。
3、輸入:即解決問(wèn)題前我們所掌握的條件。4、輸出:輸出即我們需要得到的答案。
5、可行性:邏輯不能錯(cuò)誤,步驟必須有限,必須得到結(jié)果。算法通俗的講:就是解決問(wèn)題的方法和步驟。
在計(jì)算機(jī)發(fā)明之前便已經(jīng)存在。只不過(guò)在計(jì)算機(jī)發(fā)明后,其應(yīng)用變得更為廣泛。
通過(guò)簡(jiǎn)單的算法,利用電腦的計(jì)算速度,可以讓問(wèn)題變得簡(jiǎn)單。譬如:計(jì)算 1*2*3*4。
*999999999*1000000000 如果人為計(jì)算,可想而知,即使你用N卡車(chē)的紙張都很難計(jì)算出來(lái),即使算出來(lái)了,也很難保證其準(zhǔn)確性。
如果用VB算法:dim a as integer a=1 For i =1 to 1000000000 a=a*i next i input a 就這樣,簡(jiǎn)單的算法,通過(guò)計(jì)算機(jī)強(qiáng)大的計(jì)算能力,問(wèn)題就解決了。關(guān)于這段算法的解釋?zhuān)篿每乘一次,其數(shù)值都會(huì)增大1,一直乘到1000000000,這樣,就將從1到1000000000的每個(gè)數(shù)都乘了。
而且每乘一次,就將結(jié)束賦給a,這樣,a就代表了前面的相乘的所有結(jié)果,一直乘到1000000000。最后得到的a,就是我們想要的。
〓以下是百度百科復(fù)制過(guò)來(lái)的,如果你有足夠耐心,可以參考一下。 算法(Algorithm)是一系列解決問(wèn)題的清晰指令,也就是說(shuō),能夠?qū)σ欢ㄒ?guī)范的輸入,在有限時(shí)間內(nèi)獲得所要求的輸出。
如果一個(gè)算法有缺陷,或不適合于某個(gè)問(wèn)題,執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。
一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。 算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。
或者看成按照要求設(shè)計(jì)好的有限的確切的計(jì)算序列,并且這樣的步驟和序列可以解決一類(lèi)問(wèn)題。 一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征: 1、有窮性: 一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束; 2、確切性: 算法的每一步驟必須有確切的定義; 3、輸入:一個(gè)算法有0個(gè)或多個(gè)輸入,以刻畫(huà)運(yùn)算對(duì)象的初始情況,所謂0個(gè)輸入是指算法本身定除了初始條件; 4、輸出:一個(gè)算法有一個(gè)或多個(gè)輸出,以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。
沒(méi)有輸出的算法是毫無(wú)意義的; 5、可行性: 算法原則上能夠精確地運(yùn)行,而且人們用筆和紙做有限次運(yùn)算后即可完成。 計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾著過(guò)一本著名的書(shū)《數(shù)據(jù)結(jié)構(gòu)十算法= 程序》,可見(jiàn)算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。
[編輯本段]算法的復(fù)雜度 同一問(wèn)題可用不同算法解決,而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。
一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮。 時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。
一般來(lái)說(shuō),計(jì)算機(jī)算法是問(wèn)題規(guī)模n 的函數(shù)f(n),算法的時(shí)間復(fù)雜度也因此記做 T(n)=Ο(f(n)) 因此,問(wèn)題的規(guī)模n 越大,算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n) 的增長(zhǎng)率正相關(guān),稱(chēng)作漸進(jìn)時(shí)間復(fù)雜度(Asymptotic Time Complexity)。 空間復(fù)雜度 算法的空間復(fù)雜度是指算法需要消耗的空間資源。
其計(jì)算和表示方法與時(shí)間復(fù)雜度類(lèi)似,一般都用復(fù)雜度的漸近性來(lái)表示。同時(shí)間復(fù)雜度相比,空間復(fù)雜度的分析要簡(jiǎn)單得多。
詳見(jiàn)百度百科詞條"算法復(fù)雜度" [編輯本段]算法設(shè)計(jì)與分析的基本方法 1.遞推法 遞推法是利用問(wèn)題本身所具有的一種遞推關(guān)系求問(wèn)題解的一種方法。它把問(wèn)題分成若干步,找出相鄰幾步的關(guān)系,從而達(dá)到目的,此方法稱(chēng)為遞推法。
2.遞歸 遞歸指的是一個(gè)過(guò)程:函數(shù)不斷引用自身,直到引用的對(duì)象已知 3.窮舉搜索法 窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn),并從眾找出那些符合要求的候選解作為問(wèn)題的解。 4.貪婪法 貪婪法是一種不追求最優(yōu)解,只希望得到較為滿(mǎn)意解的方法。
貪婪法一般可以快速得到滿(mǎn)意的解,因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇,而不考慮各種可能的整體情況,所以貪婪法不要回溯。
5.分治法 把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題,再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解,原問(wèn)題的解即子問(wèn)題的解的合并。 6.動(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)域。
7.迭代法 迭代是數(shù)值分析中通過(guò)從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來(lái)解決問(wèn)題(一般是解方程或者方程組)的過(guò)程,為實(shí)現(xiàn)這一過(guò)程所使用的方法統(tǒng)稱(chēng)為迭代法。[編輯本段]算法分類(lèi) 算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。
[編輯本段]舉例 經(jīng)典的算法有很多,如:"歐幾里德算法"。
算法是一系列解決問(wèn)題的清晰指令,也就是說(shuō),能夠?qū)σ欢ㄒ?guī)范的輸入,在有限時(shí)間內(nèi)獲得所要求的輸出。
算法常常含有重復(fù)的步驟和一些比較或邏輯判斷。如果一個(gè)算法有缺陷,或不適合于某個(gè)問(wèn)題,執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。
不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。
算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。一般來(lái)說(shuō),計(jì)算機(jī)算法是問(wèn)題規(guī)模n 的函數(shù)f(n),算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n) 的增長(zhǎng)率正相關(guān),稱(chēng)作漸進(jìn)時(shí)間復(fù)雜度(Asymptotic Time Complexity)。
時(shí)間復(fù)雜度用“O(數(shù)量級(jí))”來(lái)表示,稱(chēng)為“階”。常見(jiàn)的時(shí)間復(fù)雜度有: O(1)常數(shù)階;O(log2n)對(duì)數(shù)階;O(n)線性階;O(n2)平方階。
算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類(lèi)似,一般都用復(fù)雜度的漸近性來(lái)表示。
同時(shí)間復(fù)雜度相比,空間復(fù)雜度的分析要簡(jiǎn)單得多。 [font class="Apple-style-span" style="font-weight: bold;" id="bks_etfhxykd"]算法 Algorithm [/font] 算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。
通俗點(diǎn)說(shuō),就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中,無(wú)論是形成解題思路還是編寫(xiě)程序,都是在實(shí)施某種算法。
前者是推理實(shí)現(xiàn)的算法,后者是操作實(shí)現(xiàn)的算法。 一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征: 1、有窮性: 一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束; 2、確切性: 算法的每一步驟必須有確切的定義; 3、輸入:一個(gè)算法有0個(gè)或多個(gè)輸入,以刻畫(huà)運(yùn)算對(duì)象的初始情況,所謂0個(gè)輸入是指算法本身定除了初始條件; 4、輸出:一個(gè)算法有一個(gè)或多個(gè)輸出,以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。
沒(méi)有輸出的算法是毫無(wú)意義的; 5、可行性: 算法原則上能夠精確地運(yùn)行,而且人們用筆和紙做有限次運(yùn)算后即可完成。 算法的設(shè)計(jì)要求。
算法和程序嘛。。。對(duì)過(guò)程化程序來(lái)說(shuō),有個(gè)沃思公式:算法+數(shù)據(jù)結(jié)構(gòu)=程序。也就是說(shuō)一個(gè)程序主要包含以下兩方面的信息:1、對(duì)數(shù)據(jù)的描述。在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類(lèi)型和數(shù)據(jù)的組織形式。這就是數(shù)據(jù)結(jié)構(gòu)(data structure)。2、對(duì)操作的描述。即要求計(jì)算機(jī)進(jìn)行操作的步驟,也就是算法(algorithm)。
算法當(dāng)然要在有窮步后終止啊,不然計(jì)算機(jī)受得了嗎。。。算法的特性就包含有窮這一條,而且有窮性是指在合理的范圍之內(nèi),你讓一個(gè)算法持續(xù)幾千年,也不合常理。
希望對(duì)你有用。
算法,指解題方案的準(zhǔn)確而完整的描述,是一系列解決問(wèn)題的清晰指令,算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。算法中的指令描述的是一個(gè)計(jì)算,當(dāng)其運(yùn)行時(shí)能從一個(gè)初始狀態(tài)和(可能為空的)初始輸入開(kāi)始,經(jīng)過(guò)一系列有限而清晰定義的狀態(tài),最終產(chǎn)生輸出并停止于一個(gè)終態(tài)。
特征:有窮性,算法必須能在執(zhí)行有限個(gè)步驟之后終止;確切性,算法的每一步驟必須有確切的定義;輸入項(xiàng),一個(gè)算法有0個(gè)或多個(gè)輸入,以刻畫(huà)運(yùn)算對(duì)象初始情況;輸出項(xiàng),一個(gè)算法有一個(gè)或多個(gè)輸出以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果;可行性,算法中執(zhí)行的任何計(jì)算步驟都可被分解為基本的可執(zhí)行的操作步驟。
擴(kuò)展資料:
算法可以宏泛分為三類(lèi):
1、有限的、確定性算法:這類(lèi)算法在有限的一段時(shí)間內(nèi)終止。他們可能要花很長(zhǎng)時(shí)間來(lái)執(zhí)行指定的任務(wù),但仍將在一定的時(shí)間內(nèi)終止。這類(lèi)算法得出的結(jié)果常取決于輸入值。
2、有限的、非確定算法:這類(lèi)算法在有限的時(shí)間內(nèi)終止。然而,對(duì)于一個(gè)(或一些)給定的數(shù)值,算法的結(jié)果并不是唯一的或確定的。
3、無(wú)限的算法:是那些由于沒(méi)有定義終止定義條件,或定義的條件無(wú)法由輸入的數(shù)據(jù)滿(mǎn)足而不終止運(yùn)行的算法。通常,無(wú)限算法的產(chǎn)生是由于未能確定的定義終止條件。
參考資料來(lái)源:百度百科-算法
聲明:本網(wǎng)站尊重并保護(hù)知識(shí)產(chǎn)權(quán),根據(jù)《信息網(wǎng)絡(luò)傳播權(quán)保護(hù)條例》,如果我們轉(zhuǎn)載的作品侵犯了您的權(quán)利,請(qǐng)?jiān)谝粋€(gè)月內(nèi)通知我們,我們會(huì)及時(shí)刪除。
蜀ICP備2020033479號(hào)-4 Copyright ? 2016 學(xué)習(xí)鳥(niǎo). 頁(yè)面生成時(shí)間:1.769秒