




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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的方案數為,對所有
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 兒科靜脈護理缺陷管理要點
- 2024屆河南省信陽市浉河區(qū)第九中學中考數學模試卷含解析
- 新員工入職培訓與成長計劃
- 體育特長生專項訓練計劃
- 護理專家課件
- 部門經理管理能力提升培訓計劃
- 幼兒園疫情期間教師培訓計劃
- 十年(2014-2023)高考化學真題分項匯編(全國)專題42 反應熱計算-蓋斯定律(含答案或解析)
- 分娩后傷口護理指南
- 中小學生視力保護的有效措施
- 小學新課標《義務教育數學課程標準(2022年版)》新修訂解讀課件
- 七年級下學期語文5月月考試卷
- 2024年樂山市市級事業(yè)單位選調工作人員真題
- 社區(qū)衛(wèi)生服務與試題及答案
- 補單合同范本10篇
- 心血管-腎臟-代謝綜合征患者的綜合管理中國專家共識2025解讀-2
- 護工技能大賽試題及答案
- 機械制造自動化技術工業(yè)機器人
- 貨物居間協議合同協議
- 三年級美術下冊《認識圖形標志》課件
- 湖南省2024年對口升學考試計算機綜合真題試卷
評論
0/150
提交評論