算法的概念(1)

1、算法的概念一、引入一、引入 問題二：在實數(shù)范圍內(nèi)如何求解實系數(shù)一問題二：在實數(shù)范圍內(nèi)如何求解實系數(shù)一元二次方程元二次方程 的解？的解？ 問題一：如何把大象裝進冰箱？問題一：如何把大象裝進冰箱？20(0)axbxca算法的含義算法的含義對于一類有待求解的問題，如果建立了一對于一類有待求解的問題，如果建立了一套通用的求解方法，按部就班地實施就能套通用的求解方法，按部就班地實施就能使問題得以解決，那么這套解題方法就是使問題得以解決，那么這套解題方法就是求解該類問題的一種算法。求解該類問題的一種算法。簡單而言，就是對一類問題的簡單而言，就是對一類問題的機械的、統(tǒng)機械的、統(tǒng)一的一的求解方法稱為算法。求解

2、方法稱為算法。n藍墨水瓶里錯裝了紅墨水，紅墨水瓶里錯藍墨水瓶里錯裝了紅墨水，紅墨水瓶里錯裝了藍墨水，請你設(shè)計一個算法將它們改裝了藍墨水，請你設(shè)計一個算法將它們改正過來。正過來。 想一想想一想n有人對哥德巴赫猜想有人對哥德巴赫猜想“任何大于任何大于4的偶數(shù)都能寫的偶數(shù)都能寫成兩個奇質(zhì)數(shù)之和成兩個奇質(zhì)數(shù)之和”設(shè)計了如下操作步驟：設(shè)計了如下操作步驟：n第一步：檢驗第一步：檢驗6=3+3n第二步：檢驗第二步：檢驗8=3+5n第三步：檢驗第三步：檢驗10=5+5n請問，按照這種程序利用計算機無窮地進行下去，請問，按照這種程序利用計算機無窮地進行下去，能夠證明猜想的正確性嗎？能夠證明猜想的正確性嗎？n這是

3、一種算法嗎？這是一種算法嗎？想一想想一想算法是這樣的：算法是這樣的：n找到了某種算法，是指使用一系列運算規(guī)找到了某種算法，是指使用一系列運算規(guī)則能在則能在有限步驟有限步驟內(nèi)求解某類問題，其中的內(nèi)求解某類問題，其中的每條規(guī)則必須是每條規(guī)則必須是明確定義的、可行的明確定義的、可行的 算法有時被表示成一個算法有時被表示成一個計算公式計算公式,有時被有時被表示為一系列表示為一系列可執(zhí)行的步驟可執(zhí)行的步驟.二、例題選講二、例題選講n例例1 設(shè)計算法：求設(shè)計算法：求1+2+3+4+5 解法一：解法一： 求求1+21+2，得到，得到3 3； 將得到的將得到的3 3再加再加3 3，得到，得到6 6； 6+46

4、+4得到得到1010； 10+510+5得到得到1515。一共一共4個步驟依次執(zhí)行個步驟依次執(zhí)行,都是可行的乘法運算都是可行的乘法運算,各步各步驟前后順序不能交換驟前后順序不能交換,這種結(jié)構(gòu)為這種結(jié)構(gòu)為順序結(jié)構(gòu)順序結(jié)構(gòu)n例例1 設(shè)計算法：求設(shè)計算法：求1+2+3+4+5解法二：解法二：可以運用公式可以運用公式1+2+3+n n(n+1)/2 直接計算直接計算取取n=5n=5；運用公式計算運用公式計算n(n+1)/2 ；得到結(jié)果得到結(jié)果例題選講例題選講n例例1 設(shè)計算法：求設(shè)計算法：求1+2+3+4+5解法三：設(shè)計解法三：設(shè)計2個變量個變量把把1 1賦給賦給p p，把，把2 2賦給賦給i i；計

5、算計算p+ip+i，結(jié)果賦給，結(jié)果賦給p p；i+1i+1賦給賦給i i；如果如果i5,i5,返回重新執(zhí)行；否則，輸出返回重新執(zhí)行；否則，輸出p p例題選講例題選講P的值就是計算結(jié)果的值就是計算結(jié)果解法三：設(shè)計解法三：設(shè)計2個變量個變量把把1 1賦給賦給p p，把，把2 2賦給賦給i i；計算計算p+ip+i，乘積賦給，乘積賦給p p；i+1i+1賦給賦給i i；如果如果i5,i5,返回重新執(zhí)行返回重新執(zhí)行；否則，輸出；否則，輸出p p這種語句叫做算法中的這種語句叫做算法中的條件結(jié)構(gòu)條件結(jié)構(gòu)，它的基本形式是：如果它的基本形式是：如果“條件條件”成立，那么執(zhí)行指成立，那么執(zhí)行指令（指令組）令（指

