算法分析习题课第二章

算法分析习题选讲(第二章Sicily地址

第二1150115115151007Toand1036Crypto1006Team1009MersenneComposite1050Numbers&1443Printer1156Binary1063Who'sthe1024Magic例Num:array[‘a’..’z’]ofintcharsicily115011511515状态的操作序列，长度不得超过上三种基本操１２３４８１２３４８７６５８７６５１２３４１２３４１２３４８７６５４１２３５８７６B:１２１２３４８７６５１７２４８６３５解题思对模板进行状态搜在这棵三叉树上搜索，目的是求出最优解对这棵三叉树进行效果：勉强可过对这棵三叉树进行第一个可行解即是最优效果：轻松过掉1150，但过不了算法三：BFS对这棵三叉树进行第一个可行解即是最优判共有8!=40320个节算法三：BFS1.123487652.康托展 表示，在全排列中，比大而且位于前面statevoidupdate(statenew_state,int&head,int&tail,charopt){}voidbfs(statestart)intwhile(tail<head)stateififstateif}}1007ToandFro题目大给出一种，把一个字符串按列写给出加密后的字符串，还原本来的字符解题思 1036CryptoColumns题目大给定一个给出加密后的字符还原本来的字符 1006TeamRankings题对于两个排列p,qdistance(p,q)为在p,q中出现的相对次序不同的元素的解题思 枚举方法可用递voidcal(charrank[])intfor(inti=0;i<n;i++)if(count<ans_count)}}intdistance(chara[],charb[])intfor(inti=0;i<5;i++){posa[a[i]]=i;posb[b[i]]=i;for(charfor(char

if((posa[c1]-posa[c2])*(posb[c1]-return}voiddfs(charrank[],intlev)if(lev==5)}for(charc='A';c<='E';c++)if(!used[c])}}1009MersenneCompositeN素数Mn：定义为2n-1其中n为素数2n-1也为素数的给定k，求出所有素<=k，且满足1不是 数并且将它们分。方法若a是Mq的因数，则aa≡1moda≡±1mod方法查找资料可在n<=63内有以下Mn满足答只对这些数进行分vector<longlong>cal(longlongx)vector<longlonglongfor(i=3;i*i<=n;i+=2)while(n%i==0)}if(k!=0)}return}1050Numbers&Letters解题思求出所有可能的运算组合和顺得到最接近目标数的答voiddfs(inta[],intn)if(n==1)intfor(intfor(intj=i+i;j<n;j++)for(intif(k!=i&&k!=j)update_answer(b[m]=a[i]+a[j]);update_answer(b[m]=a[i]-a[j]);update_answer(b[m]=a[j]-a[i]);update_answer(b[m]=a[i]*a[j]);if(a[j]!=0&&a[i]%a[j]==0)update_answer(b[m]=a[i]/a[j]);}if(a[i]!=0&&a[j]%a[i]==0)update_answer(b[m]=a[j]/a[i]);}}}1443PrinterQueue题目大问其中某个任务是第几个被打印n≤解题思使用队列直接模直到特定的任务完成，输出答while(true)cur=if(cur.priority!=highest_priority)}elseif(cur.number==m)while highest_priority--}}1156Binarytree题目大解题思先找出没有父节点的节点，即根从根开始遍历进行先序遍1063Who'stheBoss题目大有n个人的编号，身高和工解题思可以使用STL里的set。(upper_bound())对每个询问，查找ID给出答案struct{intboolcmp(constemployee&a,constemployee{ifreturnreturn}boolcmp2(constemployee&a,constemployee{return}set<employee> torforfor(i=n-1;i>=0;i--)if(it==h.end())a[i].farther=-else}for(i=0;i<n;i++)if(a[i].fa