算法青蛙過河

1、吉林財(cái)經(jīng)大學(xué)課程設(shè)計(jì)報(bào)告所在院系：信息學(xué)院計(jì)算機(jī)系科目名稱：算法設(shè)計(jì)與分析學(xué)號(hào)：1401080940姓名：付為設(shè)計(jì)題目：題目一:過河問題題目二:直線k中值問題提交時(shí)間：2011年3月目錄1、青蛙過河問題 11.1題目描述與設(shè)計(jì)要求 11.2問題分析 11.3算法設(shè)計(jì) 21.4復(fù)雜性分析 41.5總結(jié) 41.6附錄 42、k中值問題 42.1題目描述與設(shè)計(jì)要求 72.2問題分析 72.3算法設(shè)計(jì) 82.4復(fù)雜性分析 92.5總結(jié) 92.6附錄 9青蛙過河1.1問題描述在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳

2、過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，L（其中L是橋的長度）。坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。對(duì)于30%的數(shù)據(jù)，L<=10000對(duì)于全部的數(shù)據(jù)，L<=109輸入格式 Input Format輸入的第一行有一個(gè)正整數(shù)L（1 <= L <= 1

3、09），表示獨(dú)木橋的長度。第二行有三個(gè)正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M個(gè)不同的正整數(shù)分別表示這M個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開。輸出格式 Output Format 輸出只包括一個(gè)整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。樣例輸入 Sample Input102 3 52 3 5 6 7樣例輸出 Sample Output21.2問題分析路徑壓縮法，雖然橋很長，但上面最多只有100個(gè)石

4、子，想到能否用石子DP，而應(yīng)該是不行的。由于石子排布非常的疏，我們還會(huì)發(fā)現(xiàn)，如果兩個(gè)石子相隔甚遠(yuǎn)，那他們中間的fi大部分將會(huì)是同一個(gè)數(shù)，能否把兩個(gè)石子的距離縮短，使之還與原來等效？要是行的話怎么縮？王乃巖同學(xué)考試時(shí)做了一個(gè)方法能夠過全部數(shù)據(jù)，用的滾動(dòng)數(shù)組存儲(chǔ)，下面列出了他的程序。我自己也寫了個(gè)程序，和他不盡相同：我令L=stonei-stonei-1（stonei代表按坐標(biāo)由小到大順序排列的石塊坐標(biāo)），當(dāng)L能夠被t整除時(shí)（L%t=0），令k=t；當(dāng)L不能被t整除時(shí)（L%t!=0），令k=L%t。然后令k為k+t，最后判斷如果k>L，那么map中stonei和stonei-1兩石頭的距離就

5、被等效成為L（也就是沒變）；如果k<=L，那么map數(shù)組中stonei和stonei-1兩石頭的距離就被等效成為k，可以看出來，這樣處理完，兩石子最大間距為2*t，大大的縮短了數(shù)組，再按解一進(jìn)行DP，就可以通過了。1.3算法設(shè)計(jì)J+P=0;i=1輸入L,S,T,M;stonei,min=1000YNi<=Mmemset(map, 0, sizeof(int)*100001);memset(f, 0, sizeof(int)*100001);quickSort(1, M); l = stonei - stonei - 1;YNL%T=0K=l%T;K=K+TK=TL<KK=1;

6、p=p+K;mapp=1i<=p+Tj=i-Tj>=0;fj<min j <= iNYi<=p；fi<minMin=fj;fi=min+mapii=p+1 min = fi1.4復(fù)雜性分析簡單動(dòng)態(tài)規(guī)劃，fi代表青蛙跳到i點(diǎn)時(shí)所可能踩到的最少石子數(shù)，所以有fi=minfk+mapi(i-ski-t)，其中mapi代表i上是否有石子，有是1，否則0。算法復(fù)雜度O(n2)。路徑壓縮的dp路徑壓縮方法：設(shè)s與t的最小公倍數(shù)為LCM,則當(dāng)相鄰的兩粒石子距離S>LCM時(shí)情況與相距 LCM+(S MOD LCM)情況一樣dp就很簡單了dpi表示跳到i個(gè)位置（壓縮后的

