算法分析习题课第二章

算法分析习题选讲(第二章)

第二章Sicily地址:115011511515魔板1007ToandFro1036CryptoColumns1006TeamRankings1009MersenneCompositeN1050Numbers&Letters1443PrinterQueue1156Binarytree1063Who'stheBoss1024MagicIsland例2.1输入一串字符，以”?”结束,统计其中每个字符出现的次数.1.考虑数据结构:用一维数组存放每个字母出现的次数,定义一个由26个字母组成的数组：Num:array[‘a’..’z’]ofinteger inti,Num[128]={0}; charc;

while((c=getchar())!='?') Num[c]++;

for(i='a';i<='z';i++) cout<<Num[i]<<endl;

sicily115011511515魔板题意给出魔板的起始状态，三种基本操作，步数上限和目标状态，求从起始状态到目标状态的操作序列，长度不得超过上限。三种基本操作A:上下互换B:循环右移B:循环右移１２３４８７６５８７６５１２３４１２３４８７６５４１２３５８７６１２３４８７６５１７２４８６３５解题思路对模板进行状态搜索由一种状态可以转移到另外三种状态，搜索树为一棵三叉树在这棵三叉树上搜索，目的是求出最优解。算法一：DFS(深度优先搜索)对这棵三叉树进行DFS缺点：若想求得最优解，需要遍历整棵树，会遍历很多重复的节点优化：若已找到一个可行解，可剪去大于等于这个深度的所有子树效果：勉强可过1150算法二：BFS(广度优先搜索)对这棵三叉树进行BFS第一个可行解即是最优解效果：轻松过掉1150，但过不了1151算法三：BFS+判重对这棵三叉树进行BFS第一个可行解即是最优解判重BFS每经过一个节点，就把它放进已搜索列表中如果节点在已搜索列表存在，则不再扩展该节点共有8!=40320个节点节点已搜索，再扩展该节点算法三：BFS+判重节点编码1.自定义编码，如把状态编码为整数123487652.康托展开12348765康托展开康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩N位的十进制整数可以由N个的数字表示N个数字的排列也可以由N个数字表示表示，在全排列中，比大而且位于前面的数字的个数。stateq[40320];voidupdate(statenew_state,int&head,int&tail,charopt){ q[head]=new_state; visit[hash(new_state)]=true; parent[head]=tail; op[head++]=opt;}voidbfs(statestart){ inthead=0,tail=0; update(start,head,tail,'\0'); while(tail<head){ statenew_state=A(q[tail]); if(visit[hash(new_state)]==false) update(new_state,head,tail,'A') new_state=B(q[tail]); if(visit[hash(new_state)]==false) update(new_state,head,tail,'B') statenew_state=C(q[tail]); if(visit[hash(new_state)]==false) update(new_state,head,tail,'C') tail++; }}1007ToandFro题目大意给出一种加密方式，把一个字符串按列写成二维形式，再逐行从左到右或从右到左交替输出给出加密后的字符串，还原本来的字符串解题思路按照解密规则把输入字符串写在二维数组上，再输出1036CryptoColumns题目大意给定一个Keyword把一个字符串按行写成二维形式按照Keyword的字符大小顺序逐列输出给出加密后的字符串还原本来的字符串按照解密规则把输入字符串写在二维数组上，再输出1006TeamRankings题意对于两个排列p,q，定义distance(p,q)为在p,q中出现的相对次序不同的元素的对数。相当于以p为基准，求q的逆序数。给出n个5元排列，构造一个排列，使得该排列对n个排列的distance之和最小。n<=100解题思路枚举所有5元排列，与n个排列一一比较5个元素之间顺序并累加；枚举方法可用递归。voidcal(charrank[]){ intcount=0; for(inti=0;i<n;i++)count+=distance(ranks[i],rank); if(count<ans_count){ ans_count=count; strcpy(ans,rank); }}intdistance(chara[],charb[]){ intcnt=0; for(inti=0;i<5;i++){posa[a[i]]=i;posb[b[i]]=i;} for(charc1='A';c1<='E';c1++)for(charc2='A';c2<='E';c2++)if((posa[c1]-posa[c2])*(posb[c1]-posb[c2])<0)cnt++; returncnt;}voiddfs(charrank[],intlev){ if(lev==5){ rank[5]='\0'; cal(rank); return; } for(charc='A';c<='E';c++)if(!used[c]){ rank[lev]=c; used[c]=true; dfs(rank,lev+1); used[c]=false; }}全排列next_permutation()voiddfs(charrank[]){sort(rank,rank+5);rank[5]=0;do{cal(rank);while(next_permutation(rank,rank+lev));

}1009MersenneCompositeN题意梅森素数Mn：定义为2^n-1其中n为素数且2^n-1也为素数的数。给定k，求出所有素数n<=k，且满足2^n-1不是梅森素数的数，并且将它们分解。k<=63方法1.暴力求解所有梅森素数2.查找资料可知在n<=63内有以下Mn满足答案11,23,29,37,41,43,47,53,59只对这些数进行分解。vector<longlong>cal(longlongx){ vector<longlong>factor; longlongn,i,k; n=(1LL<<x)-1; for(i=3;i*i<=n;i+=2){ k=0; while(n%i==0){ n/=i; k++; } if(k!=0)factor.push_back(i); }

if(n>1)factor.push_back(n); returnfactor;}1050Numbers&Letters题目大意给出5个数和一个目标数，从5个数中选出一部分数通过加减乘除运算得到小于等于目标数的最大数。类似的题目：24点，从52张牌中抽4张，使得其加减乘除得24解题思路DFS求出所有可能的运算组合和顺序得到最接近目标数的答案。voiddfs(inta[],intn){ if(n==1)return; intb[5],m=0; for(inti=0;i<n;i++)for(intj=i+1;j<n;j++){for(intk=0;k<n;k++)if(k!=i&&k!=j)b[m++]=a[k]; update_answer(b[m]=a[i]+a[j]);dfs(b,m+1); update_answer(b[m]=abs(a[i]-a[j]));dfs(b,m+1); update_answer(b[m]=a[i]*a[j]);dfs(b,m+1); if(a[j]!=0&&a[i]%a[j]==0){ update_answer(b[m]=a[i]/a[j]);dfs(b,m+1); } if(a[i]!=0&&a[j]%a[i]==0){ update_answer(b[m]=a[j]/a[i]);dfs(b,m+1);} }}1443PrinterQueue题目大意有一个长度为n的打印任务队列，每个任务有优先级每次从队列头得到一个任务，如果它是剩余任务中优先级最高的，则打印它，否则放到队列尾问其中某个任务是第几个被打印的。n≤100解题思路使用队列直接模拟取出队列头判断是否打印，如果打印则已打印任务数加一直到特定的任务完成，输出答案while(true){cur=q.front();if(cur.priority!=highest_priority){q.push(cur);}else{minute++;if(cur.number==m)break;

cnt[highest_priority]--;while(highest_priority>0&&cnt[highest_priority]==0)highest_priority--;}}1156Binarytree题目大意给出一棵二叉树每个节点的编号，内容以及左右子节点的编号要求对二叉树进行先序遍历，输出每个节点的内容。解题思路先序遍历：先输出当前节点的内容，然后遍历左子树，最后遍历右子树。先找出没有父节点的节点，即根。从根开始遍历进行先序遍历。防止暴栈main函数里面第一行加入如下代码：char*p=(char*)malloc(size)+size;asm("movl%0,%%esp\n"::"r"(p));size根据情况爆栈程度自行设定，如100M。先序遍历非递归voidPreoder(Node*root){Node*p;stack<Node*>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);}}通用非递归voidPreoder(Node*root){Node*p;intq;stack<Node*>s;stack<Node*>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);}elseif(q==1){s.push(p);L.push(2);s.push(p->leftchild);L.push(0);}else{s.push(p->rightchild);L.push(0);}}}1063Who'stheBoss题目大意有n个人的编号，身高和工资一个人的直接上司是身高不比他小且工资比他高最少的人而一个的下属不止是他的直接下属，还包含他的下属的下属，等等现在有q个询问，你需要输出询问到的人的直接上司，以及他的下属的数量解题思路对所有人按身高从大到小排序，相同则按工资从大到小排序。枚举每个人，在已检查的人中找出工资比他高最少的人，这个人就是他的直接上司。可以使用STL里的set。(upper_bound())再按身高从小到大枚举每个人，把每个人的下属个数累加进他的直接上司的下属个数。对每个询问，查找ID给出答案。structemployee{ intheight,id,earn,number,farther,sub;};boolcmp(constemployee&a,constemployee&b){ if(a.height!=b.height) returna.height<b.height; else returna.earn<b.earn;}boolcmp2(constemployee&a,constemployee&b){ returna.id<b.id;}set<employee>h;set<employee>::iteratorit;sort(a,a+n,cm