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

,,

三個數值的算法解:（1）.輸入

xy,

三個數值；（2）.從三個數值中挑出最小者并到中（3）.從

y,z

中挑出最小者并換到

中；（4）.輸出排序的結果1、程序框圖本概念：（一）程序構的概念：程序框圖又稱流程圖，是一種用規的圖形、指向線及文字說明來準確、直觀地表示算的圖形。一個程序框圖包括以下幾部分：表示相應操作的程序框；帶箭頭的流程線；程序框外必要文字說明。（二）構成程框的圖形符號及其作用程框

名稱

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

不可少的。表示一個算法輸入和輸的息在法中任何需要輸入、輸的置。賦值、計算，算法中處數需的算、公式等分別寫在不同的以理據的處理框內。判斷某一條件是否成立時出口處標是立標否學習這部分知識的時候，要掌握各個圖形的形狀、作用及使用規則，畫程序框圖的規則如下：使用標準的圖形符號。框圖一般按從上到下、從左到右的方向畫。除判斷框外，大多數流程圖符號只有一個進入點和一個退出點。判斷框具有超過一個退出點的唯一符號。判斷框分兩大類，一類判斷框“是”與“否”兩分支的判斷，而且有且僅有兩個結果；另一類是多分支判斷，有幾種同的結果。在圖形符號內描述的語言要非常簡練清楚。/9開始輸入≥0?Yx2

N

yx輸出

結束（三法三基本邏結構：順序結構、條件結構、循環結構。1步驟n步驟2、條件結構/93、循環結構：1終止2在循。算……+100/91、輸入語句“提示內容量

圖形計算器格式

“提示內容量2、輸出語句提示內容達式

圖形計算器格式

Disp“提示內容量3、賦值語句圖形計算器變量＝表達式

格式

表達式

變量條件語句的一般格式有種）IF—THEN—ELSE語句）IF語。IF—THEN語IF—THEN—ELSE語句一格式為圖1，對應的程序框圖為圖2。IF條件THEN語句語句ENDIF圖1

滿足條件？是語句圖2

否語句23、IF—THEN語句IF—THEN句的一般格式為圖3，對應的程序框圖圖4。IF條件THEN

是語句ENDIF

滿足條件？（圖3

否

語句（圖4/9循環結構是由循環語句來實現的。對應于程序框圖中的兩種循環結構，一般程序設計語言中也有當型WHILE型）和直到型（UNTIL型）種語句結構。即WHILE語和UNTIL語句。1、WHILE語

循環

條件WHILE語的一般格是

循環體

對應的程序框圖是

是WEND

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

DO循環體

對應的程序圖是

循環UNTIL條件

滿足條件？是

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

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

求值題把個n次項

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

改寫成如下式：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求多項式的值，首先計算最內層括號內依次多項式的值，即的，即

v=ax+a1nn-1

然由向逐計一多項式v=v21n-2

v=vx+a3n-3

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

0.8.用秦九韶算法求這個多項式當x時值f(x3.5)xvv27;v3.5138.5;v138.5689.9;v3451.2;v3451.20.817255.2.所以，當x=5時，多項式的值等于7255.2.例、例、3、位制概念：進位制是一種記數方式，用有限的數字在不同的位置表示不同的數值。可使用數字符號的個數稱為基數，基數為，即可稱n進制，簡稱n進。現在常用的是十制通使用10個拉伯數字0-9進記數。對于任何一個數，我們可以用不同的進位制來表示。比如：十進，以用二進制表示為111001，也可以用八進制表示為、十六進制表示為39，它們所代表的數值都是一的。一般地若k是個大于一的整數那以k為數的k進可表為aaaa)

,...,,

，而表示各種進位制數一般在數字右下腳加注來表,如111001表二進制數,34表5進數