算法分析习题课 第三章 李承乾

1、算法分析习题选讲(第三章)李承乾第三章 1152 1153 马周游 1093 Air Express 1134 积木分发 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; 优化 以上程序速度过慢。 优化：改变搜索顺序。 先搜索可行格较少的格子。 其他顺序。 修改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个重量区间以及在每个区间的单位重量运输价格，再给出一个背包重量，可以往背包里添加任意多重量，求最低的总运输价格。 所有数字不超过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、添加重量刚好到达某个区间的下界； 因此枚举这些情况，并求出其中的最小值即是答案。 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 积木分发 一个人手上有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、小组编号。 切断每条边后，得到一棵子树，可计算得到子树节点数和最小编号； 若每次从最小编号节点开始递归，则可以轻易比较子树的组编号以及它的补图的组编号。 记录子树的大小，删除的边的两个端点，子树中的最小编号 用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，从低位起连续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个节点和m条有向边，判断是否组成森林，如果是则求出它的最大深度和最大宽度。 所有数不超过100解题思路 先判断是否为森林： 没有一个节点有两条入边，直接统计所有节点的入度； 没有环，求图的闭包。 再求解： 枚举所有根，dfs得到最深节点和每个深度的节点数。 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个箱子。拿着箱子的人向上走，没拿箱子的向下走，当两个相遇时拿着箱子的人把箱子交给没箱子的人，互换方向继续。走到F层的人把箱子放下，走到0层的人拿起箱子。问经过多少时间所有箱子都在F层。 1=N,F=1000,1=B=1000000解题思路 两个人交换箱子互换方向，相当于没有交换。 当经过2F时间后，所有人的状态没有改变，0层的其中N个箱子搬到了F层，因此先把B对N取模。 求出每个人从当前状态把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解题思路 对平面上所有线段排序，保证在同一直线上的线段会集中在一段区间内，并且它们按照从直线的一个方向到另一个方向排序。 线段：所在直线为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张的卡片堆。每个人分别执行以下两个步骤： 1、如果手上有卡，每次轮到自己则数一个数，从1开始，在113内循环，如果数的数刚好和自己的卡片堆最顶的卡片一样，则丢弃这张卡片，否则把这张卡片放到卡片堆底； 2、除了第1个人，如果每个人前面的一个人有卡片丢弃，则把丢弃的卡片放到自己卡片堆底。 如此循环，直到每个人手上都没有卡片，或不能终止。如果可以结束，则输出每个人最后丢弃的卡片。解题思路 按照题意直接模拟。 当循环次数超过最大卡片张数（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 一个魔术，助手把五张扑克的其中四张按一定顺序给魔术师，魔术师可能通过一定的规则计算出剩余的一张扑克。 给出五张扑克，求出它们给魔术师的顺序。解题思路 枚举五张扑克的顺序，找出其中合法的。 按照题目描述的规则模拟。 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条单向边，规定天数为L。 共有q个询问，每个询问为从州A到州B刚好为L步的方案数。解题思路 第0天，每个州到自己的方案数为1。 第n+1天，每个州A到另一个州B的方案数为，对所有