第一章 算法初步
1.1 算法與程序圖框
1. 算法的含義：在數學中，主要研究計算機能實現的算法，即按照某種機械程序步驟一定可以得到結果的解決問題的程序。比如解方程的算法、函數求值的算法、作圖的算法，等等。
2. 例子：
1例1 任意給定一個大于1的整數n，試設計一個程序或步驟對n是否為質數做出判定。
算法分析：根據質數的定義，很容易設計出下面的步驟：
第一步：判斷n是否等于2，若n=2，則n是質數；若n>2，則執(zhí)行第二步。
第二步：依次從2至（n-1）檢驗是不是n的因數，即整除n的數，若有這樣的數，則n不是質數；若沒有這樣的數，則n是質數。
這是判斷一個大于1的整數n是否為質數的最基本算法。
2例2 用二分法設計一個求議程x–2=0的近似根的算法。
算法分析：回顧二分法解方程的過程，并假設所求近似根與準確解的差的絕對值不超過0.005，則不難設計出以下步驟：
2第一步：令f(x)=x–2。因為f(1)<0，f(2)>0，所以設x1=1，x2=2。
第二步：令m=(x1+x2)/2，判斷f(m)是否為0，若則，則m為所長；若否，則繼續(xù)判斷f(x1)·f(m)大于0還是小于0。
第三步：若f(x1)·f(m)>0，則令x1=m；否則，令x2=m。
第四步：判斷|x1–x2|<0.005是否成立？若是，則x1、x2之間的任意取值均為滿足條件的近似根；若否，則返回第二步。
例3 寫出解二元一次方程組 的算法
2x+y=1②
解：第一步，②-①×2得5y=3；③
第二步，解③得y=3/5；
第三步，將y=3/5代入①，得x=1/5
學生做一做：對于一般的二元一次方程組來說，上述步驟應該怎樣進一步完善？ 老師評一評：本題的算法是由加減消元法求解的，這個算法也適合一般的二元一次方
A1xB1yC10(A1B2B1A20)的解的算法： 程組的解法。下面寫出求方程組AxByC0222
第一步：②×A1-①×A2，得(A1B2-A2B1)y+A1C2-A2C1=0；③ 第二步：解③，得yA2C1A2C2； A1B2A2B1
第三步：將yA2C1A2C2B2C1B1C2代入①，得x。 A1B2A2B1A1B2A2B1
此時我們得到了二元一次方程組的求解公式，利用此公司可得到倒2的另一個算法： 第一步：取A1=1，B1=-2，C1=1，A2=2，B2=1，C2=-1；第二步：計算xB2C1B1C2ACA2C2與y21 A1B2A2B1A1B2A2B1
第三步：輸出運算結果。
可見利用上述算法，更加有利于上機執(zhí)行與操作。
基礎知識應用題
例4 寫出一個求有限整數列中的值的算法。
解：算法如下。
S1 先假定序列中的第一個整數為“值”。
S2 將序列中的下一個整數值與“值”比較，如果它大于此“值”，這時你就假定“值”是這個整數。
S3 如果序列中還有其他整數，重復S2。
S4 在序列中一直到沒有可比的數為止，這時假定的“值”就是這個序列中的值。
學生做一做 寫出對任意3個整數a,b,c求出值的算法。
老師評一評 在例2中我們是用自然語言來描述算法的，下面我們用數學語言來描述本題的算法。
S1 max=a
S2 如果b>max, 則max=b.
S3 如果C>max, 則max=c.
S4 max就是a,b,c中的值。
綜合應用題
例5 寫出求1+2+3+4+5+6的一個算法。
分析：可以按逐一相加的程序進行，也可以利用公式1+2+„+n=
根據加法運算律簡化運算過程。
解：算法1：
S1：計算1+2得到3；
S2：將第一步中的運算結果3與3相加得到6；
S3：將第二步中的運算結果6與4相加得到10；
S4：將第三步中的運算結果10與5相加得到15；
S5：將第四步中的運算結果15與6相加得到21。
算法2：
S1：取n=6；
S2：計算n(n1)進行，也可以2n(n1)； 2
S3：輸出運算結果。
算法3：
S1：將原式變形為(1+6)+(2+5)+(3+4)=3×7；
S2：計算3×7；
S3：輸出運算結果。
小結：算法1是最原始的方法，最為繁瑣，步驟較多，當加數較大時，比如1+2+3+„+10000，再用這種方法是行不通的；算法2與算法3都是比較簡單的算法，但比較而言，算法2最為簡單，且易于在計算機上執(zhí)行操作。
學生做一做 求1×3×5×7×9×11的值，寫出其算法。
老師評一評 算法1；第一步，先求1×3，得到結果3；
第二步，將第一步所得結果3再乘以5，得到結果15；
第三步，再將15乘以7，得到結果105；
第四步，再將105乘以9，得到945；
第五步，再將945乘以11，得到10395，即是最后結果。
算法2：用P表示被乘數，i表示乘數。
S1 使P=1。
S2 使i=3
S3 使P=P×i
S4 使i=i+2
S5 若i≤11，則返回到S3繼續(xù)執(zhí)行；否則算法結束。
1、寫出解一元二次方程ax2+bx+c=0(a≠0)的一個算法。
2、寫出求1至1000的正數中的3倍數的一個算法（打印結果）
1、解：算法如下
2S1 計算△=b-4ac
S2 如果△〈0，則方程無解；否則x1=
S3 輸出計算結果x1，x2或無解信息。
2、解：算法如下：
S1 使i=1
S2 i被3除，得余數r
S3 如果r=0，則打印i，否則不打印
S4 使i=i+1
S5 若i≤1000,則返回到S2繼續(xù)執(zhí)行，否則算法結束。
21、寫出解不等式x-2x-3<0的一個算法。
2解：第一步：x-2x-3=0的兩根是x1=3，x2=-1。
2第二步：由x-2x-3<0可知不等式的解集為{x | -1 2評注：該題的解法具有一般性，下面給出形如ax+bx+c>0的不等式的解的步驟（為方
便，我們設a>0）如下：
第一步：計算△= b4ac； 2
第二步：若△>0，示出方程兩根x1,2
{x | x>x1或xx2），則不等式解集為2a
b}； 2a第三步：若△= 0，則不等式解集為{x | x∈R且x
第四步：若△<0，則不等式的解集為R。
2、求過P(a1,b1)、Q(a2,b2)兩點的直線斜率有如下的算法：
第一步：取x1= a1，y1= b1，x2= a2，y1= b2；
第二步：若x1= x2；第三步：輸出斜率不存在；
第四步：若x1≠x2； 第五步：計算ky2y1； x2x1
第六步：輸出結果。
3、寫出求過兩點M(-2,-1)、N(2,3)的直線與坐標軸圍成面積的一個算法。
解：算法：第一步：取x1=-2，y1=-1，x2=2，y2=3； 第二步：計算yy1xx1； y2y1x2x1
第三步：在第二步結果中令x=0得到y的值m，得直線與y軸交點(0,m)；
第四步：在第二步結果中令y=0得到x的值n，得直線與x軸交點(n,0)；
第五步：計算S=1|m||n|； 2
第六步：輸出運算結果
3. 程序框圖的概念：是一種用規(guī)定的圖形，指向線及文字說明來準確、直觀地表示算法的
圖形。
4. 基本概念：
（1）起止框圖：
起止框是任何流程圖都不可缺少的，它表明程序的開始和結束，所以一個完整的流程圖的首末兩端必須是起止框。
（2表示數據的輸入或結果的輸出，它可用在算法中的任何需要輸入、輸出的位置。圖1-1中有三個輸入、輸出框。第一個出現在開始后的第一步，它的作用是輸入未知數的系數a11,a12,a21,a22和常數項b1,b2,通過這一步，就可以把給定的數值寫在輸入框內，它實際上是把未知數的系數和常數項的值通知給了計算機，另外兩個是輸出框，它們分別位于由判斷分出的兩個分支中，它們表示最后給出的運算結果，左邊分支中的輸出分框負責輸出D≠0時未知數x1,x2的值，右邊分支中的輸出框負責輸出D=0時的結果，即輸出無法求解信息。
（3）處理框：1-1中出現了兩個處理框。第一個處理框的作用是計算D=a11a22-a21a12的值，第二個處理框的作用是計算x1=(b1a22-b2a12)/D,x2=(b2a11-b1a21)/D的值。
（4）判斷框一般有一個入口和兩個出口，有時也有多個出口，它是惟一的具有兩個或兩個以上出口的符號，在只有兩個出口的情形中，通常都分成“是”與“否”（也可用“Y”與“N”）兩個分支，在圖1-1中，通過判斷框對D的值進行判斷，若判斷框中的式子是D=0，則說明D=0時由標有“是”的分支處理數據；若D≠0，則由標有“否”的分支處理數據。例如，我們要打印x的絕對值，可以設計如下框圖。
1.1 算法與程序圖框
1. 算法的含義：在數學中，主要研究計算機能實現的算法，即按照某種機械程序步驟一定可以得到結果的解決問題的程序。比如解方程的算法、函數求值的算法、作圖的算法，等等。
2. 例子：
1例1 任意給定一個大于1的整數n，試設計一個程序或步驟對n是否為質數做出判定。
算法分析：根據質數的定義，很容易設計出下面的步驟：
第一步：判斷n是否等于2，若n=2，則n是質數；若n>2，則執(zhí)行第二步。
第二步：依次從2至（n-1）檢驗是不是n的因數，即整除n的數，若有這樣的數，則n不是質數；若沒有這樣的數，則n是質數。
這是判斷一個大于1的整數n是否為質數的最基本算法。
2例2 用二分法設計一個求議程x–2=0的近似根的算法。
算法分析：回顧二分法解方程的過程，并假設所求近似根與準確解的差的絕對值不超過0.005，則不難設計出以下步驟：
2第一步：令f(x)=x–2。因為f(1)<0，f(2)>0，所以設x1=1，x2=2。
第二步：令m=(x1+x2)/2，判斷f(m)是否為0，若則，則m為所長；若否，則繼續(xù)判斷f(x1)·f(m)大于0還是小于0。
第三步：若f(x1)·f(m)>0，則令x1=m；否則，令x2=m。
第四步：判斷|x1–x2|<0.005是否成立？若是，則x1、x2之間的任意取值均為滿足條件的近似根；若否，則返回第二步。
例3 寫出解二元一次方程組 的算法
2x+y=1②
解：第一步，②-①×2得5y=3；③
第二步，解③得y=3/5；
第三步，將y=3/5代入①，得x=1/5
學生做一做：對于一般的二元一次方程組來說，上述步驟應該怎樣進一步完善？ 老師評一評：本題的算法是由加減消元法求解的，這個算法也適合一般的二元一次方
A1xB1yC10(A1B2B1A20)的解的算法： 程組的解法。下面寫出求方程組AxByC0222
第一步：②×A1-①×A2，得(A1B2-A2B1)y+A1C2-A2C1=0；③ 第二步：解③，得yA2C1A2C2； A1B2A2B1
第三步：將yA2C1A2C2B2C1B1C2代入①，得x。 A1B2A2B1A1B2A2B1
此時我們得到了二元一次方程組的求解公式，利用此公司可得到倒2的另一個算法： 第一步：取A1=1，B1=-2，C1=1，A2=2，B2=1，C2=-1；第二步：計算xB2C1B1C2ACA2C2與y21 A1B2A2B1A1B2A2B1
第三步：輸出運算結果。
可見利用上述算法，更加有利于上機執(zhí)行與操作。
基礎知識應用題
例4 寫出一個求有限整數列中的值的算法。
解：算法如下。
S1 先假定序列中的第一個整數為“值”。
S2 將序列中的下一個整數值與“值”比較，如果它大于此“值”，這時你就假定“值”是這個整數。
S3 如果序列中還有其他整數，重復S2。
S4 在序列中一直到沒有可比的數為止，這時假定的“值”就是這個序列中的值。
學生做一做 寫出對任意3個整數a,b,c求出值的算法。
老師評一評 在例2中我們是用自然語言來描述算法的，下面我們用數學語言來描述本題的算法。
S1 max=a
S2 如果b>max, 則max=b.
S3 如果C>max, 則max=c.
S4 max就是a,b,c中的值。
綜合應用題
例5 寫出求1+2+3+4+5+6的一個算法。
分析：可以按逐一相加的程序進行，也可以利用公式1+2+„+n=
根據加法運算律簡化運算過程。
解：算法1：
S1：計算1+2得到3；
S2：將第一步中的運算結果3與3相加得到6；
S3：將第二步中的運算結果6與4相加得到10；
S4：將第三步中的運算結果10與5相加得到15；
S5：將第四步中的運算結果15與6相加得到21。
算法2：
S1：取n=6；
S2：計算n(n1)進行，也可以2n(n1)； 2
S3：輸出運算結果。
算法3：
S1：將原式變形為(1+6)+(2+5)+(3+4)=3×7；
S2：計算3×7；
S3：輸出運算結果。
小結：算法1是最原始的方法，最為繁瑣，步驟較多，當加數較大時，比如1+2+3+„+10000，再用這種方法是行不通的；算法2與算法3都是比較簡單的算法，但比較而言，算法2最為簡單，且易于在計算機上執(zhí)行操作。
學生做一做 求1×3×5×7×9×11的值，寫出其算法。
老師評一評 算法1；第一步，先求1×3，得到結果3；
第二步，將第一步所得結果3再乘以5，得到結果15；
第三步，再將15乘以7，得到結果105；
第四步，再將105乘以9，得到945；
第五步，再將945乘以11，得到10395，即是最后結果。
算法2：用P表示被乘數，i表示乘數。
S1 使P=1。
S2 使i=3
S3 使P=P×i
S4 使i=i+2
S5 若i≤11，則返回到S3繼續(xù)執(zhí)行；否則算法結束。
1、寫出解一元二次方程ax2+bx+c=0(a≠0)的一個算法。
2、寫出求1至1000的正數中的3倍數的一個算法（打印結果）
1、解：算法如下
2S1 計算△=b-4ac
S2 如果△〈0，則方程無解；否則x1=
S3 輸出計算結果x1，x2或無解信息。
2、解：算法如下：
S1 使i=1
S2 i被3除，得余數r
S3 如果r=0，則打印i，否則不打印
S4 使i=i+1
S5 若i≤1000,則返回到S2繼續(xù)執(zhí)行，否則算法結束。
21、寫出解不等式x-2x-3<0的一個算法。
2解：第一步：x-2x-3=0的兩根是x1=3，x2=-1。
2第二步：由x-2x-3<0可知不等式的解集為{x | -1
便，我們設a>0）如下：
第一步：計算△= b4ac； 2
第二步：若△>0，示出方程兩根x1,2
{x | x>x1或x
b}； 2a第三步：若△= 0，則不等式解集為{x | x∈R且x
第四步：若△<0，則不等式的解集為R。
2、求過P(a1,b1)、Q(a2,b2)兩點的直線斜率有如下的算法：
第一步：取x1= a1，y1= b1，x2= a2，y1= b2；
第二步：若x1= x2；第三步：輸出斜率不存在；
第四步：若x1≠x2； 第五步：計算ky2y1； x2x1
第六步：輸出結果。
3、寫出求過兩點M(-2,-1)、N(2,3)的直線與坐標軸圍成面積的一個算法。
解：算法：第一步：取x1=-2，y1=-1，x2=2，y2=3； 第二步：計算yy1xx1； y2y1x2x1
第三步：在第二步結果中令x=0得到y的值m，得直線與y軸交點(0,m)；
第四步：在第二步結果中令y=0得到x的值n，得直線與x軸交點(n,0)；
第五步：計算S=1|m||n|； 2
第六步：輸出運算結果
3. 程序框圖的概念：是一種用規(guī)定的圖形，指向線及文字說明來準確、直觀地表示算法的
圖形。
4. 基本概念：
（1）起止框圖：
起止框是任何流程圖都不可缺少的，它表明程序的開始和結束，所以一個完整的流程圖的首末兩端必須是起止框。
（2表示數據的輸入或結果的輸出，它可用在算法中的任何需要輸入、輸出的位置。圖1-1中有三個輸入、輸出框。第一個出現在開始后的第一步，它的作用是輸入未知數的系數a11,a12,a21,a22和常數項b1,b2,通過這一步，就可以把給定的數值寫在輸入框內，它實際上是把未知數的系數和常數項的值通知給了計算機，另外兩個是輸出框，它們分別位于由判斷分出的兩個分支中，它們表示最后給出的運算結果，左邊分支中的輸出分框負責輸出D≠0時未知數x1,x2的值，右邊分支中的輸出框負責輸出D=0時的結果，即輸出無法求解信息。
（3）處理框：1-1中出現了兩個處理框。第一個處理框的作用是計算D=a11a22-a21a12的值，第二個處理框的作用是計算x1=(b1a22-b2a12)/D,x2=(b2a11-b1a21)/D的值。
（4）判斷框一般有一個入口和兩個出口，有時也有多個出口，它是惟一的具有兩個或兩個以上出口的符號，在只有兩個出口的情形中，通常都分成“是”與“否”（也可用“Y”與“N”）兩個分支，在圖1-1中，通過判斷框對D的值進行判斷，若判斷框中的式子是D=0，則說明D=0時由標有“是”的分支處理數據；若D≠0，則由標有“否”的分支處理數據。例如，我們要打印x的絕對值，可以設計如下框圖。