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

算法分析习题选讲(第三章) 李承乾 498727460@ 第三章? 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 or Miss ? 1018 A Card Trick ? 1052 Candy Sharing Game ? 1041 Pushing Boxes ? 1211 商人的宣传? 1071 Floors ? 1082 MANAGER 1152 1153 马周游?题目大意:?一个有限大小的棋盘上有一只马,马只能按日字方式走,如图所示。?给出初始时马的位置,找出一条马移动的路线,经过所有格子各一次。解题思路?枚举马能走的所有路径, ?直至找到一条完成周游的路径; ?递归,回溯。? bool solve(int x, int y, int lev) { ? route[lev] = x * N + y; ? if (lev == M * N - 1) {print_route();return true;} ? visited[x][y] = true; ? grid grids[8]; ? int n=get_grid(grids,x,y); ? for (i=0; i<n; i++) ? if (solve(grids[i].x, grids[i].y, lev+1)) ? return true; ? visited[x][y] = false; ? return false; ?} ? int get_grid(grid grids[], int x,int y) { ? int n=0; ? for (int i=0; i<8; i++) { ? int xx = x + direction[i][0]; ? int yy = y + direction[i][1]; ? if( xx>=0&&yy>=0&&xx<M &&yy<N ?&&!visited[xx][yy]) { ? grids[n].x = xx; ? grids[n].y = yy; ? n++; ? } ?}? return n; ?} 优化?以上程序速度过慢。?优化:改变搜索顺序。–先搜索可行格较少的格子。–其他顺序。?修改 get_grid() 函数。? int get_grid(grid grids[], int x,int y) { ? int n=0; ? for (int i=0; i<8; i++) { ? int xx = x + direction[i][0] ? int yy = y + direction[i][1]; ? if (xx>=0&&yy>=0&&xx<M&&yy<N ?&&!visited[xx][yy]) { ? grids[n].x = xx; grids[n].y = yy; ? grids[n].count = get_count(xx, yy); ? n++; ?}?}? sort(grids,grids+n); ? return n; ?} ? bool operator < (const grid &a, const grid &b) { ? return < ; ?}? int get_count(int x, int y) { ? int i, xx, yy, count = 0; ? for (i=0; i<8; i++) { ? xx = x + direction[i][0]; ? yy = y + direction[i][1]; ? if (xx>=0&&yy>=0&&xx<M&&yy<N&&!visited[xx][y y]) ? count++; ?}? return count; ?}