第一章算法初步1.算法的概念1、算法定義在數(shù)學(xué)上，現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類(lèi)問(wèn)題是程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完.2.算的點(diǎn)有窮性：一個(gè)算法在執(zhí)行有限個(gè)步驟之后，必須結(jié).確定性：算法的每一個(gè)步驟和次序應(yīng)該是確定.可行性：原則上算法能夠精確地元算，而且人們用筆和紙做有限次即可完.不唯一性：求某一個(gè)問(wèn)題的解法不一定是唯一的，對(duì)于一個(gè)問(wèn)可以有不同的算.輸出：一個(gè)算法有0個(gè)多個(gè)輸入，以刻畫(huà)運(yùn)對(duì)象的初始條.所謂0個(gè)輸是指算法本身已經(jīng)給出了初始條件.輸出：一個(gè)算法有1個(gè)或個(gè)輸出以反映對(duì)輸入數(shù)據(jù)加工的果沒(méi)有輸出的算法是毫無(wú)意義.3．算法的描：自然語(yǔ)言、程序框圖、程序語(yǔ)言。例1、寫(xiě)1×2×3×4×5×6的一算法.解:按照逐一相乘的程序行第一步計(jì)1×2,得到2；第二步將一步的運(yùn)算果2與3相乘得6；第三步將二步的運(yùn)算果6與4相,得24；第四步將三步的運(yùn)算果24與相,得到120；第五步將四的運(yùn)算結(jié)120與6相乘得720；第六步輸結(jié)果/9例2、寫(xiě)按從小到大的順序重新排列

,,

三個(gè)數(shù)值的算法解:（1）.輸入

xy,

三個(gè)數(shù)值；（2）.從三個(gè)數(shù)值中挑出最小者并到中（3）.從

y,z

中挑出最小者并換到

中；（4）.輸出排序的結(jié)果1、程序框圖本概念：（一）程序構(gòu)的概念：程序框圖又稱(chēng)流程圖，是一種用規(guī)的圖形、指向線及文字說(shuō)明來(lái)準(zhǔn)確、直觀地表示算的圖形。一個(gè)程序框圖包括以下幾部分：表示相應(yīng)操作的程序框；帶箭頭的流程線；程序框外必要文字說(shuō)明。（二）構(gòu)成程框的圖形符號(hào)及其作用程框

名稱(chēng)

功能表示一個(gè)算法的起始和束何程圖起止框輸入、輸出框處理框判斷框

不可少的。表示一個(gè)算法輸入和輸?shù)南⒃诜ㄖ腥魏涡枰斎搿⑤數(shù)闹?。賦值、計(jì)算，算法中處數(shù)需的算、公式等分別寫(xiě)在不同的以理?yè)?jù)的處理框內(nèi)。判斷某一條件是否成立時(shí)出口處標(biāo)是立標(biāo)否學(xué)習(xí)這部分知識(shí)的時(shí)候，要掌握各個(gè)圖形的形狀、作用及使用規(guī)則，畫(huà)程序框圖的規(guī)則如下：使用標(biāo)準(zhǔn)的圖形符號(hào)。框圖一般按從上到下、從左到右的方向畫(huà)。除判斷框外，大多數(shù)流程圖符號(hào)只有一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框具有超過(guò)一個(gè)退出點(diǎn)的唯一符號(hào)。判斷框分兩大類(lèi)，一類(lèi)判斷框“是”與“否”兩分支的判斷，而且有且僅有兩個(gè)結(jié)果；另一類(lèi)是多分支判斷，有幾種同的結(jié)果。在圖形符號(hào)內(nèi)描述的語(yǔ)言要非常簡(jiǎn)練清楚。/9開(kāi)始輸入≥0?Yx2

N

yx輸出

結(jié)束（三法三基本邏結(jié)構(gòu)：順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。1步驟n步驟2、條件結(jié)構(gòu)/93、循環(huán)結(jié)構(gòu)：1終止2在循。算……+100/91、輸入語(yǔ)句“提示內(nèi)容量

圖形計(jì)算器格式

“提示內(nèi)容量2、輸出語(yǔ)句提示內(nèi)容達(dá)式

圖形計(jì)算器格式

