2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二.doc
《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二.doc（8頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
2019-2020 年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二 課題：遞推法 目標(biāo)： 知識(shí)目標(biāo)：遞推概念與利用遞推解決實(shí)際問題 能力目標(biāo)：遞推方程 重點(diǎn)：遞推方程 難點(diǎn)：遞推方程寫出 板書示意： 1） 遞推的理解（例 20） 2） 倒推法（例 21） 3） 順推法（例 22、例 23） 授課過程： 遞推就是逐步推導(dǎo)的過程。我們先看一個(gè)簡(jiǎn)單的問題。 例 20：一個(gè)數(shù)列的第 0 項(xiàng)為 0，第 1 項(xiàng)為 1，以后每一項(xiàng)都是前兩項(xiàng)的和，這個(gè)數(shù)列 就是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第 N 項(xiàng)。 分析：我們可以根據(jù)裴波那契數(shù)列的定義：從第 2 項(xiàng)開始，逐項(xiàng)推算，直到第 N 項(xiàng)。 因此可以設(shè)計(jì)出如下算法： F[0] := 1; F[1] := 2; FOR I := 2 TO N DO F[I] := F[I – 1] + F[I – 2]; 從這個(gè)問題可以看出，在計(jì)算裴波那契數(shù)列的每一項(xiàng)目時(shí)，都可以由前兩項(xiàng)推出。這 樣，相鄰兩項(xiàng)之間的變化有一定的規(guī)律性，我們可以將這種規(guī)律歸納成如下簡(jiǎn)捷的遞推關(guān) 系式：F n=g(Fn-1)，這就在數(shù)的序列中，建立起后項(xiàng)和前項(xiàng)之間的關(guān)系。然后從初始條件 （或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值） 。很多問題就 是這樣逐步求解的。 對(duì)一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件（或最終結(jié)果） ， 問題就可以遞推了，接下來便是讓計(jì)算機(jī)一步步了。讓高速的計(jì)算機(jī)從事這種重復(fù)運(yùn)算， 真正起到“物盡其用”的效果。 ??????????21nffn 遞推分倒推法和順推法兩種形式。算法流程如下： 一、倒推法 所謂倒推法，就是在問題的解或目標(biāo)是由初始值遞推得到的問題中，已知解或目標(biāo)， 根據(jù)遞推關(guān)系，采用倒推手段，一步步的倒推直至求得這個(gè)問題的初始陳述的方法。因?yàn)?這類問題的運(yùn)算過程是一一映射的，故可分析其遞推公式?？纯聪旅娴睦}。 例 21：貯油點(diǎn) 一輛重型卡車欲穿過 1000 公里的沙漠，卡車耗汽油為 1 升/公里，卡車總載油能力為 500 公升。顯然卡車裝一次油是過不了沙漠的。因此司機(jī)必須設(shè)法在沿途建立若干個(gè)貯油 點(diǎn)，使卡車能順利穿過沙漠。試問司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲(chǔ)多少汽 油，才能使卡車以消耗最少汽油的代價(jià)通過沙漠？ 編程計(jì)算及打印建立的貯油點(diǎn)序號(hào)，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。格 式如下： No. Distance(k.m.) Oil(litre) 1 2 … … … … … 分析： 設(shè) Way[I]——第 I 個(gè)貯油點(diǎn)到終點(diǎn)（I=0）的距離； oil[I]——第 I 個(gè)貯油點(diǎn)的貯油量； 我們可以用倒推法來解決這個(gè)問題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置 及存油量。圖 19 表示倒推時(shí)的返回點(diǎn)。 從貯油點(diǎn) I 向貯油點(diǎn) I+1 倒推的方法是：卡車在貯油點(diǎn) I 和貯油點(diǎn) I+1 間往返若干次。 卡車每次返回 I+1 點(diǎn)時(shí)應(yīng)該正好耗盡 500 公升汽油，而每次從 I+1 點(diǎn)出發(fā)時(shí)又必須裝足 圖 19 倒推過程 滿足求解 Y{順推 } 初始條件 F1 N{倒推} 由題意（或遞推關(guān)系）定初始值 F1（邊界條件）求出順推關(guān)系式 Fi=g(Fi-1)； 由題意（或遞推關(guān)系）確定最終結(jié)果 Fn；求出倒推關(guān)系式 Fi-1=g’(Fi)； I=1；{由邊界條件 F1出發(fā)進(jìn)行順推 } I=n；{從最終結(jié)果 Fn出發(fā)進(jìn)行倒推 } While 當(dāng)前結(jié)果 Fi非最終結(jié)果 Fn do While 當(dāng)前結(jié)果 Fi非初始值 F1 do 由 Fi=g(Fi-1)順推后項(xiàng)； 由 Fi-1=g(Fi)倒推前項(xiàng)； 輸出順推結(jié)果 Fn和順推過程； 輸出倒推結(jié)果 F1和倒推過程； 500 公升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下，使 I 點(diǎn)貯足 I*500 公升汽 油的要求（0≦I≦n-1） 。具體來說，第一個(gè)貯油點(diǎn) I=1 應(yīng)距終點(diǎn) I=0 處 500km，且在該點(diǎn) 貯藏 500 公升汽油，這樣才能保證卡車能由 I=1 處到達(dá)終點(diǎn) I=0 處，這就是說 Way[I]=500；oil[I]=500； 為了在 I=1 處貯藏 500 公升汽油，卡車至少?gòu)?I=2 處開兩趟滿載油的車至 I=1 處，所 以 I=2 處至少貯有 2*500 公升汽油，即 oil[2]=500*2=1000；另外，再加上從 I=1 返回至 I=2 處的一趟空載，合計(jì)往返 3 次。三次往返路程的耗油量按最省要求只能為 500 公升， 即 d12=500/3km，Way[2]=Way[1]+d 12=Way[I]+500/3 此時(shí)的狀況如圖 20 所示。 為了在 I=2 處貯藏 1000 公升汽油，卡車至少?gòu)?I=3 處開三趟滿載油的車至 I=2 處。所 以 I=3 處至少貯有 3*500 公升汽油，即 oil[3]=500*3=1500。加上 I=2 至 I=3 處的二趟返 程空車，合計(jì) 5 次。路途耗油亦應(yīng) 500 公升，即 d23=500/5， Way[3]=Way[2]+d23=Way[2]+500/5； 此時(shí)的狀況如圖 21 所示。 依次類推，為了在 I=k 處貯藏 k*500 公升汽油，卡車至少?gòu)?I=k+1 處開 k 趟滿載車至 I=k 處，即 oil[k+1]=(k+1)*500=oil[k]+500，加上從 I=k 返回 I=k+1 的 k-1 趟返程空間， 合計(jì) 2k-1 次。這 2k-1 次總耗油量按最省要求為 500 公升，即 dk,k+1=500/(2k-1)， 圖 20 倒推到第二步 圖 21 倒推到第三步 Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)； 此時(shí)的狀況如圖 22 所示。 最后，I=n 至始點(diǎn)的距離為 1000-Way[n],oil[n]=500*n。為了在 I=n 處取得 n*500 公 升汽油，卡車至少?gòu)氖键c(diǎn)開 n+1 次滿載車至 I=n，加上從 I=n 返回始點(diǎn)的 n 趟返程空車， 合計(jì) 2n+1 次，2n+1 趟的總耗油量應(yīng)正好為（1000-Way[n]）*(2n+1)，即始點(diǎn)藏油為 oil[n] +(1000-Way[n])*(2n+1)。 程序設(shè)計(jì)如下： program Oil_lib; var K: Integer; {貯油點(diǎn)位置序號(hào)} D, {累計(jì)終點(diǎn)至當(dāng)前貯油點(diǎn)的距離} D1: Real; {I=n 至終點(diǎn)的距離} Oil, Way: array [1 .. 10] of Real; i: Integer; begin Writeln(‘No.’, ‘Distance’:30, ‘Oil’:80); K := 1; D := 500; {從 I=1 處開始向終點(diǎn)倒推} Way[1] := 500; Oil[1] := 500; repeat K := K + 1; D := D + 500 / (2 * K – 1); Way[K] := D; Oil[K] := Oil[K – 1] + 500; until D >= 1000; Way[K] := 1000; {置始點(diǎn)到終點(diǎn)的距離值} D1 := 1000 – Way[K – 1]; {求 I=n 處至至點(diǎn)的距離} Oil[K] := D1 * (2 * k + 1) + Oil[K – 1]; {求始點(diǎn)貯油量} {由始點(diǎn)開始，逐一打印至當(dāng)前貯油點(diǎn)的距離和貯油量} for i := 0 to K do Writeln(i, 1000 – Way[K – i]:30, Oil[K – i]:80); end. 圖 22 倒推到第 n 步 二、順推法 順推法是從邊界條件出發(fā)，通過遞推關(guān)系式推出后項(xiàng)值，再由后項(xiàng)值按遞推關(guān)系式推 出再后項(xiàng)值……，依次類推，直至從問題初始陳述向前推進(jìn)到這個(gè)問題的解為止。 看看下面的問題。 例 22 昆蟲繁殖 科學(xué)家在熱帶森林中發(fā)現(xiàn)了一種特殊的昆蟲，這種昆蟲的繁殖能力很強(qiáng)。每對(duì)成蟲過 x 個(gè)月產(chǎn) y 對(duì)卵，每對(duì)卵要過兩個(gè)月長(zhǎng)成成蟲。假設(shè)每個(gè)成蟲不死，第一個(gè)月只有一對(duì)成 蟲，且卵長(zhǎng)成成蟲后的第一個(gè)月不產(chǎn)卵(過 X 個(gè)月產(chǎn)卵)，問過 Z 個(gè)月以后，共有成蟲多少 對(duì)？x>=1,y>=1,z>=x 輸入：x,y,z 的數(shù)值 輸出：成蟲對(duì)數(shù) 事例： 輸入：x=1 y=2 z=8 輸出：37 分析：首先我們來看樣例：每隔 1 個(gè)月產(chǎn) 2 對(duì)卵，求過 8 月（即第 8+1=9 月）的成蟲 個(gè)數(shù) 月份 1 2 3 4 5 6 7 8 9 … 新增卵 0 2 2 2 6 10 14 26 46 … 成蟲 1 1 1 3 5 7 13 23 37 … 設(shè)數(shù)組 A[i]表示第 I 月新增的成蟲個(gè)數(shù)。 由于新成蟲每過 x 個(gè)月產(chǎn) y 對(duì)卵，則可對(duì)每個(gè) A[I]作如下操作: A[i+k*x+2]:=A[i+k*x+2]+A[i]*y （1<=k, I+k*x+2z+1 end; begin readln(x,y,z); a[1]:=1; {初始化} for i:=1 to z do add(i); {對(duì)每個(gè) A[I]進(jìn)行遞推} ans:=0; for i:=1 to z+1 do ans:=ans+a[i]; {累加總和} writeln(ans); end. 例 23：實(shí)數(shù)數(shù)列（NOI94 第 3 題） 一個(gè)實(shí)數(shù)數(shù)列共有 N 項(xiàng)，已知 ai=(ai-1-ai+1)/2+d，(1下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二 2019 2020 年高 信息技術(shù) 全國(guó)青少年 奧林匹克 聯(lián)賽 教案
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
鏈接地址：http://m.appdesigncorp.com/p-2589961.html