算法分析習題課 第三章 李承乾

1、算法分析習題選講(第三章)李承乾第三章 1152 1153 馬周游 1093 Air Express 1134 積木分發(fā) 1140 國王的遺產 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 馬周游 題目大意: 一個有限大小的棋盤上有一只馬，馬只能按日字方式走，如圖所示。 給出初始時馬的位置，找出一條馬移動的路線，經過所有格子各一次。解題思路 枚舉馬能走的所有路徑， 直至找到一條完成周游的路徑； 遞歸，回溯。 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)化 以上程序速度過慢。 優(yōu)化：改變搜索順序。 先搜索可行格較少的格子。 其他順序。 修改get_grid()函數。 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個重量區(qū)間以及在每個區(qū)間的單位重量運輸價格，再給出一個背包重量，可以往背包里添加任意多重量，求最低的總運輸價格。 所有數字不超過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解題思路 最小運輸價格必定出現在： 1、不添加任何重量； 2、添加重量剛好到達某個區(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ā) 一個人手上有s塊積木，一共有n個小朋友，每個小朋友手上有a塊積木，還需要b塊積木才能完成。當一個小朋友的積木完成后則全部回收利用。問是否所有小朋友都能完成。 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 國王的遺產 n塊金塊組成一棵樹，總共k個人，每個人選擇樹里的一條邊去掉，得到不超過當前金塊的一半的部分，并且分割使自己得到盡量多的金塊，如果相等則使金塊組編號最小。輸出每個人得到的金塊數量。 n=30000,k=100解題思路 枚舉每個人的時候，檢查切斷每一條邊所得到的金塊數和組編號，并得到最大金塊數和最

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

10、每次只能移動一個放在柱子最頂端的盤子，并且每次移動后需保證較小的盤子在較大的盤子上面。給出步數p，求第p步移動的盤子的大小。 p1)個盤子需要f(k)=f(k-1)+1+f(k-1)步。 即得到f(k)=2k-1。因此第2k步移動的是k+1個盤子。在移動第k+1個盤子后，左右對移地移動k個盤子 把p化成二進制數，假設現在p里有超過1個位為1，設最高位為k，則在2k步前和2k步后對稱，因此第p步移的盤子與第p-2k步移的盤子一樣。 直到p里只有1個位為1，設此時p=2m，則此步移動的是第m+1個盤子。 因此題目轉化成二進制數p，從低位起連續(xù)0的位數，加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 題目大意： 開始有一對大兔子。每對大兔子每個月產生一對小兔子。每對小兔子經過m個月變成大兔子。問經過d個月后有多少兔子。 1=m=10, 1=d=100解題思路 當m=1時，每個月的兔子數量是上個月的兩倍，經過d=100個月兔子將有2100個兔子，超過64位整數表示的范圍，因此要用高精度。 每個月的兔子數量，為上一個月的兔子數量，加上上一個月的大兔子數

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

13、圓的圓心坐標，求放在這兩個圓上的圓的圓心坐標。 向量+勾股定理。 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 給出棋盤大小，給出每個后、馬和兵的位置，求棋盤上有多個個沒被占領的格子不會受到后也不會受到馬的攻擊。 棋盤大小最多為1000*1000，每種棋子最多100個。解題思路 用二維數

15、組表示一個棋盤，標記每個棋子的位置，再標記每個棋子能攻擊的位置，最后計算有多少個位置不會被攻擊。 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個節(jié)點和m條有向邊，判斷是否組成森林，如果是則求出它的最大深度和最大寬度。 所有數不超過100解題思路 先判斷是否為森林： 沒有一個節(jié)點有兩條入邊，直接統計所有節(jié)點的入度； 沒有環(huán)，求圖的閉包。 再求解： 枚舉所有根，dfs得到最深節(jié)點和每個深度的節(jié)點數。 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個人在F層之間搬箱子，開始時每個人在某層樓上，有些手上已有箱子有些沒有。在第0層上還有B個箱子。拿著箱子的人向上走，沒拿箱子的向下走，當兩個相遇時拿著箱子的人把箱子交給沒箱子的人，互換方向繼續(xù)。走到F層的人把箱子放下，走到0層的人拿起箱子。問經過多少時間所有箱子都在F層。 1=N,F=1000,1=B=1000000解題思路 兩個人交換箱子互換方向，相當于沒有交換。 當經過2F時間后，所有人的狀態(tài)沒有改變，0層的其中N個箱子搬到了F層，因此先把B對N取模。 求出每個人從當前狀態(tài)把0層的一個箱子搬到F層需要的時間，排序，B對N取模的余數就由最快的部分人來搬。 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! 一個二維坐標平面上有n條邊，如果兩條邊有重疊部分，則可以合并成一條邊。問合并后的邊的數量。 n=10000，坐標范圍為0.0, 1000.0解題思路 對平面上所有線段排序，保證在同一直線上的線段會集中在一段區(qū)間內，并且它們按照從直線的一個方向到另一個方向排序。 線段：所在直線為y=kx+b或x=b，分情況討論。 排序后判斷在同一

