算法分析習(xí)題課 第三章 李承乾

1、算法分析習(xí)題選講(第三章)李承乾第三章 1152 1153 馬周游 1093 Air Express 1134 積木分發(fā) 1140 國(guó)王的遺產(chǎn) 1438 Shopaholic 1028 Hanoi Tower Sequence 1029 Rabbit 1381 a*b 1206 1012 Stacking Cylinders 1172 Queens, Knights and Pawns 1034 Forest第三章 1193 Up the Stairs 1004 I Conduit! 1017 Rate of Return 1059 Exocenter of a Trian 1003 Hit

2、or Miss 1018 A Card Trick 1052 Candy Sharing Game 1041 Pushing Boxes 1211 商人的宣傳 1071 Floors 1082 MANAGER1152 1153 馬周游 題目大意: 一個(gè)有限大小的棋盤(pán)上有一只馬，馬只能按日字方式走，如圖所示。 給出初始時(shí)馬的位置，找出一條馬移動(dòng)的路線，經(jīng)過(guò)所有格子各一次。解題思路 枚舉馬能走的所有路徑， 直至找到一條完成周游的路徑； 遞歸，回溯。 bool solve(int x, int y, int lev) routelev = x * N + y;if (lev = M * N - 1)

3、 print_route();return true;visitedxy = true;grid grids8;int n=get_grid(grids,x,y);for (i=0; in; i+) if (solve(gridsi.x, gridsi.y, lev+1) return true;visitedxy = false;return false; int get_grid(grid grids, int x,int y) int n=0;for (int i=0; i=0&yy=0&xxM&yyN &!visitedxxyy) gridsn.x =

4、xx;gridsn.y = yy;n+; return n; 優(yōu)化 以上程序速度過(guò)慢。 優(yōu)化：改變搜索順序。 先搜索可行格較少的格子。 其他順序。 修改get_grid()函數(shù)。 int get_grid(grid grids, int x,int y) int n=0;for (int i=0; i=0&yy=0&xxM&yyN &!visitedxxyy) gridsn.x = xx; gridsn.y = yy;gridsn.count = get_count(xx, yy);n+;sort(grids,grids+n);return n; bool op

5、erator (const grid &a, const grid &b) return a.count b.count; int get_count(int x, int y) int i, xx, yy, count = 0;for (i=0; i=0&yy=0&xxM&yyN&!visitedxxyy) count+;return count; 1093 Air Express 給出4個(gè)重量區(qū)間以及在每個(gè)區(qū)間的單位重量運(yùn)輸價(jià)格，再給出一個(gè)背包重量，可以往背包里添加任意多重量，求最低的總運(yùn)輸價(jià)格。 所有數(shù)字不超過(guò)1000。 Package w

6、eight Cost per pound 0 to 9 pounds $10 10 to 49 pounds $5 50 to 99 pounds $3 100 pounds or more $2解題思路 最小運(yùn)輸價(jià)格必定出現(xiàn)在： 1、不添加任何重量； 2、添加重量剛好到達(dá)某個(gè)區(qū)間的下界； 因此枚舉這些情況，并求出其中的最小值即是答案。 int cal(int weight) int price=INF;for (int i=0;i=li&weight=ri) if (weigth*rateiprice)price=weight*ratei; else if (weightli) if

7、 (li*rateiprice)price=li*ratei;return price; 1134 積木分發(fā) 一個(gè)人手上有s塊積木，一共有n個(gè)小朋友，每個(gè)小朋友手上有a塊積木，還需要b塊積木才能完成。當(dāng)一個(gè)小朋友的積木完成后則全部回收利用。問(wèn)是否所有小朋友都能完成。 s=1000000,n=10000,a,b=109解題思路 盡量先滿足需求少的小朋友，以回收得到更多積木； 因此按小朋友的需求排序，貪心求解。 struct child int a,b; ; bool operator (const child &x,cont child &y) return x.by.b; bo

8、ol check(child children,int s,int n) sort(children, children+n);for (int i=0;in;i+) if (schildreni.b)return false;s+=childreni.a;return true; 1140 國(guó)王的遺產(chǎn) n塊金塊組成一棵樹(shù)，總共k個(gè)人，每個(gè)人選擇樹(shù)里的一條邊去掉，得到不超過(guò)當(dāng)前金塊的一半的部分，并且分割使自己得到盡量多的金塊，如果相等則使金塊組編號(hào)最小。輸出每個(gè)人得到的金塊數(shù)量。 n=30000,k=100解題思路 枚舉每個(gè)人的時(shí)候，檢查切斷每一條邊所得到的金塊數(shù)和組編號(hào)，并得到最大金塊數(shù)和最

9、小組編號(hào)。 切斷每條邊后，得到一棵子樹(shù)，可計(jì)算得到子樹(shù)節(jié)點(diǎn)數(shù)和最小編號(hào)； 若每次從最小編號(hào)節(jié)點(diǎn)開(kāi)始遞歸，則可以輕易比較子樹(shù)的組編號(hào)以及它的補(bǔ)圖的組編號(hào)。 記錄子樹(shù)的大小，刪除的邊的兩個(gè)端點(diǎn)，子樹(shù)中的最小編號(hào) 用vector來(lái)保存樹(shù)的邊不同子樹(shù)之間的比較主過(guò)程 找出樹(shù)中的最小編號(hào)，從該編號(hào)開(kāi)始DFS1438 Shopaholic 買(mǎi)東西每買(mǎi)三件東西則最便宜的一件免費(fèi)。給出n個(gè)需要買(mǎi)的東西的價(jià)格，問(wèn)最多能免費(fèi)多少？ n=0;i-=3)s+=pricei;1028 Hanoi Tower Sequence 定義漢諾塔，共有三個(gè)柱子和很多的大小兩兩不同的盤(pán)子放在一個(gè)柱子上，要求把它們移到另一個(gè)柱子上，

