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