循環(huán)結(jié)構(gòu)(公開課、北師大版)

1、Page 1 Page 2 前面我們學習了算法的基本結(jié)構(gòu)：順序結(jié)構(gòu)與選擇結(jié)構(gòu)前面我們學習了算法的基本結(jié)構(gòu)：順序結(jié)構(gòu)與選擇結(jié)構(gòu) ，它們可以利用框架結(jié)構(gòu)來說明，它們可以利用框架結(jié)構(gòu)來說明 A B 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 滿足條件滿足條件 AB 是是否否 順序結(jié)構(gòu)順序結(jié)構(gòu) 滿足條件滿足條件 A 是是否否 Page 3 n 1.（2009上海卷）某算 法的程序框圖如圖所示，則 輸出量y與輸入量x滿足的關 系式是 n . 2x (x1) x-2 (x1) y= Page 4 北京取得北京取得20082008奧運會主辦權(quán)的投票過程奧運會主辦權(quán)的投票過程 對選出的五個城市進行投票表決的流程是：首對選出的五個城市進

2、行投票表決的流程是：首 先進行第一輪投票，如果有一個城市得票超過一先進行第一輪投票，如果有一個城市得票超過一 半，那么這個城市取得主辦權(quán)；如果沒有一個城半，那么這個城市取得主辦權(quán)；如果沒有一個城 市得票超過一半，那么將其中得票最少的城市淘市得票超過一半，那么將其中得票最少的城市淘 汰，然后汰，然后上述過程，再進行投票，直到選出上述過程，再進行投票，直到選出 一個城市為止。一個城市為止。 1.1.投票；投票； 2.2.計票：如果有一個城市得票超過一半，計票：如果有一個城市得票超過一半， 那么這個城市取得主辦權(quán)，轉(zhuǎn)入步驟那么這個城市取得主辦權(quán)，轉(zhuǎn)入步驟3 3； 否則淘汰掉得票最少的城市，否則淘汰掉

3、得票最少的城市，返回步驟返回步驟1 1， 繼續(xù)執(zhí)行后繼步驟；繼續(xù)執(zhí)行后繼步驟； 3.3.宣布主辦城市。宣布主辦城市。 Page 5 選出該城市選出該城市 有一城市過半數(shù)有一城市過半數(shù) 投票投票 淘汰得票最少者淘汰得票最少者 結(jié)束結(jié)束 開始開始 是是 否否 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) Page 6 開始開始 S=1 S=S+1/2 S=S+1/3 S=S+1/4 結(jié)束結(jié)束 輸出輸出S 畫出計算畫出計算 的程序框圖的程序框圖。 4 1 3 1 2 1 1 1 100000 1 1 1. 2 3 如果要計算如果要計算 的值呢？的值呢？ Page 7 以上算法中以上算法中, 出現(xiàn)從某處開始出現(xiàn)從某處開始,按照一

4、定條件按照一定條件, 反復執(zhí)行某些步驟的情況反復執(zhí)行某些步驟的情況.這就是這就是循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu).反復反復 執(zhí)行的步驟稱為執(zhí)行的步驟稱為循環(huán)體循環(huán)體. 求求:1+1/2+1/3+ +1/10000的值的值 第一步第一步:令令1,0iS 第二步第二步:若若 成立成立,則執(zhí)行第三步；否則則執(zhí)行第三步；否則,輸出輸出S,結(jié)束算法結(jié)束算法. 第四步第四步:1ii ,返回第二步返回第二步. 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 10000i 第三步第三步:iss/1 Page 8 開始開始 1i 0S N 輸出輸出S 結(jié)束結(jié)束 計數(shù)變量計數(shù)變量:用于記錄循環(huán)次數(shù)用于記錄循環(huán)次數(shù),同時還用同時還用 于判斷循環(huán)是否終止于判斷循