7、）最少踩到的石子數(shù)則有dpi=mindpi-j+fi 對(duì)于s<=j<=t當(dāng)?shù)趇格有石子時(shí)fi=1否則fi=0我們不難發(fā)現(xiàn)其實(shí)這題可以應(yīng)用單調(diào)隊(duì)列（雖然沒有必要）目前我的方法是用一個(gè)緩存隊(duì)列保存i-s+1至i格的情況，每次將第i格算出后加入緩存，并將緩存中第i-s+1格入單調(diào)隊(duì)列這樣時(shí)間復(fù)雜度由O(n2)降至O(N)1.5總結(jié)這道題在沒看數(shù)據(jù)規(guī)模之前以為是一道簡單的DP，但是數(shù)據(jù)開到十億，無論在時(shí)間還是空間復(fù)雜度都過大，所以就要進(jìn)行優(yōu)化了。選擇簡單的動(dòng)態(tài)規(guī)劃方法會(huì)使復(fù)雜度太高，所以我選擇了路徑壓縮法，調(diào)用隊(duì)列使復(fù)雜度大大降低。1.6附錄代碼#include <stdio.h&g

8、t;#include <string.h>long stone101;int map100001;int f100001;long L;int S, T, M; void quickSort(int l, int r)int i , j;long temp;i = l;j = r;temp = stonei;while (i < j)while (i < j && stonej > temp)j-;if (i < j)stonei = stonej;i+;while (i < j && stonei < temp)

9、i+;if (i < j)stonej = stonei;j-;stonei = temp;if (i - 1 > l) quickSort(l, i - 1);if (i + 1 < r) quickSort(i + 1, r);int main()int i, j;long l, k, p = 0, min;scanf("%ld%d%d%d", &L, &S, &T, &M);for (i = 1; i <= M; i+)scanf("%ld", &stonei);memset(map,

10、 0, sizeof(int)*100001);memset(f, 0, sizeof(int)*100001);quickSort(1, M);stone0 = 0;p = 0;for (i = 1; i <= M; i+)l = stonei - stonei - 1;if (l % T = 0) k = T;elsek = l % T;k = k + T;if (l < k)k = l;p = p + k;mapp = 1;for (i = 1; i <= p + T; i+)min = 1000;for (j = i - T; j <= i - S; j+)if

11、 ( j >= 0 && fj < min)min = fj;fi = min + mapi;min = 1000;for (i = p + 1; i <= p + T; i+)if (fi < min)min = fi;printf("%dn", min);return 0;直線k中值問題2.1問題描述在一個(gè)按照南北方向劃分成規(guī)整街區(qū)的城市里，n個(gè)居民點(diǎn)分布在一條直線上的n個(gè)坐標(biāo)點(diǎn)x1 << xn處。居民們希望在城市中至少選擇1個(gè)，但不超過k 個(gè)居民點(diǎn)建立服務(wù)機(jī)構(gòu)。在每個(gè)居民點(diǎn)處，服務(wù)需求量為w i ³ 0，在

12、該居民點(diǎn)設(shè)置服務(wù)機(jī)構(gòu)的費(fèi)用為c i ³ 0。假設(shè)居民點(diǎn)xi到距其最近的服務(wù)機(jī)構(gòu)的距離為di ，則居民點(diǎn)xi 的服務(wù)費(fèi)用為wi ´ di 。建立k 個(gè)服務(wù)機(jī)構(gòu)的總費(fèi)用為A+B。A 是在k 個(gè)居民點(diǎn)設(shè)置服務(wù)機(jī)構(gòu)的費(fèi)用的總和；B是n個(gè)居民點(diǎn)服務(wù)費(fèi)用的總和。編程任務(wù)：對(duì)于給定直線L 上的n 個(gè)點(diǎn)x1 << xn ，編程計(jì)算在直線L 上最多設(shè)置k 處服務(wù)機(jī)構(gòu)的最小總費(fèi)用。數(shù)據(jù)輸入：文件夾data中的各輸入文件第1 行有2 個(gè)正整數(shù)n和k。n表示直線L 上有n 個(gè)點(diǎn)x1 << xn ；k 是服務(wù)機(jī)構(gòu)總數(shù)的上限。接下來的n行中，每行有3 個(gè)整數(shù)。第i+1行的3個(gè)整

