《算法分析与设计：习题选讲第五章》由会员分享，可在线阅读，更多相关《算法分析与设计：习题选讲第五章（33页珍藏版）》请在金锄头文库上搜索。
1、习题选讲习题选讲2011-12-222第五章第五章n1317 Sudokun1215 脱离地牢脱离地牢n1050 Numbers & Lettersn1171 The Game of Efiln1219 新红黑树新红黑树n1048 Inverson1135 飞越原野飞越原野n1107 Simple Puzzle2011-12-2231317 Sudokun题目大意：题目大意：n给出一个未完成的数给出一个未完成的数独，问这个数独有多独，问这个数独有多少个解。少个解。2011-12-2241317 Sudokun解题思路：解题思路：n规则就是用规则就是用19的数字把空格填满，使得的数字把空格填满，
2、使得9行，行，9列以及列以及9个小的个小的33方格内都有方格内都有19这这9个数字。个数字。 n使用深度优先搜索使用深度优先搜索+剪枝。剪枝。2011-12-2251317 Sudokun暴力搜索：暴力搜索：n按照格子顺序，枚举每个格子可能出现的按照格子顺序，枚举每个格子可能出现的数字，如果发现矛盾则回溯。直到找出所数字，如果发现矛盾则回溯。直到找出所有解。有解。n绝对会超时。绝对会超时。2011-12-2262011-12-2271317 Sudokun剪枝：剪枝：n使用数独技巧。搜索时，对每个格子，根使用数独技巧。搜索时，对每个格子，根据同行同列和同小方格已有的数字，判断据同行同列和同小方
3、格已有的数字，判断当前格子可能填上的数字，如果只有一个当前格子可能填上的数字，如果只有一个数字可填，则可以马上填上。数字可填，则可以马上填上。n仍然会超时。仍然会超时。2011-12-2281317 Sudokun另一个剪枝：另一个剪枝：n如果有个数字在某一行某一列某个小方格如果有个数字在某一行某一列某个小方格里面只找到里面只找到1个位置，则可以马上填上。个位置，则可以马上填上。n加上这个剪枝即可通过。加上这个剪枝即可通过。nhttp:/222.200.182.58/viewsource.php?sid=806782011-12-2291215 脱离地牢脱离地牢n题目大意：题目大意：n有两个人
4、在一个地牢里，里面有墙壁也有有两个人在一个地牢里，里面有墙壁也有熔浆。当一个人向某个方向移动时，另一熔浆。当一个人向某个方向移动时，另一个人会向另一个方向移动。如果遇到墙壁个人会向另一个方向移动。如果遇到墙壁则不能前进，如到熔浆则任务失败。问使则不能前进，如到熔浆则任务失败。问使两个人相遇最少需要多少步。两个人相遇最少需要多少步。2011-12-22101215 脱离地牢脱离地牢n解题思路：解题思路：n从初始状态开始进行从初始状态开始进行bfs，状态为两个人分别的位，状态为两个人分别的位置。置。n一个状态，可以通过一个人向东南西北四个方向一个状态，可以通过一个人向东南西北四个方向移动，同时另外
5、一个人也跟着移动，到达新状态。移动，同时另外一个人也跟着移动，到达新状态。n重复状态不加入队列。重复状态不加入队列。n直到两个人相遇。直到两个人相遇。nhttp:/222.200.182.58/viewsource.php?sid=870552011-12-22111171 The Game of Efiln题目大意：题目大意：n一块一块m*n大小的板上，有一些细菌。如果一个细大小的板上，有一些细菌。如果一个细菌的八个方向上邻居细菌数是菌的八个方向上邻居细菌数是2或或3，则在下一个，则在下一个回合它能保留下来，否则它会消失。如果有一个回合它能保留下来，否则它会消失。如果有一个空格的邻居细菌数为
6、空格的邻居细菌数为3，则下一回合长出新的细菌。，则下一回合长出新的细菌。板的上下边是连通的，左右边是连通的。给出一板的上下边是连通的，左右边是连通的。给出一个板的当前状态，问上一个回合的状态有多少不个板的当前状态，问上一个回合的状态有多少不同的情况。同的情况。nm*n=162011-12-22121171 The Game of Efiln解题思路：解题思路：n枚举出每种状态，按照规则生成下一步状枚举出每种状态，按照规则生成下一步状态，并与输入状态比较，相等则答案数加态，并与输入状态比较，相等则答案数加一。一。n因为最多有因为最多有16个格子，因此最多有个格子，因此最多有216个个状态。状态。
7、n枚举状态用枚举状态用dfs。2011-12-22131171 The Game of Efilnvoid dfs(int x,int y) nif (x=m) ncal();nreturn;nndxy=0;nif (y=n-1) dfs(x+1,0);nelse dfs(x,y+1);ndxy=1;nif (y=n-1) dfs(x+1,0);nelse dfs(x,y+1);n2011-12-22141171 The Game of Efilnvoid cal() n int i,j,k,temp,t;n for (i=0;im;i+)n for (j=0;jn;j+) n temp=0;
8、n for (k=0;k8;k+)n if (d(i+dxk+m)%m(j+dyk+n)%n)n temp+;n if (temp=3) t=1;n else if (dij=1&temp=2) t=1;n else t=0;n if (strdij!=t)n return;n n ans+;n return;n2011-12-22151219 新红黑树新红黑树n题目大意：题目大意：n一棵树由红枝和黑枝组成的树，一棵树由红枝和黑枝组成的树，A和和B轮流轮流砍树，砍树，A只砍红枝，只砍红枝，B只砍黑枝。砍枝后不只砍黑枝。砍枝后不与根相连的枝都去掉。每个树枝上有权值，与根相连的枝都去掉。每个树枝上
9、有权值，砍掉的枝的权值加到自己的分数上。砍掉的枝的权值加到自己的分数上。A想使想使A-B之差越高越好，之差越高越好，B想它越低越好。在最想它越低越好。在最佳策略下佳策略下A-B之差。之差。n树枝树不超过树枝树不超过20。2011-12-22161219 新红黑树新红黑树n解题思路：解题思路：n这题是博弈题，可以看作在博弈树上进行深搜，这题是博弈题，可以看作在博弈树上进行深搜，并根据两人的策略取最大值或最小值。并根据两人的策略取最大值或最小值。n博弈状态有重复，状态只包括，当前剩下的树枝，博弈状态有重复，状态只包括，当前剩下的树枝，和轮到谁砍树枝。和轮到谁砍树枝。n使用记忆化搜索。使用记忆化搜索
10、。n预处理砍掉每个树枝会使哪些其它树枝消失。预预处理砍掉每个树枝会使哪些其它树枝消失。预处理使用处理使用dfs。n位操作。位操作。2011-12-22171219 新红黑树新红黑树nint dfs(int k) nint i,temp=0;nvisk=1;nfor (i=0;in;i+) nif (bi=k)nswap(ai,bi);nif (ai=k&visbi=0) ncuti=(dfs(bi)|(1i);ntemp|=cuti;nnnreturn temp;n2011-12-22181219 新红黑树新红黑树nint cal(int z,int t) nint i,tt,temp;nif
11、 (z=0) return 0;ntt=(t+1)/2;nif (dttz) return recttz;nfor (i=0;in;i+) nif (ci=t&(z&(1recttz*t) ndttz=1;nrecttz=temp;nnnnif (!dttz) dttz=1; recttz=cal(z,-t); nreturn recttz;n2011-12-22191048 Inverson题目大意：题目大意：n给出一个给出一个3*3棋盘，每个格子是黑色或白色。棋盘，每个格子是黑色或白色。每个格子有一个按钮，按这个按钮会使自每个格子有一个按钮，按这个按钮会使自己和周围己和周围8个方向的格子颜
12、色反转。问最少个方向的格子颜色反转。问最少需要多少步使所有格子变成白色，输出最需要多少步使所有格子变成白色，输出最小的序列。小的序列。2011-12-22201048 Inverson解题思路：解题思路：n任何一个按钮按两次以上都是没用的，因任何一个按钮按两次以上都是没用的，因为按两次的作用互相抵消了。为按两次的作用互相抵消了。n枚举每个格子按或者不按，判断是否能使枚举每个格子按或者不按，判断是否能使所有格子变成白色，如果可以，则取所有所有格子变成白色，如果可以，则取所有方案的最小值。方案的最小值。n需要特判，初始时全部格子为白色。需要特判，初始时全部格子为白色。2011-12-2221104
13、8 Inversonvoid dfs(int grid,int cnt) nif (grid9) ntempanscnt=0;nif (allwhite()&better(tempans,ans)nstrcpy(ans,tempans);nreturn;nndfs(grid+1,cnt);nflip(grid);ntempanscnt=grid+0;ndfs(grid+1,cnt+1);nreturn;n2011-12-22221135 飞越原野飞越原野n题目大意：题目大意：n在在m*n的平面上，有一个德鲁伊，可以用的平面上，有一个德鲁伊，可以用1的时间向四个方向走一步，或用的时间向四个方向走
14、一步，或用1的时间向的时间向四个方向飞任意距离。飞行降落点和行走四个方向飞任意距离。飞行降落点和行走必须在平地上。飞行的总距离有限制。问必须在平地上。飞行的总距离有限制。问从从(1,1)飞到飞到(m,n)的最短时间。的最短时间。2011-12-22231135 飞越原野飞越原野n解题思路：解题思路：n进行进行bfs。状态为当前所在格子坐标。状态为当前所在格子坐标(x,y)，当前可用飞行距离当前可用飞行距离d，初始状态为，初始状态为(0,0,d)，终止状态为终止状态为(m,n,x)，其中，其中x可以为任意非负可以为任意非负整数。整数。n每个状态，可以向四个方向走一步，或向每个状态，可以向四个方向
15、走一步，或向四个方向飞任意距离，都消耗时间四个方向飞任意距离，都消耗时间1。2011-12-22241135 飞越原野飞越原野nstruct state n int x,y,d,s;n;nqueue q;nint dx4=0,1,0,-1,dy4=1,0,-1,0;2011-12-22251135 飞越原野飞越原野nint bfs() n state temp1,temp2;n q.push(state(1,1,D,0);n while (!q.empty() n temp1=q.top(); q.pop();n if (temp1.x=m&temp2.y=n) return temp1.s;
16、n for (int k=0;k4;k+) n temp2=walk(temp1,k);n if (valid(temp2) q.push(temp2);n for (int i=1;i=temp1.d,i+) n temp2=fly(temp1,k,i);n if (vaild(temp2) q.push(temp2);n n n n2011-12-22261135 飞越原野飞越原野nstate walk(state temp,int k) ntemp.x+=dxk;ntemp.y+=dyk;ntemp.s+;nreturn temp;nnstate fly(state temp,int k
17、,int step) ntemp.x+=dxk*step;ntemp.y+=dyk*step;ntemp.d-=step;ntemp.s+;nreturn temp;n2011-12-22271135 飞越原野飞越原野nbool valid(state temp) nif (temp.xm|temp.yn)nreturn false;nif (graphtemp.xtemp.y=L)nreturn false;nif (hashtemp.xtemp.ytemp.d)nreturn false;nhashtemp.xtemp.ytemp.d=true;nreturn true;n2011-12-
18、22281107 Simple Puzzlen题目大意：题目大意：n给出给出n个数，每个数有个数，每个数有k个数字，现在把这个数字，现在把这n个数写成个数写成n行，并且对齐成行，并且对齐成k列，在每个数列，在每个数中擦去一个数字，并且擦去的数字的列要中擦去一个数字，并且擦去的数字的列要不相同，得到不相同，得到n个不完整的数。现在给出这个不完整的数。现在给出这n个不完整的数和初始个不完整的数和初始n个数的和，求这个个数的和，求这个n个数。个数。2011-12-22291107 Simple Puzzlen解题思路：解题思路：n枚举枚举n个数中每个数缺失的位，并且缺失的个数中每个数缺失的位，并且缺
19、失的位应该填上的数字，然后检查所有数的和位应该填上的数字，然后检查所有数的和是否和输入相等，相等则记下。是否和输入相等，相等则记下。n枚举用枚举用dfs。n对所有答案排序输出。对所有答案排序输出。2011-12-22301107 Simple Puzzlenint dfs(int m) nif (m=n) ncheck();nreturn;nnint temp=am;nfor (int i=0;ik;i+) nif (di) continue;ndi=true;nfor (int j=0;j=9;j+) nam=add_digit(temp,i,j);ndfs(m+1);nndi=false;nnam=temp;n2011-12-22311107 Simple Puzzlenint add_digit(int x,int pos,int n) nint z=pow(10,pos);nint y=x%z;nx/=z;nreturn (x*10+n)*z+y;n2011-12-22321107 Simple Puzzlenvoid check() nint temp=0;nfor (int i=0;in;i+)ntemp+=ai;nif (temp=sum) nmemcpy(anscnt,a,sizeof(int)*n);ncnt+;nn2011-12-2233谢谢！谢谢！