5、環(huán)是否終止. 累加變量累加變量:用于輸出結(jié)果用于輸出結(jié)果,一般與計數(shù)變一般與計數(shù)變 量同步執(zhí)行量同步執(zhí)行,累加一次累加一次,計數(shù)一次計數(shù)一次. 循環(huán)終止條件循環(huán)終止條件 循環(huán)體循環(huán)體 循環(huán)變量 10000i 1ii Y iss/1 Page 9 循環(huán)結(jié)構(gòu)的設計步驟循環(huán)結(jié)構(gòu)的設計步驟 (1)(1)確定循環(huán)結(jié)構(gòu)的循環(huán)變量和初始條件確定循環(huán)結(jié)構(gòu)的循環(huán)變量和初始條件; ; (2)(2)確定算法中需要反復執(zhí)行的部分確定算法中需要反復執(zhí)行的部分, ,即循環(huán)體；即循環(huán)體； (3)(3)確定循環(huán)的終止條件確定循環(huán)的終止條件. . 循環(huán)結(jié)構(gòu)的三要素循環(huán)結(jié)構(gòu)的三要素 循環(huán)變量循環(huán)變量, ,循環(huán)體、循環(huán)的終止條件循

6、環(huán)體、循環(huán)的終止條件. . 循環(huán)結(jié)構(gòu)一定包含條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)一定包含條件結(jié)構(gòu),用以控制循環(huán)過程用以控制循環(huán)過程,避免出現(xiàn)避免出現(xiàn) “死循環(huán)死循環(huán)”.判斷框內(nèi)寫上條件判斷框內(nèi)寫上條件,兩個出口分別對應終止條件成兩個出口分別對應終止條件成 立與否立與否,其中一個指向循環(huán)體其中一個指向循環(huán)體,經(jīng)過循環(huán)體回到判斷框的入口處經(jīng)過循環(huán)體回到判斷框的入口處. Page 10 類型二類型二 循環(huán)結(jié)構(gòu)的類型循環(huán)結(jié)構(gòu)的類型 先判斷條件先判斷條件,當條件滿足當條件滿足,再執(zhí)再執(zhí) 行循環(huán)體行循環(huán)體;當條件不滿足當條件不滿足,循循 環(huán)結(jié)束環(huán)結(jié)束. 先執(zhí)行循環(huán)體先執(zhí)行循環(huán)體,再判斷條件再判斷條件, 若條件不滿足若條件不滿

7、足,再執(zhí)行循環(huán)體再執(zhí)行循環(huán)體; 直到條件滿足直到條件滿足,循環(huán)結(jié)束循環(huán)結(jié)束. 滿足條件？滿足條件？ 循環(huán)體循環(huán)體 是是 否否 滿足條件？滿足條件？ 循環(huán)體循環(huán)體 是是 否否 類型一類型一 Page 11 注意注意:循環(huán)結(jié)構(gòu)不能是永無終止的循環(huán)結(jié)構(gòu)不能是永無終止的“死循死循 環(huán)環(huán)”,一定要在某個條件下終止循環(huán)一定要在某個條件下終止循環(huán),這就需這就需 要條件結(jié)構(gòu)來作出判斷要條件結(jié)構(gòu)來作出判斷,因此因此,循環(huán)結(jié)構(gòu)中一循環(huán)結(jié)構(gòu)中一 定包含條件結(jié)構(gòu)定包含條件結(jié)構(gòu). Page 12 開始開始 1i 0S 100?i Y 輸出輸出S 結(jié)束結(jié)束 N 類型二類型二 1ii SSi 第三步第三步: 求求1+2+3

8、+ +100 第一步第一步:令令1,0iS 第四步第四步:若若 成立成立,則輸出則輸出S, 結(jié)束算法結(jié)束算法.否則否則,返回第二步返回第二步. 100i 第二步第二步:SSi 1ii Page 13 類型一類型一 開始開始 1i 0S 100?i N 輸出輸出S 結(jié)束結(jié)束 1ii SSi Y Page 14 n按如圖所示的程序框圖 運行后，若輸出的S的值等于 16，那么在程序框圖中的判 斷框內(nèi)應填寫的條件是 （ ） nA.i5？B.i6？ nC.i7？D.i8？ A Page 15 n 從循環(huán)體中計數(shù)變量入手，確定循 環(huán)次數(shù)為多少時，運行結(jié)束，即可確定判 斷框內(nèi)的條件. n 對于i=1,S=1

