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