91欧美在线免费观看,漂亮的人妻中文字幕,国产精品免费在线观看视频,男女一起插插插视频,四虎国产精品久久久久,人妻精品有码一区二区三区,亚洲 欧美 你懂的,亚洲制服一区二区三区在线,高中女厕偷拍一区二区三区

數(shù)學(xué)技術(shù)之算法概論篇（1）

1.算法概述

計(jì)算機(jī)算法是在計(jì)算機(jī)上有限步內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則或?qū)忸}步驟的精確描述，通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程，即以一步接一步的方式詳細(xì)描述計(jì)算機(jī)如何將輸入轉(zhuǎn)化為所要求的輸出的過(guò)程，下面簡(jiǎn)稱(chēng)其為算法。在這個(gè)過(guò)程中，無(wú)論是形成解題公式還是編寫(xiě)程序，都是實(shí)施某種算法，前者利用推理實(shí)現(xiàn)算法，后者通過(guò)計(jì)算機(jī)操作實(shí)現(xiàn)算法。
計(jì)算機(jī)算法的基本特征可概括為：
①？ 正確性：對(duì)于任意一組輸入，包括合理的輸入與不合理的輸入，總能得到預(yù)期的輸出；如果一個(gè)算法只是對(duì)合理的輸入才能得到預(yù)期的輸出，而在異常情況下卻無(wú)法預(yù)料輸出的結(jié)果，那它就是不正確的；
②？ 確切性：算法的每一步必須有確切的定義，無(wú)二義性；
③？ 可行性：算法是由一系列具體步驟組成的，每一步都能夠準(zhǔn)確運(yùn)行，有確定的執(zhí)行順序；
④？ 有窮性：算法必須保證經(jīng)有限步運(yùn)行之后結(jié)束，即算法的步驟必須是有限的。在任何情況下，算法都不能陷入無(wú)限循環(huán)中；
⑤？ 輸？ 入：算法有一個(gè)或多個(gè)輸入，表示運(yùn)算對(duì)象的初始條件；
⑥？ 輸？ 出：算法有一個(gè)或多個(gè)輸出，反映運(yùn)算的最終結(jié)果。
描述算法的方法有多種，常用的有自然語(yǔ)言、結(jié)構(gòu)化流程圖、偽代碼和PAD圖（Problem Analysis Diagram）等，其中最普遍的是流程圖。雖然算法與計(jì)算機(jī)程序密切相關(guān)，但二者還是不同的，計(jì)算機(jī)程序是算法的一個(gè)實(shí)例，是將算法通過(guò)某種計(jì)算機(jī)語(yǔ)言表達(dá)出來(lái)的具體形式；同一個(gè)算法可以用不同的計(jì)算機(jī)語(yǔ)言來(lái)表達(dá)。
對(duì)同一個(gè)計(jì)算問(wèn)題，不同人會(huì)用選用不同的算法，而不同的算法使得計(jì)算機(jī)的運(yùn)行效率、解題精度和對(duì)計(jì)算資源的需求會(huì)有一定的差異。在實(shí)際問(wèn)題中遇到的高難度計(jì)算問(wèn)題，有的問(wèn)題在巨型計(jì)算機(jī)上用普通算法求解可能要用數(shù)天時(shí)間，甚至也難以找到可用的解，但用一個(gè)好的算法，即使在普通的微機(jī)上，只用幾分鐘就可以找到滿(mǎn)意的解。因此，用計(jì)算機(jī)求解一個(gè)實(shí)際問(wèn)題的計(jì)算速度和結(jié)果滿(mǎn)意度不僅僅與計(jì)算機(jī)設(shè)備的水平有關(guān)，更取決于求解該問(wèn)題算法水平的高低和對(duì)問(wèn)題的適應(yīng)性，由此可見(jiàn)算法的重要性。算法研究的重點(diǎn)隨問(wèn)題的不同而異，主要有算法設(shè)計(jì)和分析、計(jì)算復(fù)雜性和新的高效算法設(shè)計(jì)與研究等。
對(duì)一個(gè)給定問(wèn)題的算法要進(jìn)行設(shè)計(jì)和分析。算法設(shè)計(jì)，就是對(duì)一個(gè)給定問(wèn)題設(shè)計(jì)出良好的算法，并研究設(shè)計(jì)算法的規(guī)律及其有關(guān)的方法；算法分析，就是對(duì)一個(gè)給定問(wèn)題設(shè)計(jì)出來(lái)的算法，利用數(shù)學(xué)工具，研究該算法對(duì)問(wèn)題的適應(yīng)性和算法的穩(wěn)定性、收斂性、復(fù)雜性和誤差問(wèn)題等。
評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)有：
①時(shí)間復(fù)雜度：同樣的問(wèn)題規(guī)模需花費(fèi)多少時(shí)間；
②空間復(fù)雜度：同樣的問(wèn)題規(guī)模需花費(fèi)多少空間（主要是內(nèi)存）；
以上兩點(diǎn)越小越好
③穩(wěn)定性：不會(huì)因?yàn)檩斎肷杂胁煌鴮?dǎo)致計(jì)算結(jié)果不穩(wěn)定的情況發(fā)生；
④算法思路是否簡(jiǎn)單：越簡(jiǎn)單越容易實(shí)現(xiàn)越好，最好有現(xiàn)成軟件系統(tǒng)可用。
算法復(fù)雜度是對(duì)算法在計(jì)算機(jī)上運(yùn)行時(shí)所需要的計(jì)算機(jī)資源的度量，需要的時(shí)間資源量（如計(jì)算所需的步數(shù)或反復(fù)執(zhí)行指令的條數(shù)）稱(chēng)作時(shí)間復(fù)雜度，需要的空間資源量（即需占用存儲(chǔ)空間的大?。┓Q(chēng)作空間復(fù)雜度，是對(duì)算法效率的度量和評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。這些量應(yīng)該集中反映算法中所采用方法的效率，而從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來(lái)。換句話(huà)說(shuō)，這些量應(yīng)只依賴(lài)于算法要解的問(wèn)題的規(guī)模、算法的輸入、輸出和算法本身。
計(jì)算機(jī)和數(shù)學(xué)技術(shù)的快速發(fā)展，近些年來(lái)出現(xiàn)了許多新算法。它們技巧性強(qiáng)，在時(shí)間復(fù)雜度、空間復(fù)雜度和計(jì)算精度等方面各占一定優(yōu)勢(shì)，應(yīng)用廣泛，效果顯著。
算法對(duì)我們真有那么重要嗎？現(xiàn)在，這些看不見(jiàn)、摸不著的算法正在掌控著我們與數(shù)字世界的互動(dòng)，從谷歌網(wǎng)站上推薦圖書(shū)、電影和音樂(lè)的算法到Facebook網(wǎng)站上推薦朋友的算法，從操縱華爾街股票交易的算法再到各種搜索引擎的算法及好萊塢預(yù)測(cè)電影票房的算法，算法似乎已無(wú)聲地滲入到我們的世界并重塑著我們身處的世界。有專(zhuān)家指出：計(jì)算機(jī)用來(lái)做決定的算法正在以“隨風(fēng)潛入夜，潤(rùn)物細(xì)無(wú)聲”的方式，慢慢滲透進(jìn)我們?nèi)粘Ｉ畹姆椒矫婷?。這些看不見(jiàn)摸不著的算法正在慢慢掌控著我們與電子世界的相互交流，現(xiàn)在是一個(gè)“算法為王”的時(shí)代。隨著算法開(kāi)始將其影響力延伸并塑造我們身處的世界，現(xiàn)在已經(jīng)到了我們必須透徹地了解算法的時(shí)候了。

