算法的概念(1)

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

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

3、一種算法嗎？這是一種算法嗎？想一想想一想算法是這樣的：算法是這樣的：n找到了某種算法，是指使用一系列運(yùn)算規(guī)找到了某種算法，是指使用一系列運(yùn)算規(guī)則能在則能在有限步驟有限步驟內(nèi)求解某類(lèi)問(wèn)題，其中的內(nèi)求解某類(lèi)問(wèn)題，其中的每條規(guī)則必須是每條規(guī)則必須是明確定義的、可行的明確定義的、可行的 算法有時(shí)被表示成一個(gè)算法有時(shí)被表示成一個(gè)計(jì)算公式計(jì)算公式,有時(shí)被有時(shí)被表示為一系列表示為一系列可執(zhí)行的步驟可執(zhí)行的步驟.二、例題選講二、例題選講n例例1 設(shè)計(jì)算法：求設(shè)計(jì)算法：求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個(gè)步驟依次執(zhí)行個(gè)步驟依次執(zhí)行,都是可行的乘法運(yùn)算都是可行的乘法運(yùn)算,各步各步驟前后順序不能交換驟前后順序不能交換,這種結(jié)構(gòu)為這種結(jié)構(gòu)為順序結(jié)構(gòu)順序結(jié)構(gòu)n例例1 設(shè)計(jì)算法：求設(shè)計(jì)算法：求1+2+3+4+5解法二：解法二：可以運(yùn)用公式可以運(yùn)用公式1+2+3+n n(n+1)/2 直接計(jì)算直接計(jì)算取取n=5n=5；運(yùn)用公式計(jì)算運(yùn)用公式計(jì)算n(n+1)/2 ；得到結(jié)果得到結(jié)果例題選講例題選講n例例1 設(shè)計(jì)算法：求設(shè)計(jì)算法：求1+2+3+4+5解法三：設(shè)計(jì)解法三：設(shè)計(jì)2個(gè)變量個(gè)變量把把1 1賦給賦給p p，把，把2 2賦給賦給i i；計(jì)

5、算計(jì)算p+ip+i，結(jié)果賦給，結(jié)果賦給p p；i+1i+1賦給賦給i i；如果如果i5,i5,返回重新執(zhí)行；否則，輸出返回重新執(zhí)行；否則，輸出p p例題選講例題選講P的值就是計(jì)算結(jié)果的值就是計(jì)算結(jié)果解法三：設(shè)計(jì)解法三：設(shè)計(jì)2個(gè)變量個(gè)變量把把1 1賦給賦給p p，把，把2 2賦給賦給i i；計(jì)算計(jì)算p+ip+i，乘積賦給，乘積賦給p p；i+1i+1賦給賦給i i；如果如果i5,i5,返回重新執(zhí)行返回重新執(zhí)行；否則，輸出；否則，輸出p p這種語(yǔ)句叫做算法中的這種語(yǔ)句叫做算法中的條件結(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é)束”，故稱(chēng)，故稱(chēng)i i為為循環(huán)變量循環(huán)變量，稱(chēng)重復(fù)執(zhí)，稱(chēng)重復(fù)執(zhí)行的指令組為行的指令組為循環(huán)體循環(huán)體。（1）有限性：有限性： 一個(gè)算法必須保證執(zhí)行有限步后獲得結(jié)論一個(gè)算法必須保證執(zhí)行有限步后獲得結(jié)論.算法的特點(diǎn)：算法的特點(diǎn)：（5）每個(gè)算法必須有已知信息的輸入和運(yùn)算結(jié)果輸出每個(gè)算法必須有

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

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

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