10、每次只能移動(dòng)一個(gè)放在柱子最頂端的盤(pán)子，并且每次移動(dòng)后需保證較小的盤(pán)子在較大的盤(pán)子上面。給出步數(shù)p，求第p步移動(dòng)的盤(pán)子的大小。 p1)個(gè)盤(pán)子需要f(k)=f(k-1)+1+f(k-1)步。 即得到f(k)=2k-1。因此第2k步移動(dòng)的是k+1個(gè)盤(pán)子。在移動(dòng)第k+1個(gè)盤(pán)子后，左右對(duì)移地移動(dòng)k個(gè)盤(pán)子 把p化成二進(jìn)制數(shù)，假設(shè)現(xiàn)在p里有超過(guò)1個(gè)位為1，設(shè)最高位為k，則在2k步前和2k步后對(duì)稱(chēng)，因此第p步移的盤(pán)子與第p-2k步移的盤(pán)子一樣。 直到p里只有1個(gè)位為1，設(shè)此時(shí)p=2m，則此步移動(dòng)的是第m+1個(gè)盤(pán)子。 因此題目轉(zhuǎn)化成二進(jìn)制數(shù)p，從低位起連續(xù)0的位數(shù)，加1，為答案。 int cal(int a,i

11、nt n) int cnt=1;while (an-1%2=0) cnt+;for (int i=0,temp=0;in;i+) temp=temp*10+ai;ai=temp/2;temp%=2;return cnt; 1029 Rabbit 題目大意： 開(kāi)始有一對(duì)大兔子。每對(duì)大兔子每個(gè)月產(chǎn)生一對(duì)小兔子。每對(duì)小兔子經(jīng)過(guò)m個(gè)月變成大兔子。問(wèn)經(jīng)過(guò)d個(gè)月后有多少兔子。 1=m=10, 1=d=100解題思路 當(dāng)m=1時(shí)，每個(gè)月的兔子數(shù)量是上個(gè)月的兩倍，經(jīng)過(guò)d=100個(gè)月兔子將有2100個(gè)兔子，超過(guò)64位整數(shù)表示的范圍，因此要用高精度。 每個(gè)月的兔子數(shù)量，為上一個(gè)月的兔子數(shù)量，加上上一個(gè)月的大兔子數(shù)

