算法分析习题课 第二章

算法分析习题选讲(第二章)第二章Sicily 地址:http:/soj.me1150 1151 1515 魔板1007 To and Fro1036 Crypto Columns1006 Team Rankings1009 Mersenne Composite N1050 Numbers&Letters1443 Printer Queue1156 Binary tree1063 Whos the Boss1024 Magic Island例2.1 输入一串字符，以”?”结束,统计其中每个字符出现的次数.1.考虑数据结构:用一维数组存放每个字母出现的次数,定义一个由26个字母组成的数组：Num:arraya.zof integerint i,Num128=0;char c;while(c=getchar()!=?)Numc+;for(i=a;i=z;i+)coutNumiendl;sicily 1150 1151 1515 魔板 题意给出魔板的起始状态，三种基本操作，步数上限和目标状态，求从起始状态到目标状态的操作序列，长度不得超过上限。三种基本操作A:上下互换B:循环右移C:循环左移2341758解题思路对模板进行状态搜索由一种状态可以转移到另外三种状态，搜索树为一棵三叉树在这棵三叉树上搜索，目的是求出最优解。算法一：DFS(深度优先搜索)对这棵三叉树进行DFS缺点：若想求得最优解，需要遍历整棵树，会遍历很多重复的节点优化：若已找到一个可行解，可剪去大于等于这个深度的所有子树效果：勉强可过1150算法二：BFS(广度优先搜索)对这棵三叉树进行BFS第一个可行解即是最优解效果：轻松过掉1150，但过不了1151算法三：BFS+判重对这棵三叉树进行BFS第一个可行解即是最优解判重BFS每经过一个节点，就把它放进已搜索列表中如果节点在已搜索列表存在，则不再扩展该节点共有8!=40320个节点节点已搜索，再扩展该节点算法三：BFS+判重节点编码1.自定义编码，如把状态编码为整数123487652.康托展开12348765 康托展开康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩N位的十进制整数可以由N个的数字表示N个数字的排列也可以由N个数字表示 表示，在全排列 中，比 大而且位于 前面的数字的个数。state q40320;void update(state new_state,int&head,int&tail,char opt)qhead=new_state;visithash(new_state)=true;parenthead=tail;ophead+=opt;void bfs(state start)int head=0,tail=0;update(start,head,tail,0);while(tailhead)state new_state=A(qtail);if(visithash(new_state)=false)update(new_state,head,tail,A)new_state=B(qtail);if(visithash(new_state)=false)update(new_state,head,tail,B)state new_state=C(qtail);if(visithash(new_state)=false)update(new_state,head,tail,C)tail+;1007 To and Fro 题目大意给出一种加密方式，把一个字符串按列写成二维形式，再逐行从左到右或从右到左交替输出给出加密后的字符串，还原本来的字符串解题思路按照解密规则把输入字符串写在二维数组上，再输出1036 Crypto Columns 题目大意给定一个Keyword把一个字符串按行写成二维形式按照Keyword的字符大小顺序逐列输出给出加密后的字符串还原本来的字符串按照解密规则把输入字符串写在二维数组上，再输出1006 Team Rankings 题意对于两个排列p,q，定义 distance(p,q)为在p,q中出现的相对次序不同的元素的对数。相当于以p为基准，求q的逆序数。给出n个5元排列，构造一个排列，使得该排列对n个排列的distance之和最小。n=100解题思路枚举所有5元排列，与n个排列一一比较5个元素之间顺序并累加；枚举方法可用递归。void cal(char rank)int count=0;for(int i=0;in;i+)count+=distance(ranksi,rank);if(countans_count)ans_count=count;strcpy(ans,rank);int distance(char a,char b)int cnt=0;for(int i=0;i5;i+)posaai=i;posbbi=i;for(char c1=A;c1=E;c1+)for(char c2=A;c2=E;c2+)if(posac1-posac2)*(posbc1-posbc2)0)cnt+;return cnt;void dfs(char rank,int lev)if(lev=5)rank5=0;cal(rank);return;for(char c=A;c=E;c+)if(!usedc)ranklev=c;usedc=true;dfs(rank,lev+1);usedc=false;全排列next_permutation()void dfs(char rank)sort(rank,rank+5);rank5=0;do cal(rank);while(next_permutation(rank,rank+lev);1009 Mersenne Composite N 题意梅森素数Mn：定义为2n-1其中n为素数且2n-1也为素数的数。给定k，求出所有素数n=k，且满足2n-1不是梅森素数的数，并且将它们分解。k=63方法1.暴力求解所有梅森素数2.查找资料可知在n=63内有以下Mn满足答案11,23,29,37,41,43,47,53,59只对这些数进行分解。vector cal(long long x)vectorfactor;long long n,i,k;n=(1LLx)-1;for(i=3;i*i1)factor.push_back(n);return factor;求质数bool v101000;int p101000,pn;n=100000;pn=0;fill(v,v+n+1,0);for(i=2;i=n;i+)if(!vi)ppn+=i;for(j=i*i;j=n;j+=i)vj=1;1050 Numbers&Letters 题目大意给出5个数和一个目标数，从5个数中选出一部分数通过加减乘除运算得到小于等于目标数的最大数。类似的题目：24点，从52张牌中抽4张，使得其加减乘除得24解题思路DFS求出所有可能的运算组合和顺序得到最接近目标数的答案。void dfs(int a,int n)if(n=1)return;int b5,m=0;for(int i=0;in;i+)for(int j=i+1;jn;j+)for(int k=0;k0&cnthighest_priority=0)highest_priority-;1156 Binary tree 题目大意给出一棵二叉树每个节点的编号，内容以及左右子节点的编号要求对二叉树进行先序遍历，输出每个节点的内容。解题思路先序遍历：先输出当前节点的内容，然后遍历左子树，最后遍历右子树。先找出没有父节点的节点，即根。从根开始遍历进行先序遍历。中序遍历void dfs(Node*s)dfs(s-leftchild);Visit(s);dfs(s-rightchild);后序遍历void dfs(Node*s)dfs(s-leftchild);dfs(s-rightchild);Visit(s);防止暴栈main函数里面第一行加入如下代码：char*p=(char*)malloc(size)+size;asm(movl%0,%espn:r(p);size根据情况爆栈程度自行设定，如1024M。先序遍历非递归void Preoder(Node*root)Node*p;stack s;s.push(root);while(s.size()p=s.top();s.pop();if(p=0)continue;Visit(p);s.push(p-rightchild);s.push(p-leftchild);通用非递归 先序遍历void Preoder(Node*root)Node*p;int q;stack s;stack L;s.push(root);L.push(0);while(s.size()p=s.top();s.pop();q=L.top();L.pop();if(p=0)continue;if(q=0)s.push(p);L.push(1);Visit(p);else if(q=1)s.push(p);L.push(2);s.push(p-leftchild);L.push(0);else s.push(p-rightchild);L.push(0);中序遍历非递归void Preoder(Node*T)stack S;while(T|stack.size()while(T)S.push(T);T=T-leftchild;T=S.top();S.pop();Visit(T);T=T-rightchild;通用非递归 中序遍历void Preoder(Node*root)Node*p;int q;stack s;stack L;s.push(root);L.push(0);while(s.size()p=s.top();s.pop();q=L.top();L.pop();if(p=0)continue;if(q=0)s.push(p);L.push(1);s.push(p-leftchild);L.push(0);else if(q=1)s.push(p);L.push(2);Visit(p);else s.push(p-rightchild);L.push(0);通用非递归 后序遍历void Preoder(Node*root)Node*p;int q;stack s;stack L;s.push(root);L.push(0);while(s.size()p=s.top();s.pop();q=L.top();L.pop();if(p=0)continue;if(q=0)s.push(p);L.push(1);s.push(p-leftchild);L.push(0);else if(q=1)s.push(p);L.push(2);s.push(p-rightchild);L.push(0);else Visit(p);1063 Whos the Boss 题目大意有n个人的编号，身高和工资一个人的直接上司是身高不比他小且工资比他高最少的人而一个的下属不止是他的直接下属，还包含他的下属的下属，等等现在有q个询问，你需要输出询问到的人的直接上司，以及他的下属的数量解题思路对所有人按身高从大到小排序，相同则按工资从大到小排序。枚举每个人，在已检查的人中找出工资比他高最少的人，这个人就是他的直接上司。可以使用STL里的set。(upper_bound()再按身高从小到大枚举每个人，把每个人的下属个数累加进他的直接上司的下属个数。对每个询问，查找ID给出答案。struct employeeint height,id,earn,number,farther,sub;bool cmp(const employee&a,const employee&b)if(a.height!=b.height)return a.heightb.height;elsereturn a.earnb.earn;boo