算法分析习题课 第一章

1、算法分析习题选讲(第一章)第一章Sicily 地址: http:/soj.me1020 Big Integer1021 Couple1027 MJ, Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Bikers Trip Odomete1198 Substring1176 Two Ends1020 Big Integer题目大意：给出n个整数b1,b2,.,bn，和一个大整数x，求x对每个数bi取模的结果。n=100, 1bi=1000, x的长度不超过400解题思路12345678901234567890 % m1 % m =

2、112 % m = (1 * 10 + 2) % m = (1 % m * 10 + 2) % m123 % m = (12 * 10 + 3) % m = (12 % m * 10 + 3) % m12345678901234567890 % m= ( ( 1 % m * 10 + 2 ) % m*10+3 ) % m 解题思路对bi逐个计算；高精度，模拟竖式计算。int div(char x, int b) int a=0;for (int i=0;xi!=0;i+) a=(a*10+xi-0)%b;return a;1021 Couple题目大意：N对夫妇站成一圈如果某对夫妇站在相邻位置

3、，则从圈中移走重复以上操作问最后会不会没人如1 3是一对，2 4是一对，则No如1 4是一对，2 3是一对，则Yes1=N=100,000解题思路类似于括号匹配，可将n对夫妇看成n种括号用一个栈来模拟，将括号逐个push到栈里当栈顶存在匹配对时进行pop操作看最后栈是否为空例子1如1 4是一对，2 3是一对最后栈为空，输出Yes112123114例子2如1 3是一对，2 4是一对最后栈不为空，输出No1121231423代码stack s;for (int i=1;i=2*n;i+) if (!s.empty()&s.top()=couplei)s.pop();elses.push(i);10

4、27 MJ, Nowhere to Hide题目大意：给出N对BBS_ID IP_Address，求出IP_Address相同的BBS_ID。N=20解题思路枚举每两个BBS_ID IP_Address对，比较IP_Address是否相同；字符串比较。for (int i=0;in;i+) for (int j=i;jn;j+) if (strcmp(ipi,ipj)=0) anscnt+=make_pair(idi,idj);1035 DNA matching给出n个DNA单链，问可以用这些DNA单链组成多少个DNA双链；每个DNA单链最多使用一次；两个DNA单链能组成DNA双链，当且仅当两

5、个DNA单链的长度相等，且对应位置上能配对，A与T配对，C与G配对；n=100, 每个单链长度不超过100。解题思路枚举每个没有被匹配的DNA单链，再枚举另外一个没有被匹配的DNA单链，如果它们能匹配，则都标记为匹配，答案加一。for (i = 0; i N; i+) if (!vsti)for (j = i + 1; j N; j+) if (!vstj) if (match(DNAi, DNAj) ans+;vsti = vstj = true;break;1046 Plane Spotting给出一个长度为N的非负整数序列（所有数不超过200），还有两个整数M和K，求前M个最优的长度不小

6、于K的连续子序列。连续子序列的优先级如何比较1、平均值大的序列优于平均值小的2、条件1相同情况下，长度大的序列优于长度小的3、条件1和2相同情况下，结束位置靠前的序列优于结束位置靠后的1N300，1M100，1K300解题思路使用结构体表示一个子序列，重写比较操作“”。对所有可能的子序列进行排序。struct period double aver;int length,ends;bool operator 1e-6) return a.averb.aver;if (a.length!=b.length) return a.lengthb.length;return a.endsb.ends;f

7、or (i=0;in;i+) temp=0;for (j=i+1;j=k) pcnt.length=j-i+1;pcnt.ends=j+1;pcnt.aver=(double)temp/(j-i+1);cnt+;sort(p,p+cnt);1051 Bikers Trip Odomete给出车前轮的直径转圈数以及时间求出车行走的路程和平均速度解题思路车轮周长 = 直径 圆周率路程 = 周长 转圈数平均速度 = 路程 / 时间1198 Substring用N个字符串拼成一个新的字符串要求新字符串字典序最小如： a ab ac则答案为：aabac1=N=8,每个字符串长度不超过100解题思路枚举n

8、!种情况，最多为8!=40320种情况从中找最优的接用STL中的next_permutation直接排序做法反例 b ba babbbasort ( sub, sub + n ) ;do string total=“”; for (i = 0 ; i n ; + + i ) total + = sub i ; ans = min ( ans , total ) ;while(next _permutation(sub, sub + n ) ) ;1176 Two Ends给出n个正整数排成一列，A和B轮流取数，只能取两端的数，最后取到的数的和较大的人胜利，A和B之间的差为分值；A可以自由选择策

9、略，B的贪心策略取两端中较大的数，如果相等则取左边的数；问A赢B的分值最大为多少。n=1000,且n为偶数。解题思路A尝试计算所有情况，并选出自己得分最多的情况；计算所有情况时，减少重复计算（动态规划），每个状态为当前数列的左右端点位置。int cal(int left,int right) if (right left) return 0; if (is_calleftright) return ansleftright; int ans_left = arrleft; if(arrleft+1arrright) ans_left += cal(left+1,right-1); else ans_left += cal(left+2,right); int ans_right = arrright; if (arrleft=dataj) fij=-data