算法分析習(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)計(jì)其中每個(gè)字符出現(xiàn)的次數(shù).1.考慮數(shù)據(jù)結(jié)構(gòu):用一維數(shù)組存放每個(gè)字母出現(xiàn)的次數(shù),定義一個(gè)由26個(gè)字母組成的數(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)的操作序列，長(zhǎng)度不得超過(guò)上限。三種基本操作A:上下互換B:循環(huán)右移C:循環(huán)左移2341758解題思路對(duì)模板進(jìn)行狀態(tài)搜索由一種狀態(tài)可以轉(zhuǎn)移到另外三種狀態(tài)，搜索樹為一棵三叉樹在這棵三叉樹上搜索，目的是求出最優(yōu)解。算法一：DFS(深度優(yōu)先搜索)對(duì)這棵三叉樹進(jìn)行DFS缺點(diǎn)：

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

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

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

7、nce之和最小。n=100解題思路枚舉所有5元排列，與n個(gè)排列一一比較5個(gè)元素之間順序并累加；枚舉方法可用遞歸。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 題意梅森素?cái)?shù)Mn：定義為2n-1其中n為素?cái)?shù)且2n-1也為素?cái)?shù)的數(shù)。給定k，求出所有素?cái)?shù)n=k，且滿足2n-1不是梅森素?cái)?shù)的數(shù)，并且將它們分解。k=63方法1.暴力求解所有梅森素?cái)?shù)2.查找資料可知在n=63內(nèi)有以下Mn滿足答案11,23,29,37,41,43,47,53,59只對(duì)這些數(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個(gè)數(shù)和一個(gè)目標(biāo)數(shù)，從5個(gè)數(shù)中選出一部分?jǐn)?shù)通過(guò)加減乘除運(yùn)算得到小于等于目標(biāo)數(shù)的最大數(shù)。類似的題目：24點(diǎn)，從52張牌中抽4張，使得其加減乘除得24解題思路DFS求出所有可能的運(yùn)算組合和順序得到最接近目標(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 題目大意給出一棵二叉樹每個(gè)節(jié)點(diǎn)的編號(hào)，內(nèi)容以及左右子節(jié)點(diǎn)的編號(hào)要求對(duì)二叉樹進(jìn)行先序遍歷，輸出每個(gè)節(jié)點(diǎn)的內(nèi)容。解題思路先序遍歷：先輸出當(dāng)前節(jié)點(diǎn)的內(nèi)容，然后遍歷左子樹，最后遍歷右子樹。先找出沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)，即根。從根開始遍歷進(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個(gè)人的編號(hào)，身高和工資一個(gè)人的直

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