2013宁波小学生程序设计试卷解题报告by slzxlzw【精选】.doc

小学教育精选篇 问题 E: 哈夫曼编码（coding.pas） 题目描述 哈夫曼编码是一种编码方式， 是可变字长编码的一种， 由 Huffman 于 1952 年提出。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字， 有时称之为最佳编码，一般就叫 Huffman 编码。简单地来说，就是出现概率高的字符使用较短的编码， 反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低， 从而达到无损压缩数据的目的。现在请你模拟这样的原则对给定的一个字符串进行字母统计。 输入 输入文件 coding.in，只有一行，是一个字符串，由小写英文字母组成，长度不超过255 个字符。 输出 输出文件 coding.out，有若干行，每行有两部分组成：一个字母和该字母出现的频率，中间用一个空格分隔，并按频率高低排列，频率相同时则按字母的 ASC 码的先后顺序排列。 样例输入 soon 样例输出 o 2 n 1 s 1 提示 【题目分析】 给出一段字符串，在字符串中出现的字符按出现次数从多到少输出，出现次数一样按字母表顺序输出。 【算法分析】 模拟。开一个记录字符出现次数的数组，然后按照题意输出。 【参考程序】 var ch:char; a:array[a..z]of longint; max,i:longint; begin while not eoln do begin read(ch); inc(a[ch]); //记录出现次数 if a[ch]max then max:=a[ch]; //记录出现最大出现次数 end; for i:=max downto 1 do //按出现次数从大到小输出 for ch:=a to z do //相同的按字母表顺序输出 if a[ch]=i then writeln(ch, ,a[ch]); end. 问题 F: 立方和（cubsum.pas） 时间限制: 1 Sec??内存限制: 128 MB提交: 37??解决: 21[ HYPERLINK 38:8090/JudgeOnline/submitpage.php?cid=1017pid=5langmask=0 提交][ HYPERLINK 38:8090/JudgeOnline/problemstatus.php?id=1793 状态][ HYPERLINK 38:8090/JudgeOnline/bbs.php?pid=1793cid=1017 讨论版] 题目描述 现给出一个三位数， 先对这个三位数的各位数字的立方求和，然后再对求出的和中的各位数字的立方求和， 如此一直继续下去， 判断最后能否得到一个不再变化的固定值。如能得到一个固定值，就求出这个固定值；如果不能，则输出提示信息“error” 。另外请注意，在求解过程中，若某一次求和过程中得到的值超过三位数，则取该数的低三位继续往下运算……例如，对于三位数 111，则第一次计算应是 1×1×1+1×1×1+1×1×1=3，第二次计算应是 0×0×0+0×0×0+3×3×3=27，第三次计算应是0×0×0+2×2×2+7×7×7=351，第四次计算应是 3×3×3+5×5×5+1×1×1=153，第五次计算应是 1×1×1+5×5×5+3×3×3=153，与第四次计算的结果相同，这时可不再计算，输出固定值 153。亲爱的同学，请你也来计算一下。 输入 输入文件 cubsum.in，只有一行，是一个三位数。 输出 输出文件 cubsum.out，也只有一行，如能得到一个固定值，则输出这个固定值；如不能，则输出一个提示信息“error” 。 样例输入 111 样例输出 153 提示 输入样例 2：102输出样例 2：error 【题目分析】 对一个三位数字（多于三位取最低三位，少于三位添零计算）进行各个数位立方求和。判断是否最后变成一个固定的数。 【算法分析】 对于一个固定不变的数，则是与前一次相同，就是求立方和前相同。而没有固定值的数，则是在前面所有变化的数中出现过（当然排除前一次），因为会形成一个循环。像这样我们只要开一个记录是否出现过某个数的数组（0..1000）(不包括前一次），如果出现过就没有固定值。最坏情况也就o(1000),是个常数。 【参考程序】 var x,y,t:longint; a:Array[0..10000]of boolean; begin read(x); repeat t:=x; //保存一遍，因为下面x会变 y:=sqr(x mod 10)*(x mod 10); //求立方和 x: