算法设计chapter1-2.ppt

算法设计与分析,习题课1(第一、二章) 2010-09-26,声明：本课件由往届算法课课件修改而成。,Self Introduction,Name: 陈宇恒 BBS Nickname: hoveychen Email: QQ/MSN: contact me later Sicily系统的维护 欢迎各种bug、改进，甚至举行比赛、出题等。,Exercise Environment,推荐IDE VS2005、2008、2010 Dev-Cpp；VC6.0 推荐语言 C(not C+) Try to debug with printf or cout,Useful URL,Sicily Online Judge ACMICPC in argo BBS /bbsdoc?board=ACMICPC,第一章作业,1198 SubString 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈,1198 Substring,题目大意： 用N个字符串拼成一个新的字符串 要求新字符串字典序最小 如： a ab ac 则答案为：aabac,1198 Substring,解法一：贪心 先对N个字符串按字典序排序 后从小到大拼在一起 如：a ab ac 排序后就是 a ab ac 最后的字符串即是 aabac 又如：b ac bd abc 排序后是 abc ac b bd 最后的字符串即是 abcacbbd,错误,1198 Substring,解法一：贪心 先对N个字符串按字典序排序 后从小到大拼在一起,反例？越简单的反例越好 b ba bba? bab!,1198 Substring,真解法一：枚举 8！= 40320 KISS = Keep It Simple, Stupid 直接枚举所有8！种组合，从中找最优的 正确性：所有方案都枚举了，所以绝对正确 效率：8! * 100 * 8 = 32032000 可以应付,Tips,刚才提到了 效率：8! * 100 * 8 = 32,032,000 可以应付 那其实这个运算量又是什么概念呢？ 在我自己的2.5GHz CPU的电脑上面跑一个空循环， 每个枚举耗费比空循环多10-100倍 合理的运算量估计10-100M，复杂度O(1,000,000),1198 Substring,解法二：排序 比较函数定义为 bool cmp(a, b) return ab ba; 证明提示： 方法一: 将字符串看作26进制数，证明如下推理成abba and bccb implies acca 方法二: 数学归纳法,第一章作业,1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈,1029 Rabbit,题目大意： 每对成年兔子每个月会生一对小兔子 小兔子m个月后会变成大兔子（成年兔子） 一开始只有一对大兔子 d个月后总共有多少对兔子 注意，这些兔子不会老死，也不会被杀死，更不会自杀，总之就是不会死,1029 Rabbit,解题思路： 题目也说了，m=2时就是Fibonacci 即 Fn = Fn-1 + Fn-2 即 Fn = Fn-1 + Fn-m 边界： Fn = 1, 如果 n = 0 注意高精 搞定,Tips,What is 高精？ 使用数组表示一个数 常用运算 加，减，乘，除，取余 值得注意的细节 数的长度、前导0、进位的先后顺序 特别注意数字0的处理,第一章作业,1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈,1028 Hanoi Tower Sequence,题目大意： 经典的汉诺塔 n个盘编号，从小到大 1n 问：移动的序列中第k步移的是哪个盘 如： n = 3时：1 2 1 3 1 2 1 n = 4时：1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 序列与n无关，递归性很强,1028 Hanoi Tower Sequence,解题思路： 定义n个盘子时的序列为S(n) S(n)=S(n-1)nS(n-1) 令S(1)=1 查找S()中的第p个元素 解决n个盘子的hanoi tower需要2n-1步 序列中心位置为n，若p在中心则输出n； 否则递归求解 结果为k的二进制表示中末尾0的个数加1,第一章作业,1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈,1193 Up the Stairs,题目大意： N个人，F级楼梯，从0级搬货物到F级 一人只能搬一件，每一级楼梯时间为1 第0级（即地板）有B件货物 N个人的初始状态不一定在地板，可能在某级，并有两种可能状态：搬着东西上去，或刚搬完正在走下来 拿放货物不需要时间 要多久才能将地板的货物全部搬上去,1193 Up the Stairs,解题思路： 碰撞时两人交换速度,也可看成两人继续向原来的方向行进 可以独立的考虑每个人的搬运活动 KISS：可以二分答案,Tips,What is 二分？ Example 1 4 5 8 9 10 12 15 1 4 5 8 1 4 4 两个主要元素：布尔查询，区段,第一章作业,1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈,1021 Couples,题目大意： N对夫妇坐成一圈 如果某对夫妇挨着坐将被从圈中移走 重复以上操作 问最后会不会全部被移走 如1 3是一对，2 4是一对 如果1 3 2 4（4与1相邻）则 YES 如果1 2 3 4（4与1相邻）则 NO,1021 Couples,解题思路 无解的情况，互相嵌套 a.b.a.b 类似于括号匹配，可将n对夫妇看成n种括号 用一个栈来模拟，将括号逐个push到栈里 当栈顶存在匹配对时进行pop操作 看最后栈顶是否为空,1021 Couples,如样例： 4 1 4 2 3 5 6 7 8,1,2,3,4,5,6,7,8,1021 Couples,如样例： 2 1 3 2 4,1,2,3,4,第一章作业,1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈 1176 Two Ends,1176 Two Ends,题目大意 给定偶数项的数列，轮流从两端取。 玩家一允许任意策略，玩家二采用贪心策略（每次取两端大者） 最终根据取数的总和大小判断胜负 问玩家一最多能赢多少分？,1176 Two Ends,与上课课件上面的题目类似 问题不一样，解法不一样 解法 二维状态的动态规划 算法时间复杂度O(n2),第二章作业,1150 简单魔板 1151 魔板 1515 魔板C 1007 数组与下标（二维数组） 简单 1036 数组与下标（二维数组） 简单 1027 简单 1006 栈与回溯 简单 5!搜索 1156 深搜 指针 简单 树的遍历 1034 队列与搜索,1150 1151 1515 魔板,题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换,1,2,3,4,5,6,7,8,1150 1151 1515 魔板,题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 每行循环右移一格,1,2,3,4,5,6,7,8,1150 1151 1515 魔板,题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 每行循环右移一格 中间四块顺时针转一格,1,2,3,4,5,6,7,8,1150 1151 1515 魔板,题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 每行循环右移一格 中间四块顺时针转一格 给定一个终止状态，求最小操作数及方案,1,2,3,4,5,6,7,8,1,2,4,5,6,7,8,3,1150 1151 1515 魔板,解题思路 对模板进行状态搜索 由一种状态可以转移到另外三种状态，搜索树为一棵三叉树 在这棵三叉树上搜索，目的是求出最优解,1150 1151 1515 魔板,算法一：盲目DFS 对这棵三叉树进行DFS 若想求得最优解，需要遍历整棵树 需要进行重复扩展 优化： 若已找到一个可行解，可剪去大于等于这个深度的所有子树,评价：,效果：,加优化后勉强可过1150,很傻很天真,1150 1151 1515 魔板,算法二：BFS 对这棵三叉树进行BFS 第一个可行解即是最优解,评价：,效果：,轻松切掉1150，但过不了1151,很慢很暴力,1150 1151 1515 魔板,算法三：DFS/BFS + 判重 可将一个魔板的状态编码，用8！以内的整数表示一个状态 可用8！的数组判重 不管DFS还是BFS，最多搜8！=40320个状态,评价：,效果：,轻松切掉以上三题,很快很易写,第二章作业,1150 简单魔板 1151 魔板 1515 魔板C 1007 数组与下标（二维数组） 简单 1036 数组与下标（二维数组） 简单 1027 简单 1006 栈与回溯 简单 5!搜索 1156 深搜 指针 简单 树的遍历 1034 队列与搜索,1007 To and Fro,题目大意： 按照某种顺序输出数组中的元素 解题思路： Just do it,1036 Crypto Columns,题目大意： 模拟一种加密方法 解题思路： Just do it, too,1027 MJ, Nowhere to Hide,题目大意： 根据ip找出主ID和马甲 找某个字符串是否在之前出现过 解题思路： 字符串查找,1006 Team Rankings,题目大意： 对于两个排列p, q，定义 distance( p, q )为在p, q中出现的相对次序不同的元素的对数。相当于以p为基准，求q的逆序数。 给出n个5元排列，构造一个排列，使得该排列对n个排列的distance之和最小。,1006 Team Rankings,解题思路： 可以使用深度(或宽度)优先法生成排列。 求逆序数的算法 平方级枚举 n2 规模较大时可采用归并排序 nlogn,Tips,What is求逆序数的快速算法? 归并排序的原理 What is nlogn? 通常出现的算法复杂度级别 O(mn),O(n!),O(nm),O(n),O(logn),O(1) 当n10000时，至少要O(nlogn),1156 B