2.計(jì)算機(jī)里的數(shù)及其計(jì)算

數(shù)學(xué)應(yīng)用、應(yīng)用數(shù)學(xué)，數(shù)學(xué)計(jì)算、計(jì)算數(shù)學(xué)，數(shù)學(xué)技術(shù)、技術(shù)數(shù)學(xué)，粗看起來(lái)，它們都和數(shù)學(xué)密切相連，都是以數(shù)學(xué)為工具，解決現(xiàn)實(shí)世界中遇到的各種各樣實(shí)際中遇到的問(wèn)題；細(xì)分起來(lái)，在發(fā)展過(guò)程、研究方向、考慮問(wèn)題的重點(diǎn)和評(píng)價(jià)優(yōu)劣的標(biāo)準(zhǔn)等方面確有不少差異。但不管怎么說(shuō)，以數(shù)學(xué)為思維的方法，研究的工具，把實(shí)際問(wèn)題經(jīng)抽象處理，構(gòu)建可用的數(shù)學(xué)模型，研究其中用到的各類(lèi)算法，編制成在計(jì)算機(jī)上可運(yùn)行的程序，通過(guò)計(jì)算機(jī)上的實(shí)際計(jì)算和計(jì)算結(jié)果的分析處理，解決遇到的實(shí)際問(wèn)題，這些都是它們應(yīng)含有的思想和實(shí)際應(yīng)用中要處理的問(wèn)題。
說(shuō)到計(jì)算機(jī)，就像顯微鏡對(duì)醫(yī)學(xué)、望遠(yuǎn)鏡對(duì)天文學(xué)一樣，是數(shù)學(xué)應(yīng)用、數(shù)學(xué)計(jì)算、數(shù)學(xué)技術(shù)中不可缺少的設(shè)備，時(shí)時(shí)、處處都要用到計(jì)算機(jī)，有的還要用到巨型計(jì)算機(jī)。計(jì)算機(jī)使數(shù)學(xué)原理得以實(shí)現(xiàn)，為數(shù)學(xué)應(yīng)用開(kāi)辟了無(wú)限廣闊的天地；計(jì)算機(jī)是具體化了的數(shù)學(xué)，現(xiàn)代數(shù)學(xué)的實(shí)驗(yàn)室，進(jìn)行現(xiàn)代數(shù)學(xué)研究和實(shí)際應(yīng)用時(shí)必不可少的工具。這里只能掛一漏萬(wàn)，介紹一下計(jì)算機(jī)上數(shù)據(jù)的表示、數(shù)學(xué)運(yùn)算及其誤差和幾個(gè)簡(jiǎn)單的算例。
① 計(jì)算機(jī)里的數(shù)據(jù)
數(shù)據(jù)（Data）是信息的載體，是計(jì)算機(jī)加工處理的對(duì)象，描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。它是計(jì)算機(jī)程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計(jì)算機(jī)里的數(shù)據(jù)可以是數(shù)值型數(shù)據(jù)，也可以是非數(shù)值型數(shù)據(jù)。數(shù)值型數(shù)據(jù)是一些整數(shù)、實(shí)數(shù)或復(fù)數(shù)，主要用于工程計(jì)算、科學(xué)計(jì)算和商務(wù)處理等；非數(shù)值型數(shù)據(jù)包括字符、文字、圖表、圖形、圖像、語(yǔ)音等。數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位。
計(jì)算機(jī)中，以位（0或1）表示數(shù)據(jù)。數(shù)據(jù)的最小的尋址單位稱(chēng)為字節(jié)（通常是八位），機(jī)器碼指令處理的單位，稱(chēng)作字長(zhǎng)。大部分對(duì)字長(zhǎng)的指令解譯，主要以二進(jìn)制為主，如一個(gè)32位的字長(zhǎng)，可以表示從0至2³²-1的無(wú)符號(hào)整數(shù)值，或者表示從-(2³²-1)至(2³²-1)有符號(hào)整數(shù)值。存在著特殊的算術(shù)指令，對(duì)字長(zhǎng)中的位使用不同的解釋?zhuān)源俗鳛楦↑c(diǎn)數(shù)。
數(shù)據(jù)類(lèi)型(Data type)是用來(lái)約束數(shù)據(jù)的解釋?zhuān)泻芏喾N，最簡(jiǎn)單的就是數(shù)字。數(shù)據(jù)也可以是文字、圖像、聲音等，可用于科學(xué)研究、設(shè)計(jì)、查證等。在編程語(yǔ)言中，常見(jiàn)的數(shù)據(jù)類(lèi)型包括原始類(lèi)型（如：整數(shù)、浮點(diǎn)數(shù)或字符）、多元組、記錄單元、代數(shù)數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型、參考類(lèi)型、類(lèi)別以及函數(shù)型等。數(shù)據(jù)類(lèi)型描述了數(shù)值的表示法、解釋和結(jié)構(gòu)，并以算法操作，或是物件在內(nèi)存中的儲(chǔ)存區(qū)，或者其它儲(chǔ)存裝置，隨不同的計(jì)算機(jī)語(yǔ)言系統(tǒng)會(huì)有所不同。
數(shù)據(jù)在計(jì)算機(jī)里的基本運(yùn)算和操作有如下四類(lèi)：
1.算術(shù)運(yùn)算：加減乘除等運(yùn)算；
2.邏輯運(yùn)算：或、且、非等運(yùn)算；
3.關(guān)系運(yùn)算：大于、小于、等于、不等于等運(yùn)算；
4.數(shù)據(jù)傳輸：輸入、輸出、賦值等運(yùn)算。
② 數(shù)值計(jì)算
用計(jì)算機(jī)高級(jí)語(yǔ)言研制的程序，大都含有數(shù)值計(jì)算；因此，在計(jì)算機(jī)應(yīng)用中，進(jìn)行數(shù)值計(jì)算是其最重要的功能之一。計(jì)算機(jī)語(yǔ)言中的數(shù)值表示及其運(yùn)算和數(shù)學(xué)中的數(shù)值與運(yùn)算有所不同，對(duì)此要有明確的認(rèn)識(shí)和嚴(yán)格的區(qū)分，并在計(jì)算機(jī)上實(shí)施實(shí)際計(jì)算中給予足夠的重視和進(jìn)行細(xì)致的分析。在計(jì)算機(jī)各種不同的編程語(yǔ)言中，數(shù)值計(jì)算多采用32位（4字節(jié)）的單字長(zhǎng)或64位（8字節(jié)）的雙字長(zhǎng)作為一個(gè)數(shù)存單元，每一個(gè)數(shù)值都存放在計(jì)算機(jī)里數(shù)存的一個(gè)單元中。數(shù)值的大小和數(shù)值的精度都受到一定限制。
受計(jì)算機(jī)字長(zhǎng)的限制，輸入到計(jì)算機(jī)里的數(shù)會(huì)有原始誤差和舍入誤差，經(jīng)計(jì)算得到結(jié)果的數(shù)含有運(yùn)算誤差、傳遞誤差和累積誤差，計(jì)算公式進(jìn)過(guò)簡(jiǎn)化、離散、近似逼近等處理也會(huì)出現(xiàn)誤差。在計(jì)算機(jī)億萬(wàn)次計(jì)算過(guò)程中，誤差的積累和傳遞是紙上手工計(jì)算中無(wú)法體會(huì)和了解的，兩者有很大不同，甚至在數(shù)學(xué)上成立的恒等式，在計(jì)算機(jī)上實(shí)施計(jì)算的過(guò)程中也會(huì)產(chǎn)生異化而不再成立。
這里將對(duì)上述問(wèn)題及應(yīng)注意的一些事項(xiàng)進(jìn)行一些簡(jiǎn)單扼要介紹。
從我們接受基礎(chǔ)教育開(kāi)始到中學(xué)學(xué)習(xí)結(jié)束，接觸到的數(shù)多是數(shù)學(xué)中的數(shù)，像小學(xué)中的自然數(shù)、小數(shù)、分?jǐn)?shù)，中學(xué)時(shí)的負(fù)數(shù)、無(wú)理數(shù)、實(shí)數(shù)、復(fù)數(shù)等等，如53、123.618、2/3、-35.4、√2、3+10i（這里，i= √-1，為虛數(shù)單位）等，用來(lái)表示一個(gè)明確的數(shù)；代數(shù)中，更是用英文字母表示非常廣義的數(shù)，如向量、矩陣等。但在計(jì)算機(jī)上和計(jì)算機(jī)語(yǔ)言中表示的數(shù)和運(yùn)算，和數(shù)學(xué)中的數(shù)和運(yùn)算卻有所不同，即計(jì)算機(jī)上計(jì)算公式里的運(yùn)算必須是計(jì)算機(jī)上可實(shí)際執(zhí)行的運(yùn)算，參與運(yùn)算的數(shù)是有限小數(shù)或整數(shù)，并有一定的表示格式。
在計(jì)算機(jī)內(nèi)，所有的數(shù)均用二進(jìn)制表示，優(yōu)點(diǎn)在于表示容易、物理實(shí)現(xiàn)簡(jiǎn)單、節(jié)省設(shè)備、代數(shù)運(yùn)算簡(jiǎn)單可靠、邏輯運(yùn)算方便。在計(jì)算機(jī)里，除二進(jìn)制數(shù)（用B表示）外、還有八進(jìn)制數(shù)（用O表示）、十進(jìn)制數(shù)（用D表示）、十六進(jìn)制數(shù)（用H表示）和二/十進(jìn)制數(shù)（全名為“二進(jìn)制編碼的十進(jìn)制數(shù)”，用BCD表示）等。
計(jì)算機(jī)上的數(shù)，用二進(jìn)制的一位數(shù)碼表示數(shù)的符號(hào)，稱(chēng)為“數(shù)符”，且用“0”表示正數(shù)，“1”表示負(fù)數(shù)。小數(shù)點(diǎn)的位置隱含表示，以節(jié)省存儲(chǔ)空間。隱含的小數(shù)點(diǎn)位置有固定和可變兩種，分別稱(chēng)為定點(diǎn)數(shù)和浮點(diǎn)數(shù)。
1.定點(diǎn)數(shù)表示法
定點(diǎn)整數(shù)：最高二進(jìn)制的一位數(shù)碼表示數(shù)的符號(hào)，小數(shù)點(diǎn)位置約定在最低數(shù)值位的后面，用于表示整數(shù)。
定點(diǎn)小數(shù)：最高二進(jìn)制的一位數(shù)碼表示數(shù)的符號(hào)，小數(shù)點(diǎn)位置約定在符號(hào)位的后面，用于表示絕對(duì)值小于1的有限位小數(shù)。
2.浮點(diǎn)數(shù)表示法

