動態(tài)規(guī)劃教案

吉林師范大學(xué)計算機(jī)學(xué)院教案課程名稱C程序設(shè)計(算法部分)院系級計算機(jī)學(xué)院計算機(jī)科學(xué)與技術(shù)09級教研室(系、實驗室)計算機(jī)基礎(chǔ)教研室5101授課班級09計算機(jī)科學(xué)與技術(shù)3班實習(xí)生鄭言系指導(dǎo)教師滕國文吉林師范大學(xué)計算機(jī)學(xué)院二○一二年四月二十五日（禮拜三5，6節(jié)）課型章節(jié)：動向規(guī)劃基本思想基要本參教考材資和料主：算法設(shè)計與剖析》教課目標(biāo)：本課程以C語言為教授程序設(shè)計的描繪語言，聯(lián)合語言介紹程序設(shè)計的基本原理、技巧和方法。主要解說內(nèi)容包含程序設(shè)計動向規(guī)劃基本觀點(diǎn)，動向規(guī)劃的基本步驟，動向規(guī)劃問題的特點(diǎn)。經(jīng)過本課程的學(xué)習(xí)，為算法更好的學(xué)習(xí)，以及能用計算機(jī)解決一些實質(zhì)問題打下堅固的基礎(chǔ)。教課基本要求：掌握C語言中動向規(guī)劃的基本觀點(diǎn)，動向規(guī)劃的基本步驟，動向規(guī)劃問題的特點(diǎn)。并能嫻熟使用C語言動向規(guī)劃思想解決一些簡單程序問題；掌握一些基本算法結(jié)構(gòu)及有關(guān)方法；熟習(xí)程序設(shè)計的思想和編程技巧。要點(diǎn)：動向規(guī)劃基本觀點(diǎn)，動向規(guī)劃的基本步驟，動向規(guī)劃問題的特點(diǎn)。難點(diǎn):動向規(guī)劃的基本步驟課型：理論課教法：1.多媒體解說2.舉例解說教課內(nèi)容及過程：課前回首：列舉法:在進(jìn)行概括推理時，假如逐一觀察了某類事件的全部可能狀況，因此得出一般結(jié)論，那么這結(jié)論是靠譜的，這種概括方法叫做列舉法．?dāng)?shù)塔問題有形以下列圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)能夠選擇向左走或是向右走，向來走究竟層，要求找出一條路徑，使路徑上的值最大。簡單的進(jìn)行選舉方法的指引，讓同學(xué)們主動思慮到動向規(guī)劃的思想上了?？紤]一下：從極點(diǎn)出發(fā)時究竟向左走仍是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只需左右兩道路徑上的最大值求出來了才能作出決策。相同，下一層的走向又要取決于再下一層上的最大值能否已經(jīng)求出才能決議。這樣一層一層推下去，直到倒數(shù)第二層時就特別了然。如數(shù)字2，只需選擇它下邊較大值的結(jié)點(diǎn)19行進(jìn)就能夠了。所以實質(zhì)求解時，可從基層開始，層層遞進(jìn)，最后獲得最大值。結(jié)論：自頂向下的剖析，自底向上的計算。#include<>#include<>intmax(intx,inty){if(x>y)returnx;elsereturny;}main( ){inta[100][100];inti,j,n;scanf("%d",&n);for(i=0;i<n;i++)for(j=0;j<=i;j++)scanf("%d",&a[i][j]);for(i=n-2;i>=0;i--)for(j=0;j<=i;j++){a[i][j]+=max(a[i+1][j],a[i+1][j+1]);}printf("%d\n",a[0][0]);}3.總結(jié)“動向規(guī)劃的基本思想”假如各個子問題不是獨(dú)立的，不一樣的子問題的個數(shù)不過多項式量級，假如我們能夠保留已經(jīng)解決的子問題的答案，而在需要的時候再找出已求得的答案，這樣就能夠防止大批的重復(fù)計算。由此而來的基本思路是，用一個表記錄全部已解決的子問題的答案，不論該問題此后能否被用到，只需它被計算過，就將其結(jié)果填入表中。4.總結(jié)“動向規(guī)劃的基本步驟”動向規(guī)劃算法往常用于求解擁有某種最優(yōu)性質(zhì)的問題。在這種問題中，可能會有很多可行解。每一個解都對應(yīng)于一個值，我們希望找到擁有最優(yōu)值（最大值或最小值）的那個解。設(shè)計一個動向規(guī)劃算法，往常能夠按以下幾個步驟進(jìn)行：1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特點(diǎn)。2）遞歸地定義最優(yōu)值。3）以自底向上的方式計算出最優(yōu)值。4）依據(jù)計算最優(yōu)值時獲得的信息，結(jié)構(gòu)一個最優(yōu)解。此中（1）——（3）步是動向規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情況，步驟（4）能夠省去。若需要求出問題的一個最優(yōu)解，則一定履行步驟（4）。此時，在步驟（3）上當(dāng)算最優(yōu)值時，往常需記錄更多的信息，以便在步驟（4）中，依據(jù)所記錄的信息，迅速結(jié)構(gòu)出一個最優(yōu)解。5.總結(jié)“動向規(guī)劃問題的特點(diǎn)”動向規(guī)劃算法的有效性依靠于問題自己所擁有的兩個重要性質(zhì)：1、最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題擁有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不老是新問題，有些子問題被頻頻計算多次。動向規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，爾后將其解保留在一個表格中，在以后盡可能多地利用這些子問題的解。6.思慮：《免費(fèi)餡餅》題目描繪:都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，突然天上掉下大把大把的餡餅。說來gameboy的人格實在是太好了，這餡餅別處都不掉，就掉落在他身邊的10米范圍內(nèi)。餡餅假如掉在了地受騙然就不可以吃了，所以gameboy立刻卸掉身上的背包去接。但因為小徑雙側(cè)都不可以站人，所以他只好在小徑上接。因為gameboy平常老呆在房間里玩游戲，固然在游戲中是個身手矯捷的能手，但在現(xiàn)實中運(yùn)動神經(jīng)特別愚鈍，每秒種只有在挪動不超出一米的范圍內(nèi)接住墜落的餡餅。此刻給這條小徑如圖標(biāo)上坐標(biāo)：為了使問題簡化，假定在接下來的一段時間里，餡餅都掉落在0-10這11個地點(diǎn)。開始時gameboy站在5這個地點(diǎn)，所以在第一秒，他只好接到4,5,6這三個地點(diǎn)中期中一個地點(diǎn)上的餡餅。問gameboy最多可能接到多少個餡餅（假定他的背包能夠容納無量多個餡餅）#include<iostream>usingnamespacestd;inta[100001][11];intmax(intx,inty,intz){if(x>y)if(x>z)returnx;elsereturnz;elseif(y>z)returny;elsereturnz;}intmain( ){inti,j,f,n,x,y;while(cin>>n){if(n==0)break;memset(a,0,sizeof(a));f=0;for(i=0;i<n;i++){cin>>y>>x;a[x][y]++;if(x>f)f=x;}for(i=f-1;i>=0;i--){for(j=0;j<11;j++)if(j>0&&j<10)a[i][j]+=max(a[i+1][j-1],a[i+1][j],a[i+1][j+1]);elseif(j==0)a[i][j]+=max(0,a[i+