9、時，執(zhí)行S=S+i后，S=2， 執(zhí)行i=i+1后，i=2； ni=2,S=2時，執(zhí)行S=S+i后，S=4，執(zhí)行 i=i+1后，i=3； ni=3,S=4時，執(zhí)行S=S+i后，S=7，執(zhí)行 i=i+1后，i=4； Page 16 ni=4,S=7時，執(zhí)行S=S+i后，S=11，執(zhí)行 i=i+1后，i=5； ni=5,S=11時，執(zhí)行S=S+i后，S=16，執(zhí)行 i=i+1后， ni=6，因為輸出的S的值等于16，所以判斷框 內(nèi)的條件為i5，選A. n 在循環(huán)結(jié)構(gòu)中，要注意根據(jù)條件設 計合理的計數(shù)變量、累加變量及其個數(shù)，特 別要求條件的表述要恰當、精確. Page 17 菲波拉契數(shù)列表示的是這菲波

10、拉契數(shù)列表示的是這 樣一列數(shù)樣一列數(shù): 0，1，1，2，3，5， 后一項等于前兩項的和后一項等于前兩項的和. 設計一個設計一個 算法流程圖算法流程圖,輸出這個數(shù)列的前輸出這個數(shù)列的前50項項. 開始開始 A=0,B=1 輸出輸出A，B i=3 結(jié)束結(jié)束 i50 C=A+B 輸出輸出C A=B B=C i=i+1 算法：算法： 節(jié)約空間節(jié)約空間A=0，B=1 輸出輸出A,B C=A+B 輸出輸出C 執(zhí)行至此，已經(jīng)輸出了數(shù)列的前三項，執(zhí)行至此，已經(jīng)輸出了數(shù)列的前三項， 可以釋放掉這可以釋放掉這3個變量代表的數(shù)值，個變量代表的數(shù)值， 賦予變量新的數(shù)值：賦予變量新的數(shù)值： A=B；（用；（用A表示數(shù)列

11、的第表示數(shù)列的第2項）項） B=C；（；（用用B表示數(shù)列的第表示數(shù)列的第3項）項） C=A+B；輸出；輸出C Page 18 設計算法流程圖，求解方程設計算法流程圖，求解方程x3 3+4+4x-10=0-10=0在區(qū)在區(qū) 間間00，22內(nèi)的解（精確至內(nèi)的解（精確至1010-5 -5） ） 開始開始 a=0,b=1 a=(a+b)/2 輸出輸出(a+b)/2 結(jié)束結(jié)束 f(a+b)/2)=0 是是 f(a)f(a+b)/2)0 b=(a+b)/2 否否 b-a100? 結(jié)束 是 否 輸出S 開始 S=1,i=2 S=S*i i=i+1 i100? 結(jié)束 是 否 輸出S Page 20 n 2.如

12、果執(zhí)行下面的程序框圖，那么輸出的 S=（ ） n A.7 B.9 n C.11D.13 C 對于對于i=1,S=1時，執(zhí)時，執(zhí) 行行i=i+1后，后，i=2，執(zhí)行，執(zhí)行S=S+2后，后， S=3； 當當i=2，S=3時，執(zhí)行時，執(zhí)行i=i+1后，后， i=3，執(zhí)行，執(zhí)行S=S+2后，后，S=5； Page 21 n 當i=3，S=5時，執(zhí)行i=i+1后，i=4，執(zhí)行S=S+2后，S=7； n 當i=4，S=7時，執(zhí)行i=i+1后，i=5，執(zhí)行S=S+2后，S=9； n 當i=5，S=9時，執(zhí)行i=i+1后，i=6，執(zhí)行S=S+2后，S=11； n 此時i=65，故輸出S=11，選C. n 易錯

13、點：對于循環(huán)體執(zhí)行的次數(shù). Page 22 n 3.如圖所示的程序框圖的 算法功能。 n ，輸出結(jié)果 為i= ，i+2= . 若若i=2，則，則 i+2也是偶數(shù)也是偶數(shù).而由程序框而由程序框 圖中有循環(huán)結(jié)構(gòu)可知，圖中有循環(huán)結(jié)構(gòu)可知， 算法功能為求積是算法功能為求積是624的的 相相 求積是求積是 624的相鄰兩個偶數(shù)的相鄰兩個偶數(shù) 24 26 鄰兩個偶數(shù)鄰兩個偶數(shù).填：求積是填：求積是624的相鄰兩個偶數(shù)；的相鄰兩個偶數(shù)； 24；26. 易錯點：對條件語句的理解易錯點：對條件語句的理解. 循環(huán)量：循環(huán)量：= =初始值初始值 循環(huán)體循環(huán)體 循環(huán)量：循環(huán)量：= =循環(huán)變量的后繼循環(huán)變量的后繼 循環(huán)

