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

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