[理学]算法习题.ppt

算法习题课第四章 国际大学生程序设计竞赛（ACM/ICPC）试题及分析 主讲：张子臻 习题题目 第一节 生成字符串（简单有哪些信誉好的足球投注网站生成） ★ 第二节 模式识别的“中心”问题（简单枚举） 第三节 划分凸多边形（Catalan数） 第四节 防卫导弹（经典DP） ★ 第五节 邮票问题（经典DP） ★ 第六节 骨牌矩阵（有哪些信誉好的足球投注网站） ★ 第七节 师生树（图论） 第八节 旅游预算（DP） 第九节 正整数竖式除法（高精度模拟） 第十节 移棋子（有哪些信誉好的足球投注网站） 第一节 生成字符串 本题取材于NWERC（西北欧）89C题。 问题描述: 假设字符串只由字符‘0’，‘1’，‘*’组成，其中字符‘*’表示该字符可由字符‘0’或‘1’替代。 现有一些字符串，根据这些字符串生成所有字符串。 如：{10，*1，0*}可生成{10，01，11，00 } {101，001，*01}可生成{101，001} 注意后一个例子中‘*01’并没有生成新的字符串。 输入格式: 文件的第一行是两个整数m,n。（1≤m≤15,1≤n≤2500）m表示字符串的长度，n表示字符串的个数。以下n行每行各有一个字符串。 输出格式: 输出所能生成的字符串的个数。 第一节 生成字符串 题目分析 m很小，生成的字符串总数不多—— 2^m 如何判重？hash思想——将生成的字符串看成二进制 ‘1**’将生成： ‘100’(2)=4，‘101’ (2)=5，‘110’ (2)=6，‘111’ (2)=7 如何生成？ 递归有哪些信誉好的足球投注网站生成’*’ 第一节 生成字符串 有哪些信誉好的足球投注网站程序框架 Type search(level) { // make_pruning() if (level==leaflevel) return evaluate_record(); for (each possible move i) { Makemove(i); Recordmove(i); search(next_level); unMakemove(i); } } 第一节 生成字符串 递归生成 void search(int level,int value) { if (level==m) { mark[value]=1; return; } if (s[level]==‘*’) { search(level+1,value); //’*’ for ‘0’ search(level+1,value|(1level)); //’*’ for ‘1’ } else search(level+1,value|((s[i]-’0’)level)); } 第一节 生成字符串 插曲-小练习 判断无符号整数n的二进制第k位是否为1 将n的二进制第k位置1(或取反) 求n div 2^k的快速方法 求n mod 2^k的快速方法 析取掉n二进制最后的1 不使用多余变量交换两整数 第三节 划分多边形 问题描述： 一个正凸N边形，可以用N-3条互不相交的对角线将正N边形分成N-2个三角形。任务：从键盘输入N（N=20），在显示器上输出不同分法的总数（不需要输出各种分法）。 输入格式：N=5 输出格式：TOTAL=5 例如：当N=5时，共有5种分法。 第三节 划分多边形 题目分析 经典catalan数问题 令h(1)＝1，catalan数满足递归式：h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n=2) 通项公式为： h(n)=C(2n-2,n-1)/n (n=1,2,3,...) 递推关系式为： h(n+1)=(4n-2)/(n+1)*h(n) 第三节 划分多边形 Catalan应用 括号化问题 矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？ 出栈次序问题 出栈序列：一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列。 排队买票：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) 第三节 划分多边形 Catalan应用 图划分问题划分三角形：将一个凸多边形区域分成三角形区域的方法数。 道路穿越：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 圆上线段相交：在圆