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

《北京大学ACM国际大学生程序设计竞赛课件5.ppt》由会员分享，可在线阅读，更多相关《北京大学ACM国际大学生程序设计竞赛课件5.ppt（38页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、问题求解与程序设计第五讲 问题抽象李文新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 11 1 0 0 00 0 1 1 00 1 1 0 0问题描述对它们做排序，得矩阵0 0 0 1 10 0 1 1

2、 0 0 1 1 0 01 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.in51 0 0 1 0问题描述输出样例bincode.out0 0 0 1 1问题描述限制1 =N O(N3)N次迭代，每次要对一个N*N的矩阵排序解

3、法三 迭代法证明该算法的本质是逐一构造矩阵的前 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行开始，按照Ne

4、xt指引的顺序 从k到Nextk,每次把该行最后一列的数字取出生成第一行的相应数字。解法四 线性算法例如 输入 100101.有3个0，2个1，所以第1列一定是00011解法四 线性算法例如 输入 100102.生成Next数组Next10122003300541115104解法四 线性算法例如 输入 10010 Next 235143.沿着Next，根据 输入列，生成第一行0 0 0 1 1解法四 线性算法证明对于序列（1）b1 b2 bN-1 bN，左旋一位变成（2）b2 bN-1 bN b1，我们只要知道（1）左旋后得到的（2）在矩阵中是哪一行，就可以根据该行第一列的值得到 b2，依次类

5、推得到b3，b4，解法四 线性算法证明假设矩阵中两行都以0开始，则它们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的行。对1开始的行有同样的性质。解法四 线性算法证明例如 1 0 0 0 1 1 第1，2，3行以0 20 0 1 1 0 开始，左旋后0 30 1 1 0 0 到最后1列，但 41 0 0 0 1 前后顺序不变，51 1 0 0 0 所以是2，3，5解法四 线性算法证明该算法就是利用了这一性质，根据第1列和最后1列，直接算出第1行。测试数据20 组100 位 全1100位 全0100位 01011000位 0011,5位，10位，15位的小数据长度为300-1000的随机序列 13个算法分析初步算法 解决问题的计算方法衡量算法的标准：正确性时间效率空间效率清晰性 实现的简单性最优性算法分析初步正确性完整的算法包括输入、输出和从输入到输出的处理过程。验证算法的正确性是指证明该算法可以从输入经过算法所描述的过程一定可以到达预定的输出。定理证明正确性简单验证+几个样例验证算法分析初步时间效率 执行该算法所需时间通常用执行关键语句的次数来衡量常数时间多项式时间指数时间算法分析初步空间效率 程序占用的内存空间简单性高效的算法未必易于实现简单的代码未必最高效最优性讨论1063小结Binary codes讨论 1063 作业 1063