acm指导书.doc

acm指导书 篇一：acm实验指导书(新版) 实验1——统计字符数 1 实验2——串匹配问题 3 实验3——0/1背包问题 4 实验4——哈夫曼编码 5 实验1——统计字符数 1．实验题目 判断一个由a-z 这26 个字符组成的字符串中哪个字符出现的次数最多 2．实验目的 熟练掌握在acm竞赛中常出现的有关字符串操作题目 3．实验要求 设计实验程序验证分析结果。 4．输入输出样例 Input：第1 行是测试数据的组数n，每组测试数据占1 行，是一个由a-z 这26 个字符组成的字符串，每组测试数据之间有一个空行，每行数据不超过1000 个字符且非空。 Output：n 行，每行输出对应一个输入。一行输出包括出现次数最多的字符和该字符出现的次数，中间是一个空格。 如果有多个字符出现的次数相同且最多，那么输出ascii 码最小的那一个字符。 Sample Input 2 abbccc adfadffasdf Sample Output c 3 f 4 分析： 每读入一个字符串，将这个字符串作为一个字符型数组，依次判断每个数组元素分别是什么字母。统计出各个字母在字符串中分别出现了多少次，找到出现次数最多的。这里要注意三点： (1) 输入字符串时，可以象一般变量一样，一次输入一个字符串。scanf 函数通过空格或者回车字符判断一个字符串的结束。而一般数组在输 入时，每次只能输入一个数组元素。 (2) 字符串是一个字符型数组，可以象访问一般数组的元素一样，通过下 标访问其中的各个元素。scanf函数输入字符串时，并不返回所输入字符串的长度。可以使用字符串处理函数strlen函数计算字符串中包括多少个字符。 (3) 输入的字符串中，可能有多个字符出现的次数相同且最多的情况。此 时要输出ascii 码最小的那一个字符。 实验2——串匹配问题 1．实验题目 给定一个文本，在该文本中查找并定位任意给定字符串。 2．实验目的 深刻理解并掌握蛮力法的设计思想； 提高应用蛮力法设计算法的技能； 理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。 3．实验要求 实现BF算法； 4．输入输出样例 Input：要求输入多组样例，第1 行是测试数据的组数n，每组测试数据占1 行，先输入主串，然后输入相应的子串，字符串长度不超过1000 Output：子串输入结束会返回串的匹配结果，如果是在第三位开始匹配的，则返回数字3，否则返回匹配失败。 Sample Input 2 abcaddasd sad abcdefgh defg Sample Output 匹配失败 4 5．算法描述 实验3——0/1背包问题 1．实验题目 给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大? 2．实验目的 （1）掌握回溯法的设计思想； （2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径； （3）考察回溯法求解问题的有效程度。 3．实验要求 （1）设计可能解的表示方式，构成解空间树； （2）设计回溯算法完成问题求解； （3）设计测试数据，统计有哪些信誉好的足球投注网站空间的结点数； 4．输入输出样例 Input：第一行二个整数 n 和m，分别为物品数和背包容量（nlt;=30，mlt;=200）。 接下来有 n 行，每行有两个实数wi，ci，分别为背包 i 的重量和价值。 Output：每个测例的输出占一行，输出一个整数，使得装入背包中物品的总价值最大。 Sample Input 10 4 2 1 3 3 4 5 7 9 Sample Output 12 5．实现提示 为了便于求解，将物品按单位重量价值从大到小排序，这样只要顺序考察各物品即可。设bestP表示当前背包获得的最大价值，背包的当前的重量和获得的价值分别用变量cw和cp表示，物品的重量存储在数组w[n] 中，价值存储在数组p[n]中，算法如下： 1．实验题目 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2．实验目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 3．实验要求 （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档