北京大学ACM国际大学生程序设计竞赛课件5.ppt

问题求解与程序设计 第五讲 问题抽象,李文新 2004.2 2004.6,内容提要,Binary codes - 1147 讨论 1063 作业 1063,问题描述,给定一个N位的二进制串 b1 b2 bN-1 bN 将该串做旋转，即将b1移到bN后面，得到一个新的二进制串： b2 bN-1 bN b1,问题描述,对新的二进制串再做旋转，得二进制串 b3 b4 bN-1 bN b1 b2 重复旋转操作操作，可得N个二进制串，对这N个串排序，可得一个N*N的矩阵,问题描述,例如： 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0,问题描述,对它们做排序，得矩阵 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0,问题描述,问：给定这种矩阵的最后一列， 求出矩阵的第一行。 对于上面的例子，给出 1 0 0 1 0，要你的程序输出 0 0 0 1 1。,问题描述,输入文件名：bincode.in 第一行有一个整数 N 表示二进制串的长度 第二行有N个整数，表示矩阵最后一列从上到下的数值。,问题描述,输出文件名：bincode.out 第一行包括N个整数，表示矩阵第一行从左到右的数值。,问题描述,输入样例 bincode.in 5 1 0 0 1 0,问题描述,输出样例 bincode.out 0 0 0 1 1,问题描述,限制 1 = N = 1000,解法一 猜测法,计算输入列中包含 0 的个数 I 生成输出行：前I个为0，后N-I个为1 思路：因为矩阵按字母序排序，所以0应该在前面。 该算法不能保证正确，但对样例正确,解法二 穷举法,生成一个长度为N的全0序列 按规则将其旋转生成N*N矩阵 如果最后一列与输入相同，则输出开始的序列。 按字母序生成下一个长度为N的二进制序列，goto 2.,解法二 穷举法,显然这一算法不是最优的，但是它是正确的，因为它穷举了全部可能。,解法三 迭代法,初始化一个N行，最开始是0列的工作矩阵. 将输入列放在当前工作矩阵左边，对行排序. 如果矩阵列数小于N, goto 2. 输出第一行,解法三 迭代法,例子 （输入10010） 0 10 00 100 000 0 0 00 00 000 001 0 0 00 01 001 011 1 1 11 10 110 100 0 1 01 11 011 110,解法三 迭代法,例子 （输入10010） 000 1000 0001 10001 00011 0 001 0001 0011 00011 00110 0 011 0011 0110 00110 01100 1 100 1100 1000 11000 10001 0 110 0110 1100 01100 11000 输出：00011,解法三 迭代法,分析 该算法所需数时间是O(N3) N次迭代，每次要对一个N*N的矩阵排序,解法三 迭代法,证明 该算法的本质是逐一构造矩阵的前 I 列 对于I=1,重新排序后显然成立 对于IN，如果前I列就是矩阵的前I列，那么把最后一列加到前面，从序列的顺序来说，是正确的，重新对这I+1列排序保证了行顺序的正确性。,解法三 迭代法,分析 一个值得注意的现象是：每次排序总是把开头是0的行按原来的先后次序移到前面，而把开头是1的行按原来的先后次序移到后面。,解法四 线性算法,算法描述： 1. 计算输入列中0和1的个数，并用它们形成第一列.,解法四 线性算法,2. 生成一个Next数组，使得数组中的i个0指向最后一列第i个0的行数，数组中的第j个1指向最后一列第j个1的行数.,解法四 线性算法,3. 从第1行开始，按照Next指引的顺序 从k到Nextk, 每次把该行最后一列的数字取出生成第一行的相应数字。,解法四 线性算法,例如 输入 10010 有3个0，2个1，所以第1列一定是 0 0 0 1 1,解法四 线性算法,例如 输入 10010 2. 生成Next数组 Next 1 0 1 2 2 0 0 3 3 0 0 5 4 1 1 1 5 1 0 4,解法四 线性算法,例如 输入 10010 Next 23514 3. 沿着Next，根据 输入列，生成第一行 0 0 0 1 1,解法四 线性算法,证明 对于序列（1） b1 b2 bN-1 bN，左旋一位变成（2） b2 bN-1 bN b1 ，我们只要知道（1）左旋后得到的（2）在矩阵中是哪一行，就可以根据该行第一列的值得到 b2，依次类推得到b3 ， b4 ， ,解法四 线性算法,证明 假设矩阵中两行都以0开始，则它们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的行。对1开始的行有同样的性质。,解法四 线性算法,证明 例如 1 0 0 0 1 1 第1，2，3行以0 2 0 0 1 1 0 开始，左旋后0 3 0 1 1 0 0 到最后1列，但 4 1 0 0 0 1 前后顺序不变， 5 1 1 0 0 0 所以是2，3，5,解法四 线性算法,证明 该算法就是利用了这一性质，根据第1列和最后1列，直接算出第1行。,测试数据,20 组 100 位 全1 100位 全0 100位 0101 1000位 0011, 5位，10位，15位的小数据 长度为300-1000的随机序列 13个,算法分析初步,算法 解决问题的计算方法 衡量算法的标准： 正确性 时间效率 空间效率 清晰性 实现的简单性 最优性,算法分析初步,正确性 完整的算法包括输入、输出和从输入到输出的处理过程。验证算法的正确性是指证明该算法可以从输入经过算法所描述的过程一定可以到达预定的输出。 定理证明正确性 简单验证+几个样例验证,算法分析初步,时间效率 执行该算法所需时