13、數(shù)xi , w i , c i ，分別表示相應(yīng)居民點(diǎn)的位置坐標(biāo)，服務(wù)需求量和在該點(diǎn)設(shè)置服務(wù)機(jī)構(gòu)的費(fèi)用。結(jié)果輸出:將計(jì)算的最小服務(wù)費(fèi)用輸出到文件output.out。輸入文件示例 輸出文件示例kml0.in output0.out9 3 192 1 23 2 16 3 37 1 19 3 215 1 616 2 118 1 219 1 12.2問題分析本題是求最優(yōu)解的問題，考慮用動(dòng)態(tài)規(guī)劃算法。在直線L上增設(shè)k處服務(wù)機(jī)構(gòu)，設(shè)xt為我們?cè)鲈O(shè)的第一個(gè)服務(wù)機(jī)構(gòu)，則問題轉(zhuǎn)化為x0到x(t-1)的最小費(fèi)用。我們計(jì)算x0到xn曾設(shè)k個(gè)（設(shè)置k+1個(gè)點(diǎn)）是最優(yōu)的，必須xt到xn增設(shè)k-1（設(shè)置k個(gè)點(diǎn)）也是最優(yōu)的

14、。我們引入數(shù)組cij表示最小服務(wù)轉(zhuǎn)移費(fèi)用，其中i表示直線L上點(diǎn)xi處已設(shè)置了i個(gè)服務(wù)機(jī)構(gòu)，j表示在xi后面設(shè)置j處服務(wù)機(jī)構(gòu)。我們的問題轉(zhuǎn)化為求c0k+1。計(jì)算出所有兩點(diǎn)之間的距離d(i,j),并計(jì)算出之間的服務(wù)轉(zhuǎn)移費(fèi)m(i,j).設(shè)L上有n個(gè)點(diǎn)，在點(diǎn)xi處已設(shè)置了服務(wù)機(jī)構(gòu)，現(xiàn)在要xi后設(shè)置j個(gè)服務(wù)機(jī)構(gòu)（包括xi那個(gè)），使得整體服務(wù)轉(zhuǎn)移費(fèi)用最小，根據(jù)地推公式，容易求出c0k+1的遞推公式。Ans=2100000000;i=prev+1;temp=0;tempcur=cur2.3算法設(shè)計(jì)YNDepth=ki<nTempcur+=ri.c;j=prev+1j<iYNdepth=0|(de

15、pth!=0&&ri.x+rprev.x<rj.x*2)tempcur+=(ri.x-rj.x)*rj.w;j=i+1tempcur+=(rj.x-rprev.x)*rj.w;j<ntemp+=(rj.x-ri.x)*rj.w;tempcur+temp<ansans=tempcur+temp;dfs(depth+1,i,tempcur);i+;j+2.4復(fù)雜性分析根據(jù)遞推公式，容易求出c0k+1的遞推式。時(shí)間復(fù)雜度為O（nlog2n）。2.5總結(jié)設(shè)xt是增設(shè)的第一個(gè)服務(wù)站，總的服務(wù)費(fèi)用等于x1xt-1到x0的服務(wù)費(fèi)用W1加上后面一段xtxn增設(shè)k個(gè)服務(wù)站的費(fèi)用

16、W2是最優(yōu)的。證明使用反正打，如果這后面一段服務(wù)費(fèi)用W2不是最優(yōu)的，假設(shè)存在某種增設(shè)方法得到后一段服務(wù)費(fèi)用W2<W2，則W2-W1<W2-W1，所以得到原來的設(shè)置方法不是最優(yōu)解，這與題設(shè)矛盾，所以后面一段必須是最優(yōu)的。2.6附錄#include <stdio.h>struct res int x,w,c;FILE* fp;int n,k;int ans=2100000000;struct res r10;void dfs(int depth,int prev,int cur) int i,j; if(depth=k)return; for(i=prev+1;i<n

17、;i+) int temp=0,tempcur=cur; tempcur+=ri.c; for(j=prev+1;j<i;j+) if(depth=0|(depth!=0&&ri.x+rprev.x<rj.x*2)tempcur+=(ri.x-rj.x)*rj.w; else tempcur+=(rj.x-rprev.x)*rj.w; for(j=i+1;j<n;j+) temp+=(rj.x-ri.x)*rj.w; if(tempcur+temp<ans)ans=tempcur+temp; dfs(depth+1,i,tempcur); int main() int i; fp=fopen("kml0.in&qu