12、量，即m個(gè)月前的兔子數(shù)量，即an=an-1+an-m。 注意當(dāng)n-m為負(fù)數(shù)時(shí)，也有初始時(shí)存大的一對(duì)大兔子。主過(guò)程1381 a*b 給出兩個(gè)整數(shù)a和b，求a*b的結(jié)果。（題目描述有誤，可能有零） 0=a=10100,0=b=10000。解題思路 高精度，模擬豎式乘法。 從低位向高位逐位計(jì)算。 輸出時(shí)注意結(jié)果為0的情況。 另外，這兩個(gè)大整數(shù)程序都以10為進(jìn)位， 實(shí)際使用時(shí)可以用10000為進(jìn)位數(shù)，把4個(gè)數(shù)字壓在一個(gè)數(shù)組中，可以明顯提高程序效率。1206 1012 Stacking Cylinders 如圖所示，給出最底層的n個(gè)球的位置，求最頂層的球的位置。 1=n=10解題思路 關(guān)鍵點(diǎn)在于已知兩個(gè)

13、圓的圓心坐標(biāo)，求放在這兩個(gè)圓上的圓的圓心坐標(biāo)。 向量+勾股定理。 struct point double x,y;point()x=0;y=0;point(double a,double b)x=a;y=b;point operator - (point b)return point(x-b.x,y-b.y);point operator + (point b)return point(x+b.x,y+b.y);point operator / (double b)return point(x/b,y/b);point operator * (double b)return point(x*b

14、,y*b);double dis()return sqrt(x*x+y*y);void left()y=-y;swap(x,y); r1111; bool cmp(const point& a,const point &b) return a.x=0;i-) for(j=0;j=i;j+)rj=cal(rj,rj+1); return r0; 1172 Queens, Knights and Pawns 給出棋盤(pán)大小，給出每個(gè)后、馬和兵的位置，求棋盤(pán)上有多個(gè)個(gè)沒(méi)被占領(lǐng)的格子不會(huì)受到后也不會(huì)受到馬的攻擊。 棋盤(pán)大小最多為1000*1000，每種棋子最多100個(gè)。解題思路 用二維數(shù)