Disp“提示內(nèi)容量3、賦值語(yǔ)句圖形計(jì)算器變量＝表達(dá)式

格式

表達(dá)式

變量條件語(yǔ)句的一般格式有種）IF—THEN—ELSE語(yǔ)句）IF語(yǔ)。IF—THEN語(yǔ)IF—THEN—ELSE語(yǔ)句一格式為圖1，對(duì)應(yīng)的程序框圖為圖2。IF條件THEN語(yǔ)句語(yǔ)句ENDIF圖1

滿足條件？是語(yǔ)句圖2

否語(yǔ)句23、IF—THEN語(yǔ)句IF—THEN句的一般格式為圖3，對(duì)應(yīng)的程序框圖圖4。IF條件THEN

是語(yǔ)句ENDIF

滿足條件？（圖3

否

語(yǔ)句（圖4/9循環(huán)結(jié)構(gòu)是由循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)的。對(duì)應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般程序設(shè)計(jì)語(yǔ)言中也有當(dāng)型WHILE型）和直到型（UNTIL型）種語(yǔ)句結(jié)構(gòu)。即WHILE語(yǔ)和UNTIL語(yǔ)句。1、WHILE語(yǔ)

循環(huán)

條件WHILE語(yǔ)的一般格是

循環(huán)體

對(duì)應(yīng)的程序框圖是

是WEND

滿足條件？否2、UNTIL語(yǔ)UNTIL語(yǔ)的一般格式是

DO循環(huán)體

對(duì)應(yīng)的程序圖是

循環(huán)UNTIL條件

滿足條件？是

否1、輾轉(zhuǎn)相除與更相減損術(shù)（1轉(zhuǎn)相除法。也叫歐幾里德算法，用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：（1定個(gè)正整數(shù)，n；：計(jì)算m以n所的數(shù)r；：m=n，n=r若r=0則，n的最大公約數(shù)等于m；則，返回第二步。/9f(x)=axf(x)=axn（2相減損術(shù)我國(guó)早期也有求最大公約數(shù)問(wèn)題的算法，就是更相減損術(shù)。在《九章算術(shù)》中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母?子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯為意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。（2較的減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所的最大公約數(shù)。2、秦九韶算與排序1、秦九韶算概念：

n+ax+….+ax+an-110

求值題把個(gè)n次項(xiàng)

f(x)=axnxn-1+….+ax+ann-110

改寫(xiě)成如下式：f(x)=an+axn-1+….+ann-110=(an-1+ax+….+ann-110=((an-2+axn-3+….+ann-1210=......=(...(ax+a)x+a)x+...+a)x+ann-1n-210求多項(xiàng)式的值，首先計(jì)算最內(nèi)層括號(hào)內(nèi)依次多項(xiàng)式的值，即的，即

v=ax+a1nn-1

然由向逐計(jì)一多項(xiàng)式v=v21n-2

v=vx+a3n-3

......v=vx+ann-10這樣，把次多式的求值問(wèn)題轉(zhuǎn)化成求n個(gè)一次多項(xiàng)的值的題。/9例、已知一個(gè)5次多項(xiàng)式為(x)x

0.8.用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x時(shí)值f(x3.5)xvv27;v3.5138.5;v138.5689.9;v3451.2;v3451.20.817255.2.所以，當(dāng)x=5時(shí)，多項(xiàng)式的值等于7255.2.例、例、3、位制概念：進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱(chēng)為基數(shù)，基數(shù)為，即可稱(chēng)n進(jìn)制，簡(jiǎn)稱(chēng)n進(jìn)?，F(xiàn)在常用的是十制通使用10個(gè)拉伯?dāng)?shù)字0-9進(jìn)記數(shù)。對(duì)于任何一個(gè)數(shù)，我們可以用不同的進(jìn)位制來(lái)表示。比如：十進(jìn)，以用二進(jìn)制表示為111001，也可以用八進(jìn)制表示為、十六進(jìn)制表示為39，它們所代表的數(shù)值都是一的。一般地若k是個(gè)大于一的整數(shù)那以k為數(shù)的k進(jìn)可表為aaaa)

,...,,

，而表示各種進(jìn)位制數(shù)一般在數(shù)字右下腳加注來(lái)表,如111001表二進(jìn)制數(shù),34表5進(jìn)數(shù)