階符：位于左側(cè)最高位二進(jìn)制的一位數(shù)字，表示階碼的符號(hào)；
階碼：表示指數(shù)部分，階碼的位數(shù)決定數(shù)的范圍；
數(shù)符：二進(jìn)制的一位數(shù)字，表示數(shù)的符號(hào)；
尾數(shù)：小于1的小數(shù)，尾數(shù)的位數(shù)（長(zhǎng)度）決定數(shù)的精度。
在計(jì)算機(jī)語(yǔ)言中，把數(shù)分為實(shí)型數(shù)和復(fù)型數(shù)兩大類(lèi)，分別和數(shù)學(xué)中的實(shí)數(shù)和復(fù)數(shù)相對(duì)應(yīng)。在實(shí)型數(shù)中，又有整型數(shù)、定點(diǎn)數(shù)和浮點(diǎn)數(shù)之分，其中整型數(shù)相當(dāng)于數(shù)學(xué)中的整數(shù)，定點(diǎn)數(shù)相當(dāng)于數(shù)學(xué)中的小數(shù)，浮點(diǎn)數(shù)又稱(chēng)作指數(shù)記數(shù)法，相當(dāng)于數(shù)學(xué)中的科學(xué)計(jì)數(shù)法，不同只在于表示方法，例如，數(shù)學(xué)中的-79*10⁵，在計(jì)算機(jī)上用浮點(diǎn)數(shù)表示為-0.79E7，其中-0.79為其尾數(shù)部分，E7為代表10⁷的指數(shù)部分。那么像√2 ，2/3等無(wú)理數(shù)、分?jǐn)?shù)，在計(jì)算機(jī)及其語(yǔ)言中，又表示成什么樣子呢？
在BASIC語(yǔ)言中，有一個(gè)計(jì)算平方根的函數(shù)SQR（X），和數(shù)學(xué)中的√X起同樣作用，都是求X的平方根，如2的平方根SQR（2）=√2 ，只是SQR（X）被稱(chēng)作函數(shù)，受計(jì)算機(jī)字長(zhǎng)的限制，不再是無(wú)理數(shù)，而是一個(gè)有限字長(zhǎng)的浮點(diǎn)數(shù)，取為√2 的近似值；像2/3，在BASIC語(yǔ)言中，稱(chēng)作表達(dá)式，所得的是分子除以分母后所得的結(jié)果，只是為了計(jì)算機(jī)方便和清晰明了采用2/3這種表示方法。在計(jì)算機(jī)上使用的2/3，實(shí)際上是2除以3后的用有限字長(zhǎng)表示的2/3的近似值。
此外，在計(jì)算機(jī)語(yǔ)言中，數(shù)的大小有著明確規(guī)定的范圍。如在BASIC語(yǔ)言中，數(shù)的絕對(duì)值取值范圍為[2.938736*10^-39，1.701412*10³⁸]；絕對(duì)值低于2.938736*10^-39，計(jì)算機(jī)判為0，稱(chēng)作下溢為0；超過(guò)上限1.701412*10³⁸，計(jì)算機(jī)將顯示出錯(cuò)信息，稱(chēng)為上溢出錯(cuò)停機(jī)；而在數(shù)學(xué)當(dāng)中，數(shù)的大小是無(wú)限的，范圍是（-∞，+∞）。
在數(shù)學(xué)中，0.1=1/10，是一個(gè)不存在誤差的小數(shù)；但在計(jì)算機(jī)上，0.1用八進(jìn)制將無(wú)法精確表示，是一個(gè)含有誤差的數(shù)。
計(jì)算機(jī)中的復(fù)數(shù)，把實(shí)部和虛部分開(kāi)存放，通過(guò)內(nèi)部子程序?qū)崿F(xiàn)復(fù)數(shù)各種不同類(lèi)型的運(yùn)算。