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

1、算法分析習(xí)題選講(第二章)第二章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 輸入一串字符，以”?”結(jié)束,統(tǒng)計其中每個字符出現(xiàn)的次數(shù).1.考慮數(shù)據(jù)結(jié)構(gòu):用一維數(shù)組存放每個字母出現(xiàn)的次數(shù),定義一個由26個字母組成的數(shù)組：N

2、um:arraya.zof integerint i,Num128=0;char c;while( (c=getchar()!=? )Numc+;for(i=a;i=z;i+)coutNumiendl;sicily 1150 1151 1515 魔板 題意給出魔板的起始狀態(tài)，三種基本操作，步數(shù)上限和目標(biāo)狀態(tài)， 求從起始狀態(tài)到目標(biāo)狀態(tài)的操作序列，長度不得超過上限。三種基本操作A:上下互換B:循環(huán)右移C:循環(huán)左移2341758解題思路對模板進(jìn)行狀態(tài)搜索由一種狀態(tài)可以轉(zhuǎn)移到另外三種狀態(tài)，搜索樹為一棵三叉樹在這棵三叉樹上搜索，目的是求出最優(yōu)解。算法一：DFS(深度優(yōu)先搜索)對這棵三叉樹進(jìn)行DFS缺點：

3、若想求得最優(yōu)解，需要遍歷整棵樹，會遍歷很多重復(fù)的節(jié)點優(yōu)化：若已找到一個可行解，可剪去大于等于這個深度的所有子樹效果：勉強(qiáng)可過1150算法二：BFS(廣度優(yōu)先搜索)對這棵三叉樹進(jìn)行BFS第一個可行解即是最優(yōu)解效果：輕松過掉1150，但過不了1151算法三：BFS + 判重對這棵三叉樹進(jìn)行BFS第一個可行解即是最優(yōu)解判重BFS每經(jīng)過一個節(jié)點，就把它放進(jìn)已搜索列表中如果節(jié)點在已搜索列表存在，則不再擴(kuò)展該節(jié)點共有8!=40320個節(jié)點節(jié)點已搜索，再擴(kuò)展該節(jié)點算法三：BFS + 判重節(jié)點編碼1. 自定義編碼，如把狀態(tài)編碼為整數(shù)123487652. 康托展開12348765 康托展開康托展開是一個全排列到

4、一個自然數(shù)的雙射，常用于構(gòu)建哈希表時的空間壓縮N位的十進(jìn)制整數(shù)可以由N個的數(shù)字表示N個數(shù)字的排列也可以由N個數(shù)字表示 表示，在全排列 中，比 大而且位于 前面的數(shù)字的個數(shù)。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

5、(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 題目大意給出一種加密方式，把一個字符

6、串按列寫成二維形式，再逐行從左到右或從右到左交替輸出給出加密后的字符串，還原本來的字符串解題思路按照解密規(guī)則把輸入字符串寫在二維數(shù)組上，再輸出1036 Crypto Columns 題目大意給定一個Keyword把一個字符串按行寫成二維形式按照Keyword的字符大小順序逐列輸出給出加密后的字符串還原本來的字符串按照解密規(guī)則把輸入字符串寫在二維數(shù)組上，再輸出1006 Team Rankings 題意對于兩個排列p,q，定義 distance( p, q )為在p,q中出現(xiàn)的相對次序不同的元素的對數(shù)。相當(dāng)于以p為基準(zhǔn)，求q的逆序數(shù)。給出n個5元排列，構(gòu)造一個排列，使得該排列對n個排列的dista

7、nce之和最小。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 (ch

8、ar 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);

9、 while(next_permutation(rank,rank+lev);1009 Mersenne Composite N 題意梅森素數(shù)Mn：定義為2n-1其中n為素數(shù)且2n-1也為素數(shù)的數(shù)。給定k，求出所有素數(shù)n=k，且滿足2n-1不是梅森素數(shù)的數(shù)，并且將它們分解。k=63方法1.暴力求解所有梅森素數(shù)2.查找資料可知在n=63內(nèi)有以下Mn滿足答案11,23,29,37,41,43,47,53,59只對這些數(shù)進(jìn)行分解。vector cal(long long x) vectorfactor;long long n,i,k;n=(1LLx)-1;for (i=3;i*i1) factor.

10、push_back(n);return factor;求質(zhì)數(shù)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=2;i*j=n;j+) vi*j=1;1050 Numbers & Letters 題目大意給出5個數(shù)和一個目標(biāo)數(shù)，從5個數(shù)中選出一部分?jǐn)?shù)通過加減乘除運算得到小于等于目標(biāo)數(shù)的最大數(shù)。類似的題目：24點，從52張牌中抽4張，使得其加減乘除得24解題思路DFS求出所有可能的運算組合和順序得到最接近目標(biāo)數(shù)的答案。void dfs(int a, in

11、t 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 題目大意給出一棵二叉樹每個節(jié)點的編號，內(nèi)容以及左右子節(jié)點的編號要求對二叉樹進(jìn)行先序遍歷，輸出每個節(jié)點的內(nèi)容。解題思路先序遍歷：先輸出當(dāng)前節(jié)點的內(nèi)容，然后遍歷左子樹，最后遍歷右子樹。先找出沒有父節(jié)點的節(jié)點，即根。從根開始遍歷進(jìn)行先序遍歷。中序遍歷void dfs(Node *s) dfs(s-leftc

12、hild); Visit(s); dfs(s-rightchild);后序遍歷void dfs(Node *s) dfs(s-leftchild); dfs(s-rightchild); Visit(s);防止暴棧main函數(shù)里面第一行加入如下代碼：char *p = (char*)malloc(size) + size;asm(movl %0, %espn : r(p);size根據(jù)情況爆棧程度自行設(shè)定，如1024M。先序遍歷非遞歸void Preoder(Node *root) Node* p; stack s; s.push(root); while(s.size() p=s.top()

13、; 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)

14、 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

15、 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; st

16、ack 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個人的編號，身高和工資一個人的直

17、接上司是身高不比他小且工資比他高最少的人而一個的下屬不止是他的直接下屬，還包含他的下屬的下屬，等等現(xiàn)在有q個詢問，你需要輸出詢問到的人的直接上司，以及他的下屬的數(shù)量解題思路對所有人按身高從大到小排序，相同則按工資從大到小排序。枚舉每個人，在已檢查的人中找出工資比他高最少的人，這個人就是他的直接上司?？梢允褂肧TL里的set。(upper_bound ()再按身高從小到大枚舉每個人，把每個人的下屬個數(shù)累加進(jìn)他的直接上司的下屬個數(shù)。對每個詢問，查找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;bool cmp2(const employee &a,const employee &b)return a.idb.id;set h;set:iterator