22、直線上的線段哪些有重疊部分，一個線段的結束位置在另一個線段的起始位置之前，則它們有重疊。 #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 給出一個人在某些月份的開始時增加的投資額，并給出在某個月份結束時本金和利潤的總和。每個月的利潤率是固定的。每個月增加的利潤會自動加入投資額。求利潤率。利潤率在0,1之間。 例如1月和3月開始時各投資100元，4月底共得到210元，設利潤率為x，則有方程： 100*(1+x)4 + 100*(1+x)2 = 210解題思路 當利潤率在0,1之間，假設投資額和時間不變，則利潤率越高，最后的本金和利潤總和越大。 因此對利潤率進行二分查找，檢查在假設的利潤率下，比較最后的本金和利潤總和與實際值，調整二分上下界，直到達到某個精度

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三點坐標，如圖所示，作正方形ABDE，正方形BCHJ，正方形CAGF，L為DG中點，M為EJ中點，N為FH中點，直線LA，MB，NC交于同一點O，求點O的坐標。解題思路 按照題意求出所有點

27、的坐標。 需要的函數：向量旋轉，兩點中點，直線相交。 輔助函數：向量叉積。向量叉積 兩個向量u1和u2，若叉積小于0，表示u1在u2逆時針方向，叉積為0表示共線，叉積大于0表示u1在u2順時針方向。向量旋轉 把向量分解成平行于x坐標軸和y坐標軸的向量，再分別旋轉，最合把旋轉結果合并 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、點中點 x和y坐標的平均值。 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個人，第一個人開始時以一定順序拿著標有1到13各4張的卡片堆。每個人分別執(zhí)行以下兩個步驟： 1、如果手上有卡，每次輪到自己則數一個數，從1開始，在113內循環(huán)，如果數的數剛好和自己的卡片堆最頂的卡片一樣，則丟棄這張卡片，否則把這張卡片放到卡片堆底； 2、除了第1個人，如果每個人前面的一個人有卡片丟棄，則把丟棄的卡片放到自己卡片堆底。 如此循環(huán)，直到每個人手上都沒有卡片，或不能終止。如果可以結束，則輸出每個人最后丟棄的卡片。解題思路 按照題意直接模擬。 當循環(huán)次數超過最大卡片張數（52）仍沒有人拋棄卡片，則判斷不能終止。 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 一個魔術，助手把五張撲克的其中四張按一定順序給魔術師，魔術師可能通過一定的規(guī)則計算出剩余的一張撲克。 給出五張撲克，求出它們給魔術師的順序。解題思路 枚舉五張撲克的順序，找出其中合法的。 按照題目描述的規(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個學生圍成一圈，開始時所有學生都有偶數的糖。每個回合，所有學生同時把手里的一半糖傳給右邊的學生，如果某個學生的糖數為奇數，則老師多給他一個糖。直到所有學生的糖數目相等則結束。求回合數和每個學生手里的糖數。解題思路 直接按照題目模擬。 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 一間長方形房間里有一些箱子，每次操作為房間的其中一面墻向里移動，把其中的箱子推到新的位置。求最后箱子的位置。解題思路 思路1： 分上下左右四種情況分別考慮。 按照題目描述模擬。 思路2： 只考慮一個方向。 在移動其它方向時，把房間旋轉至默認方向，移動后再旋轉回原來的方向。 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個州，m條單向邊，規(guī)定天數為L。 共有q個詢問，每個詢問為從州A到州B剛好為L步的方案數。解題思路 第0天，每個州到自己的方案數為1。 第n+1天，每個州A到另一個州B的方案數為，對所有