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

问题求解与程序设计第五讲问题抽象李文新2004.2–2004.6内容提要Binarycodes-1147讨论–1063作业–1063问题描述给定一个N位的二进制串b1b2…bN-1bN将该串做旋转，即将b1移到bN后面，得到一个新的二进制串：b2…bN-1bNb1问题描述对新的二进制串再做旋转，得二进制串b3b4…bN-1bNb1b2重复旋转操作操作，可得N个二进制串，对这N个串排序，可得一个N*N的矩阵问题描述例如：1000100011110000011001100问题描述对它们做排序，得矩阵0001100110011001000111000问题描述问：给定这种矩阵的最后一列，求出矩阵的第一行。对于上面的例子，给出10010，要你的程序输出00011。问题描述输入文件名：bincode.in第一行有一个整数N表示二进制串的长度第二行有N个整数，表示矩阵最后一列从上到下的数值。问题描述输出文件名：bincode.out第一行包括N个整数，表示矩阵第一行从左到右的数值。问题描述输入样例bincode.in510010问题描述输出样例bincode.out00011问题描述限制1=N=1000解法一猜测法计算输入列中包含0的个数I生成输出行：前I个为0，后N-I个为1思路：因为矩阵按字母序排序，所以0应该在前面。该算法不能保证正确，但对样例正确解法二穷举法1.生成一个长度为N的全0序列2.按规则将其旋转生成N*N矩阵3.如果最后一列与输入相同，则输出开始的序列。4.按字母序生成下一个长度为N的二进制序列，goto2.解法二穷举法显然这一算法不是最优的，但是它是正确的，因为它穷举了全部可能。解法三迭代法1.初始化一个N行，最开始是0列的工作矩阵.2.将输入列放在当前工作矩阵左边，对行排序.3.如果矩阵列数小于N,goto2.4.输出第一行解法三迭代法例子（输入10010）101000100000000000000001000001001011111110110100010111011110解法三迭代法例子（输入10010）10001000000110001000110001000100110001100110001100110110001100110011001100100011000100010110011011000110011000输出：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到Next[k],每次把该行最后一列的数字取出生成第一行的相应数字。解法四线性算法例如输入100101.有3个0，2个1，所以第1列一定是00011解法四线性算法例如输入100102.生成Next数组Next10122003300541115104解法四线性算法例如输入10010Next235143.沿着Next，根据输入列，生成第一行00011解法四线性算法证明对于序列（1）b1b2…bN-1bN，左旋一位变成（2）b2…bN-1bNb1，我们只要知道（1）左旋后得到的（2）在矩阵中是哪一行，就可以根据该行第一列的值得到b2，依次类推得到b3，b4，…解法四线性算法证明假设矩阵中两行都以0开始，则它们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的行。对1开始的行有同样的性质。解法四线性算法证明例如100011第1，2，3行以0200110开始，左旋后0301100到最后1列，但410001前后顺序不变，511000所以是2，3，5解法四线性算法证明该算法就是利用了这一性质，根据第1列和最后1列，直接算出第1行。测试数据20组•100位全1•100位全0•100位01…01•1000位0…01…1,•5位，10位，15位的小数据•长度为300-1000的随机序列13个算法分析初步算法–解决问题的计算方法衡量算法的标准：•正确性•时间效率•空间效率•清晰性–实现的简单性•最优性算法分析初步正确性•完整的算法包括输入、输出和从输入到输出的处理过程。验证算法的正确性是指证明该算法可以从输入经过算法所描述的过程一定可以到达预定的输出。•定理证明正确性•简单验证+几个样例验证算法分析初步时间效率–执行该算法所需时间•通常用执行关键语句的次数来衡量•常数时间•多项式时间•指数时间算法分析初步空间效率–程序占用的内存空间简单性•高效的算法未必易于实现•简单的代码未必最高效最优性讨论1063小结Binarycodes讨论–1063作业–1063