15、組表示一個(gè)棋盤(pán)，標(biāo)記每個(gè)棋子的位置，再標(biāo)記每個(gè)棋子能攻擊的位置，最后計(jì)算有多少個(gè)位置不會(huì)被攻擊。 enum grid_state empty,occupied,attacked; grid_state grid10011001; int cal(vector q, vector k, vector p) memset(grid,0,sizeof(grid);occupy(q); occupy(k); occupy(p);attackQ(q); attackK(k);int s=0;for (int i=1;i=row;i+)for (int j=1&p.x=1&p.y=col)

16、return gridp.xp.y!=occupied;return false; void occupy(vector v) for (int i=0;iv.size();i+)gridvi.xvi.y=occupied; int dQ82=1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,0,1,1,1; void attackQ(vector q) for (int i=0;iq.size();i+) for (int dir=0;dir8;dir+) point temp(qi.x+dQdir0,qi.y+dQdir1); while (in_board_and_unoccu

17、pied(temp) gridtemp.xtemp.y=attacked; temp=point(temp.x+dQdir0,temp.y+dQdir1; int dK82=1,2,1,-2,2,-1,-2,-1,-1,-2,-1,2,-2,1,2,1; void attackK(vector k) for (int i=0;ik.size();i+) for (int dir=0;dir8;dir+) point temp(ki.x+dKdir0,ki.y+dKdir1); if (in_board_and_unoccupied(temp) gridtemp.xtemp.y=attacked

18、; 1034 Forest 給出n個(gè)節(jié)點(diǎn)和m條有向邊，判斷是否組成森林，如果是則求出它的最大深度和最大寬度。 所有數(shù)不超過(guò)100解題思路 先判斷是否為森林： 沒(méi)有一個(gè)節(jié)點(diǎn)有兩條入邊，直接統(tǒng)計(jì)所有節(jié)點(diǎn)的入度； 沒(méi)有環(huán)，求圖的閉包。 再求解： 枚舉所有根，dfs得到最深節(jié)點(diǎn)和每個(gè)深度的節(jié)點(diǎn)數(shù)。 bool is_forest(int n) bool closure101101;for (i=1;i=n;i+) for (j=1,cnti=0;j1) return false;memcpy(closure,edge,sizeof(edge);for (i=1;i=n;i+) for (j=1;j=n;

19、j+) for (k=1;k=n;k+)if (closureki&closureij)closurekj=true;for (i=1;i=n;i+) if (closureii) return false;return true; int width101; void dfs(int k,int lev,int n) widthlev+;for (int i=1;i=n;i+) if (edgeki)dfs(i,lev+1,n); void cal(int n) for (int i=1;i=n;i+) if (cnti=0)dfs(i,0,n); 1193 Up the Stair

20、s N個(gè)人在F層之間搬箱子，開(kāi)始時(shí)每個(gè)人在某層樓上，有些手上已有箱子有些沒(méi)有。在第0層上還有B個(gè)箱子。拿著箱子的人向上走，沒(méi)拿箱子的向下走，當(dāng)兩個(gè)相遇時(shí)拿著箱子的人把箱子交給沒(méi)箱子的人，互換方向繼續(xù)。走到F層的人把箱子放下，走到0層的人拿起箱子。問(wèn)經(jīng)過(guò)多少時(shí)間所有箱子都在F層。 1=N,F=1000,1=B=1000000解題思路 兩個(gè)人交換箱子互換方向，相當(dāng)于沒(méi)有交換。 當(dāng)經(jīng)過(guò)2F時(shí)間后，所有人的狀態(tài)沒(méi)有改變，0層的其中N個(gè)箱子搬到了F層，因此先把B對(duì)N取模。 求出每個(gè)人從當(dāng)前狀態(tài)把0層的一個(gè)箱子搬到F層需要的時(shí)間，排序，B對(duì)N取模的余數(shù)就由最快的部分人來(lái)搬。 int cal() for (

21、i=0;in;i+) if (bi=0) tii=fi+F;else tii=3*F-fi;sort(ti,ti+N);int s=B/N*2*F;B%=N;if (B=0) B+=N;s-=2*F;s+=tiB-1;return s; 1004 I Conduit! 一個(gè)二維坐標(biāo)平面上有n條邊，如果兩條邊有重疊部分，則可以合并成一條邊。問(wèn)合并后的邊的數(shù)量。 n=10000，坐標(biāo)范圍為0.0, 1000.0解題思路 對(duì)平面上所有線段排序，保證在同一直線上的線段會(huì)集中在一段區(qū)間內(nèi)，并且它們按照從直線的一個(gè)方向到另一個(gè)方向排序。 線段：所在直線為y=kx+b或x=b，分情況討論。 排序后判斷在同一

22、直線上的線段哪些有重疊部分，一個(gè)線段的結(jié)束位置在另一個(gè)線段的起始位置之前，則它們有重疊。 #define INF1e+15 #define EPS1e-7 inline int dcmp( double x) if ( x EPS; struct Tline double k, b, pstart, pend; Tline toline (double x1, double y1, double x2, double y2) if ( dcmp ( x1-x2 ) = 0 ) k = INF, b = x1; pstart = min ( y1, y2 ) ; pend = max ( y1,

23、 y2 ) ; else k = ( y2 - y1 ) / ( x2 - x1 ), b = y1 - k * x1 ; pstart = min ( x1, x2 ) ; pend = max ( x1, x2 ) ; ; bool line_cmp ( const Tline& x, const Tline& y ) if (dcmp(x.k-y.k) != 0)return dcmp(x.k-y.k) 0;if (dcmp(x.b-y.b) != 0)return dcmp(x.b-y.b) 0;return dcmp(x.pstart-y.pstart) 0; int

24、 cal() sort(lines, lines + n, line_cmp); int i, ans = n; double maxreached = lines0.pend; for (i = 1; i n; i +) if (dcmp(linesi.k-linesi-1.k) = 0 & dcmp(linesi.b-linesi-1.b) = 0) if (dcmp(linesi.pstart-maxreached) = 0) ans -; maxreached = max( maxreached, linesi.pend ); else maxreached = linesi.

25、pend; return ans; 1017 Rate of Return 給出一個(gè)人在某些月份的開(kāi)始時(shí)增加的投資額，并給出在某個(gè)月份結(jié)束時(shí)本金和利潤(rùn)的總和。每個(gè)月的利潤(rùn)率是固定的。每個(gè)月增加的利潤(rùn)會(huì)自動(dòng)加入投資額。求利潤(rùn)率。利潤(rùn)率在0,1之間。 例如1月和3月開(kāi)始時(shí)各投資100元，4月底共得到210元，設(shè)利潤(rùn)率為x，則有方程： 100*(1+x)4 + 100*(1+x)2 = 210解題思路 當(dāng)利潤(rùn)率在0,1之間，假設(shè)投資額和時(shí)間不變，則利潤(rùn)率越高，最后的本金和利潤(rùn)總和越大。 因此對(duì)利潤(rùn)率進(jìn)行二分查找，檢查在假設(shè)的利潤(rùn)率下，比較最后的本金和利潤(rùn)總和與實(shí)際值，調(diào)整二分上下界，直到達(dá)到某個(gè)精度

26、。 double find(double a,double c,int m,double x) double b,s; while(a+epsc) b=(a+c)/2; for (int i=1,s=0;i=m;i+) s+=ai*pow(1.0+center,m+1-i); if (sx) a=b; else c=b; return a; 1059 Exocenter of a Trian 給出三角形ABC三點(diǎn)坐標(biāo)，如圖所示，作正方形ABDE，正方形BCHJ，正方形CAGF，L為DG中點(diǎn)，M為EJ中點(diǎn)，N為FH中點(diǎn)，直線LA，MB，NC交于同一點(diǎn)O，求點(diǎn)O的坐標(biāo)。解題思路 按照題意求出所有點(diǎn)

27、的坐標(biāo)。 需要的函數(shù)：向量旋轉(zhuǎn)，兩點(diǎn)中點(diǎn)，直線相交。 輔助函數(shù)：向量叉積。向量叉積 兩個(gè)向量u1和u2，若叉積小于0，表示u1在u2逆時(shí)針?lè)较?，叉積為0表示共線，叉積大于0表示u1在u2順時(shí)針?lè)较?。向量旋轉(zhuǎn) 把向量分解成平行于x坐標(biāo)軸和y坐標(biāo)軸的向量，再分別旋轉(zhuǎn)，最合把旋轉(zhuǎn)結(jié)果合并 CPoint rotate(CPoint& v, double angle) CPoint res; res.x = p.x * cos(angle) - p.y * sin(angle); res.y = p.x * sin(angle) + p.y * cos(angle); return res; 兩

28、點(diǎn)中點(diǎn) x和y坐標(biāo)的平均值。 CPoint middle(CPoint &a,CPoint &b) CPoint c;c.x=(a.x+b.x)/2.0;c.y=(a.y+b.y)/2.0;return c; 直線相交 Point cal() D=rotate(B-A, pi/2)+A;G=rotate(C-A,-pi/2)+A;L=middle(D,G);E=rotate(A-B,-pi/2)+B;J=rotate(C-B, pi/2)+B;M=middle(E,J);O=LineIntersection(L,A,M,B);return O; 1003 Hit or Miss

29、 一共有n個(gè)人，第一個(gè)人開(kāi)始時(shí)以一定順序拿著標(biāo)有1到13各4張的卡片堆。每個(gè)人分別執(zhí)行以下兩個(gè)步驟： 1、如果手上有卡，每次輪到自己則數(shù)一個(gè)數(shù)，從1開(kāi)始，在113內(nèi)循環(huán)，如果數(shù)的數(shù)剛好和自己的卡片堆最頂?shù)目ㄆ粯?，則丟棄這張卡片，否則把這張卡片放到卡片堆底； 2、除了第1個(gè)人，如果每個(gè)人前面的一個(gè)人有卡片丟棄，則把丟棄的卡片放到自己卡片堆底。 如此循環(huán)，直到每個(gè)人手上都沒(méi)有卡片，或不能終止。如果可以結(jié)束，則輸出每個(gè)人最后丟棄的卡片。解題思路 按照題意直接模擬。 當(dāng)循環(huán)次數(shù)超過(guò)最大卡片張數(shù)（52）仍沒(méi)有人拋棄卡片，則判斷不能終止。 struct player queue cards;int la

30、stcard, count;int step1() int discard=-1;if (!(cards.empty() int cur=cards.front();cards.pop();if (cur=count) lastcard=discard=cur;else cards.push(cur);if (count=13) count=1;else count+;return discard; ; void run() int lastround = 0;for (int round=1;round-lastround=52;round+) for (int i=0; in; i+) d

31、iscardsi = pi.step1();if (discardsi != -1)lastround=round;for (int i=1; in; i+)if (discardsi-1 != -1)pi.cards.push(discardsi-1); 1018 A Card Trick 一個(gè)魔術(shù)，助手把五張撲克的其中四張按一定順序給魔術(shù)師，魔術(shù)師可能通過(guò)一定的規(guī)則計(jì)算出剩余的一張撲克。 給出五張撲克，求出它們給魔術(shù)師的順序。解題思路 枚舉五張撲克的順序，找出其中合法的。 按照題目描述的規(guī)則模擬。 struct card int num;char suit; ; bool operator

32、 (const card &a,const card &b) if (a.num!=b.num)return a.numb.num;elsereturn a.suitb.suit; bool check() if (cards0.suit!=cards1.suit) return false; int result=0,min=2,max=2; for (int i=3;i5;i+) if (cardsicardsmax) max=i; int middle=2+3+4-min-max; result+=min-1; if (middlemax) result+=3; retu

33、rn cards0.num%13=(cards1.num+result)%13; void run() sort(cards,cards+5);while (true)if (check()break;next_permutation(cards,cards+5); 1052 Candy Sharing Game M個(gè)學(xué)生圍成一圈，開(kāi)始時(shí)所有學(xué)生都有偶數(shù)的糖。每個(gè)回合，所有學(xué)生同時(shí)把手里的一半糖傳給右邊的學(xué)生，如果某個(gè)學(xué)生的糖數(shù)為奇數(shù)，則老師多給他一個(gè)糖。直到所有學(xué)生的糖數(shù)目相等則結(jié)束。求回合數(shù)和每個(gè)學(xué)生手里的糖數(shù)。解題思路 直接按照題目模擬。 for (round=0;!allsame();

34、round+) for (int i=0;im;i+)bi=ai=ai/2;for (int i=0;im;i+) a(i+1)%m+=bi;a(i+1)%m+=a(i+1)%m%2; 1041 Pushing Boxes 一間長(zhǎng)方形房間里有一些箱子，每次操作為房間的其中一面墻向里移動(dòng)，把其中的箱子推到新的位置。求最后箱子的位置。解題思路 思路1： 分上下左右四種情況分別考慮。 按照題目描述模擬。 思路2： 只考慮一個(gè)方向。 在移動(dòng)其它方向時(shí)，把房間旋轉(zhuǎn)至默認(rèn)方向，移動(dòng)后再旋轉(zhuǎn)回原來(lái)的方向。 bool cmpright(const pos &a,const pos &b) if (a.x!=b.x) return a.xb.x;else return a.yb.y; void moveright(int m) sort(box,box+n,cmpright);int x=-1,y;for (int i=0;in;i+) if (boxi.x!=x) x=boxi.x;y=m;else y+;if (boxi.yy) boxi.y=y; 1211 商人的宣傳 有n個(gè)州，m條單向邊，規(guī)定天數(shù)為L(zhǎng)。 共有q個(gè)詢問(wèn)，每個(gè)詢問(wèn)為從州A到州B剛好為L(zhǎng)步的方案數(shù)。解題思路 第0天，每個(gè)州到自己的方案數(shù)為1。 第n+1天，每個(gè)州A到另一個(gè)州B的方案數(shù)為，對(duì)所有