算法分析習(xí)題課第二章

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

第二1150115115151007Toand1036Crypto1006Team1009MersenneComposite1050Numbers&1443Printer1156Binary1063Who'sthe1024Magic例Num:array[‘a(chǎn)’..’z’]ofintcharsicily115011511515狀態(tài)的操作序列，長(zhǎng)度不得超過(guò)上三種基本操１２３４８１２３４８７６５８７６５１２３４１２３４１２３４８７６５４１２３５８７６B:１２１２３４８７６５１７２４８６３５解題思對(duì)模板進(jìn)行狀態(tài)搜在這棵三叉樹(shù)上搜索，目的是求出最優(yōu)解對(duì)這棵三叉樹(shù)進(jìn)行效果：勉強(qiáng)可過(guò)對(duì)這棵三叉樹(shù)進(jìn)行第一個(gè)可行解即是最優(yōu)效果：輕松過(guò)掉1150，但過(guò)不了算法三：BFS對(duì)這棵三叉樹(shù)進(jìn)行第一個(gè)可行解即是最優(yōu)判共有8!=40320個(gè)節(jié)算法三：BFS1.123487652.康托展 表示，在全排列中，比大而且位于前面statevoidupdate(statenew_state,int&head,int&tail,charopt){}voidbfs(statestart)intwhile(tail<head)stateififstateif}}1007ToandFro題目大給出一種，把一個(gè)字符串按列寫(xiě)給出加密后的字符串，還原本來(lái)的字符解題思 1036CryptoColumns題目大給定一個(gè)給出加密后的字符還原本來(lái)的字符 1006TeamRankings題對(duì)于兩個(gè)排列p,qdistance(p,q)為在p,q中出現(xiàn)的相對(duì)次序不同的元素的解題思 枚舉方法可用遞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素?cái)?shù)Mn：定義為2n-1其中n為素?cái)?shù)2n-1也為素?cái)?shù)的給定k，求出所有素<=k，且滿(mǎn)足1不是 數(shù)并且將它們分。方法若a是Mq的因數(shù)，則aa≡1moda≡±1mod方法查找資料可在n<=63內(nèi)有以下Mn滿(mǎn)足答只對(duì)這些數(shù)進(jìn)行分vector<longlong>cal(longlongx)vector<longlonglongfor(i=3;i*i<=n;i+=2)while(n%i==0)}if(k!=0)}return}1050Numbers&Letters解題思求出所有可能的運(yùn)算組合和順得到最接近目標(biāo)數(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題目大問(wèn)其中某個(gè)任務(wù)是第幾個(gè)被打印n≤解題思使用隊(duì)列直接模直到特定的任務(wù)完成，輸出答while(true)cur=if(cur.priority!=highest_priority)}elseif(cur.number==m)while highest_priority--}}1156Binarytree題目大解題思先找出沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)，即根從根開(kāi)始遍歷進(jìn)行先序遍1063Who'stheBoss題目大有n個(gè)人的編號(hào)，身高和工解題思可以使用STL里的set。(upper_bound())對(duì)每個(gè)詢(xún)問(wèn)，查找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