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

《北京大学ACM国际大学生程序设计竞赛课件5.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、问题求解与程序设计第五讲问题抽象李文新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问题

2、描述问：给定这种矩阵的最后一列，求出矩阵的第一行。对于上面的例子，给出10010，要你的程序输出00011。问题描述输入文件名：bincode.in第一行有一个整数N表示二进制串的长度第二行有N个整数，表示矩阵最后一列从上到下的数值。问题描述输出文件名：bincode.out第一行包括N个整数，表示矩阵第一行从左到右的数值。问题描述输入样例bincode.in510010问题描述输出样例bincode.out00011问题描述限制1<=N<=1000解法一猜测法计算输入列中包含0的个数I生成输出行：前I个为0，后N-I个为1思路：因为矩阵按字母序排序，

3、所以0应该在前面。该算法不能保证正确，但对样例正确解法二穷举法生成一个长度为N的全0序列按规则将其旋转生成N*N矩阵如果最后一列与输入相同，则输出开始的序列。按字母序生成下一个长度为N的二进制序列，goto2.解法二穷举法显然这一算法不是最优的，但是它是正确的，因为它穷举了全部可能。解法三迭代法初始化一个N行，最开始是0列的工作矩阵.将输入列放在当前工作矩阵左边，对行排序.如果矩阵列数小于N,goto2.输出第一行解法三迭代法例子（输入10010）010001000000000000000010000010010111111101101000101

4、11011110解法三迭代法例子（输入10010）0001000000110001000110001000100110001100110001100110110001100110011001100100011000100010110011011000110011000输出：00011解法三迭代法分析该算法所需数时间是>O(N3)N次迭代，每次要对一个N*N的矩阵排序解法三迭代法证明该算法的本质是逐一构造矩阵的前I列对于I=1,重新排序后显然成立对于I

5、序保证了行顺序的正确性。解法三迭代法分析一个值得注意的现象是：每次排序总是把开头是0的行按原来的先后次序移到前面，而把开头是1的行按原来的先后次序移到后面。解法四线性算法算法描述：1.计算输入列中0和1的个数，并用它们形成第一列.解法四线性算法2.生成一个Next数组，使得数组中的i个0指向最后一列第i个0的行数，数组中的第j个1指向最后一列第j个1的行数.解法四线性算法3.从第1行开始，按照Next指引的顺序–从k到Next[k],每次把该行最后一列的数字取出生成第一行的相应数字。解法四线性算法例如输入10010有3个0，2个1，所以第1列一定是00

6、011解法四线性算法例如输入100102.生成Next数组Next10122003300541115104解法四线性算法例如输入10010Next235143.沿着Next，根据输入列，生成第一行00011解法四线性算法证明对于序列（1）b1b2…bN-1bN，左旋一位变成（2）b2…bN-1bNb1，我们只要知道（1）左旋后得到的（2）在矩阵中是哪一行，就可以根据该行第一列的值得到b2，依次类推得到b3，b4，…解法四线性算法证明假设矩阵中两行都以0开始，则它们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的

7、行。对1开始的行有同样的性质。解法四线性算法证明例如100011第1，2，3行以0200110开始，左旋后0301100到最后1列，但410001前后顺序不变，511000所以是2，3，5解法四线性算法证明该算法就是利用了这一性质，根据第1列和最后1列，直接算出第1行。测试数据20组100位全1100位全0100位01…011000位0…01…1,5位，10位，15位的小数据长度为300-1000的随机序列13个算法分析初步算法–解决问题的计算方法衡量算法的标准：正确性时间效率空间效率清晰性–实现的简单性最优性算法分析初步正确性完整的算法包括输入、输出

8、和从输入到输出的处理过程。验证算法的正确性是指证明该算法可以从输入经过算法所描述的过程一定可以