6、令組）A A；如果；如果“條條件件”不成立，那么執(zhí)行指令不成立，那么執(zhí)行指令（指令組）（指令組）B B。 反復(fù)多次執(zhí)行反復(fù)多次執(zhí)行步驟，這種重復(fù)執(zhí)步驟，這種重復(fù)執(zhí)行同樣指令的結(jié)構(gòu)叫做算法中的行同樣指令的結(jié)構(gòu)叫做算法中的循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)。 其中變量其中變量i的數(shù)值決定循環(huán)的的數(shù)值決定循環(huán)的“繼續(xù)繼續(xù)”還還是是“結(jié)束結(jié)束”，故稱，故稱i i為為循環(huán)變量循環(huán)變量，稱重復(fù)執(zhí)，稱重復(fù)執(zhí)行的指令組為行的指令組為循環(huán)體循環(huán)體。（1）有限性：有限性： 一個算法必須保證執(zhí)行有限步后獲得結(jié)論一個算法必須保證執(zhí)行有限步后獲得結(jié)論.算法的特點：算法的特點：（5）每個算法必須有已知信息的輸入和運算結(jié)果輸出每個算法必須有

7、已知信息的輸入和運算結(jié)果輸出.（4）非唯一性：非唯一性：求解某個問題的算法不一定是唯一的，允求解某個問題的算法不一定是唯一的，允許有不同的算法許有不同的算法.（3）可行性：可行性： 前一步是后一步的基礎(chǔ)；每一步都是可行的前一步是后一步的基礎(chǔ)；每一步都是可行的.（2）確定性：確定性： 每一步操作都有確定意義，不允許產(chǎn)生歧義每一步操作都有確定意義，不允許產(chǎn)生歧義.12-1-21,1,(3),nnnfffffn 例例2 2 對于第對于第7 7章閱讀材料中給出的斐波那契數(shù)列：章閱讀材料中給出的斐波那契數(shù)列：20f20.S 計算并輸出計算并輸出和前和前2020項的和項的和 分析：因為斐波那契數(shù)列是以遞推

8、形式給出的，所以要逐分析：因為斐波那契數(shù)列是以遞推形式給出的，所以要逐項計算項計算3420.SSS、 、3420fff、 、和和（1 1）把）把1 1賦予賦予和和，把，把2 2賦予賦予，把，把3 3賦予賦予n.n.1f2f2S12nnnfff 1.nnnSSf （2 2）計算）計算，計算，計算（3 3）把）把 n+1 n+1 賦予賦予 n. n. 20n 20,n 20f20S（4）如果）如果，那么再執(zhí)行第（，那么再執(zhí)行第（2）步；如果）步；如果那么輸出那么輸出和和并結(jié)束計算并結(jié)束計算. 2 0f2 0S求求和和的一種算法的一種算法. 例題選講例題選講n例例3：設(shè)計算法，找出三個數(shù)：設(shè)計算法，

9、找出三個數(shù)a,b,c中的最大中的最大數(shù)數(shù).n把把a a賦給賦給M M；n如果如果MbMb，則，則b b賦給賦給M M； 如果如果MbMb，則，則M M不變；不變；nMcMc，則，則c c賦給賦給M M； 如果如果McMc，則，則M M不變；不變；例題選講例題選講n設(shè)計算法，找出五個數(shù)設(shè)計算法，找出五個數(shù)x1,x2,x3,x4,x5中的最中的最大數(shù)大數(shù)練一練練一練n設(shè)計算法，找出任意設(shè)計算法，找出任意N個數(shù)個數(shù)x1,x2,x3,xN中的最大數(shù)中的最大數(shù)三、小結(jié)三、小結(jié)n算法的含義算法的含義：一般而言，對一類問題的機械的、一般而言，對一類問題的機械的、統(tǒng)一的求解方法稱為算法。統(tǒng)一的求解方法稱為算法。n算法的基本思想：探求解決問題的一般性方法，算法的基本思想：探求解決問題的一般性方法，并將解決問題的步驟用具體化