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

算法分析习题选讲(第二章) 李承乾 498727460@ 第二章? Sicily 地址: ? 1150 1151 1515 魔板? 1007 To and Fro ? 1036 Crypto Columns ? 1006 Team Rankings ? 1009 posite N ? 1050 Numbers & Letters ? 1443 Printer Queue ? 1156 Binary tree ? 1063 Who's the Boss ? 1024 Magic Island 例 ?输入一串字符,以”?”结束,统计其中每个字符出现的次数.? :用一维数组存放每个字母出现的次数,定义一个由 26 个字母组成的数组: Num:array[ ‘a’..’z’]of integer ? int i,Num[128]={0}; ? char c; ?? while( (c=getchar())!='?' ) ? Num[c]++; ?? for(i='a';i<='z';i++) ? cout<<Num[i]<<endl; ? sicily 1150 1151 1515 魔板题意?给出魔板的起始状态,三种基本操作,步数上限和目标状态, 求从起始状态到目标?状态的操作序列,长度不得超过上限。三种基本操作? A:上下互换? B:循环右移? C:循环左移 1234 8765 8765 1234 1234 8765 4123 5876 1234 8765 234176 58解题思路?对模板进行状态搜索?由一种状态可以转移到另外三种状态,搜索树为一棵三叉树?在这棵三叉树上搜索,目的是求出最优解。算法一: DFS( 深度优先搜索) ?对这棵三叉树进行 DFS ?缺点:若想求得最优解,需要遍历整棵树, 会遍历很多重复的节点?优化:若已找到一个可行解,可剪去大于等于这个深度的所有子树?效果:勉强可过 1150 算法二: BFS( 广度优先搜索) ?对这棵三叉树进行 BFS ?第一个可行解即是最优解?效果:轻松过掉 1150 ,但过不了 1151 算法三: BFS + 判重?对这棵三叉树进行 BFS ?第一个可行解即是最优解?判重? BFS 每经过一个节点,就把它放进已搜索列表中?如果节点在已搜索列表存在,则不再扩展该节点?共有 8!=40320 个节点