14、變量循環(huán)變量 終值終值 是是 否否 Page 24 若將條件若將條件“i”改改 為為“”，輸出結(jié)果是什，輸出結(jié)果是什 么？么？ 2. 若將若將” i i + 1” 與與 “S S + i”交換交換,則輸出結(jié)果則輸出結(jié)果 是什么？是什么？ 結(jié)束 輸出S i 1，S 0 開始 s s + i i i + 1 i=? 否 是 Page 25 n 2.（2009浙江卷）某程序框 圖如圖所示，該程序運行后 輸出的k的值是（ ） n A.4 n B.5 n C.6 n D.7 A Page 26 1如圖是一個程序框圖，則輸出的結(jié)果如圖是一個程序框圖，則輸出的結(jié)果 是是() Page 27 (2010年高考

15、年高考 陜西卷陜西卷)如圖是求如圖是求x1，x2， ，x10的乘積的乘積S的程序框圖，的程序框圖， 圖中空白框中應填入的圖中空白框中應填入的 內(nèi)容為內(nèi)容為() 變式訓練變式訓練1 ASS*(n1) BSS*xn 1 CSS*n DSS*xn Page 28 設計算法流程圖，求解方程設計算法流程圖，求解方程x3 3+4+4x-10=0-10=0在區(qū)在區(qū) 間間00，22內(nèi)的解（精確至內(nèi)的解（精確至1010-5 -5） ） 開始開始 a=0,b=1 a=(a+b)/2 輸出輸出(a+b)/2 結(jié)束結(jié)束 f(a+b)/2)=0 是是 f(a)f(a+b)/2)0 b=(a+b)/2 否否 b-a100

16、，故輸出k=4. Page 30 例例8 閱讀如圖所示閱讀如圖所示 的流程圖，解答下的流程圖，解答下 列問題：列問題： (1)(1)變量變量y在這個算法中在這個算法中 的作用是什么？的作用是什么？ (2)(2)這個算法的循環(huán)體是這個算法的循環(huán)體是 哪一部分，功能是什么？哪一部分，功能是什么？ (3)(3)這個算法的處理功能這個算法的處理功能 是什么？是什么？ 開始開始 y=2000 4整除整除y 100整除整除y 輸出輸出“y是閏年是閏年” 輸出輸出“y不是閏年不是閏年” 400整除整除y 是是 否否 是是 否否 否否是是 輸出輸出“y 不是閏年不是閏年” 輸出輸出“y 是閏年是閏年” y:=

17、y+1 y2500 否否 是是 結(jié)束結(jié)束 Page 31 例2. 某工廠2005年的年生產(chǎn)總值為 200萬元,技術革新后,預計每年生產(chǎn) 總值都比前一年增長5%,設計一個程 序圖,輸出預計年生產(chǎn)總值超過300 萬元的最早年份。 Page 32 算法算法 第一步：輸入第一步：輸入2005年的年生產(chǎn)總值年的年生產(chǎn)總值. 第二步：計算下一年的年生產(chǎn)總值第二步：計算下一年的年生產(chǎn)總值. 第三步：判斷所得結(jié)果是否大于第三步：判斷所得結(jié)果是否大于300.若是，輸出該年若是，輸出該年 年份年份;否則，返回第二步否則，返回第二步. 循環(huán)結(jié)構(gòu)的設計步驟循環(huán)結(jié)構(gòu)的設計步驟 (1)(1)確定循環(huán)結(jié)構(gòu)的確定循環(huán)結(jié)構(gòu)的循環(huán)變量循環(huán)變量和和初始條件初始條件; ; (2)(2)確定算法中需要反復執(zhí)行的部分確定算法中需要反復執(zhí)行的部分, ,即即循環(huán)體