算法分析習題課第二章

算法分析習題選講(第二章Sicily地址

第二1150115115151007Toand1036Crypto1006Team1009MersenneComposite1050Numbers&1443Printer1156Binary1063Who'sthe1024Magic例Num:array[‘a(chǎn)’..’z’]ofintcharsicily115011511515狀態(tài)的操作序列，長度不得超過上三種基本操１２３４８１２３４８７６５８７６５１２３４１２３４１２３４８７６５４１２３５８７６B:１２１２３４８７６５１７２４８６３５解題思對模板進行狀態(tài)搜在這棵三叉樹上搜索，目的是求出最優(yōu)解對這棵三叉樹進行效果：勉強可過對這棵三叉樹進行第一個可行解即是最優(yōu)效果：輕松過掉1150，但過不了算法三：BFS對這棵三叉樹進行第一個可行解即是最優(yōu)判共有8!=40320個節(jié)算法三：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中出現(xiàn)的相對次序不同的元素的解題思 枚舉方法可用遞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素數(shù)Mn：定義為2n-1其中n為素數(shù)2n-1也為素數(shù)的給定k，求出所有素<=k，且滿足1不是 數(shù)并且將它們分。方法若a是Mq的因數(shù)，則aa≡1moda≡±1mod方法查找資料可在n<=63內(nèi)有以下Mn滿足答只對這些數(shù)進行分vector<longlong>cal(longlongx)vector<longlonglongfor(i=3;i*i<=n;i+=2)while(n%i==0)}if(k!=0)}return}1050Numbers&Letters解題思求出所有可能的運算組合和順得到最接近目標數(shù)的答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題目大解題思先找出沒有父節(jié)點的節(jié)點，即根從根開始遍歷進行先序遍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