-2 1 4 -1 0 0 第12题 数与表达式 <0> 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。 输入数据： 一个正整数，以命令行参数的形式提供给程序。 输出数据： 在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序 列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。 例如，对于15，其输出结果是： 1 2 3 4 5 4 5 6 7 8 对于16，其输出结果是： NONE <1> 重叠区间大小（20分） 题目描述： 请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。 对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。 例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为[10 12]，其大小为3；行(20 10)和（20 30）的重叠区间大小为1。 输入数据： 程 序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有用一个空格分隔的2个正整数，这2个正整数的 大小次序随机，每个数都在1和2^32-1之间。（为便于调试，您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。） 输出数据： 在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。 评分标准： 程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。 <2> 题目描述： 请编写程序，根据指定的对应关系，把一个文本中的字符串替换成另外的字符串。 输入数据： 程 序读入已被命名为text.txt和dict.txt的两个输入数据文本文件，text.txt为一个包含大量字符串（含中文）的文本，以 whitespace为分隔符；dict.txt为表示字符串（s1）与字符串（s2）的对应关系的另一个文本（含中文），大约在1万行左右，每行两个字 符串（即s1和s2），用一个\\t或空格分隔。dict.txt中各行的s1没有排序，并有可能有重复，这时以最后出现的那次s1所对应的s2为准。 text.txt和dict.txt中的每个字符串都可能包含除whitespace之外的任何字符。text.txt中的字符串必须和dict.txt 中的某s1完全匹配才能被替换。（为便于调试，您可下载测试text.txt和dict.txt文件，实际运行时我们会使用不同内容的输入文件。） 输出数据： 11

在标准输出上打印text.txt被dict.txt替换后了的整个文本。 评分标准： 程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。 第13题 低频词过滤 <1>：低频词过滤（40分） 题目描述： 请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多个单词都出现最少的次数，则将这些单词都删除。 输入数据： 程序读入已被命名为corpus.txt的一个大数据量的文本文件，该文件包含英文单词和中文单词，词与词之间以一个或多个whitespace分隔。（为便于调试，您可下载测试corpus.txt文件，实际运行时我们会使用不同内容的输入文件。） 输出数据： 在标准输出上打印删除了corpus.txt中出现次数最少的单词之后的文本（词与词保持原来的顺序，仍以空格分隔）。 评分标准： 程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。 题目描述： 一个Internet站点集合，可以用如下的方式来描述站点和站点之间的链接引用关系： s 1 2 3 4 1 / 4 0 3 2 3 / 4 5 3 2 2 / 2 4 6 1 4 / 其中与s(site)同行和同列的数字都表示站点号，其他每个数字表示一个站点到另一个站点的超文本链接数。如果站点A有到另一个站点B的直接链接或间接（指通过一个或多个直接链接）链接，则称站点A有到站点B的访问关系，或称站点B可以被站点A访问到。例如，上面描述了一个有4个站点链接关系的站点集合，第一行 / 4 0 3 表示站点1到站点1，2，3，4的超文本链接数。 请编写程序: 1） 将一个有N个站点的集合划分成满足下面所有条件的站点子集（这些子集的union组成了该N个站点集合）： a) 当任一子集中的站点数大于1时，该子集内至少存在一个站点有到该子集内所有其他站点的访问关系； b) 当任一子集中的站点数大于1时，该子集内的任一站点至少可以被该子集内的某一站点访问到； c) 两个不同子集中的任意两个站点之间不存在任何访问关系。 2） 裁减这些子集内的站点之间现有的链接关系，使得被裁减后的各子集内的站点依然可以满足上述所有条件，同时使得子集内的站点之间的链接总数相加之和为最小。 假如上面的站点集合是这N个站点集合中的一个子集，它满足了条件a)：4可以访问到3，也可以访问到2和1；也满足了条件b)：站点4可以被站点3访问到，等等。对该站点集合进行裁减使其仍然满足条件a和b，并使得其链接总数之和为最小的结果为： s 1 2 3 4 1 / 0 0 0 2 0 / 0 0 3 2 0 / 2 4 0 1 4 / 这里，站点4可以访问到站点3和2，站点4也可以访问到站点1（通过站点3间接访问）；此外，站点3可以访问到站点4；最小链接总数相加为2＋2＋1＋4=9。 输入数据： 程序读入已被命名为sites.txt的完全如上所示的N*N矩阵的输入数据文本文件，N不大于10万（N即为行数和列数），输入文件的每一行的列和列之间用一个\\\\t分隔，行和行之间用\\\\n分隔。 输出数据： 按行输出满足题目要求的每个子集内的站点数以及裁减后的最小链接总数之和，数和数之间都以一个空格分隔。如上述子集和最小链接总数为：1 2 3 4 9 如果输入数据无满足题目要求的子集存在，则输出NONE。 <2> 题目描述： 一个智能决策系统可以由规则库和事实库两部分组成，假定规则库的形式为： Ri C1 & C2 & … & Cn->A 表示在条件C1，C2，… 和Cn都满足的前提下，结论A成立（即采取行动A）；Ri表示这是规则库中的第i条规则。事实库则由若干为真的条件（即命题）所组成。 对一个新的待验证的命题Q，可使用数据驱动或目标驱动两种推理方式之一，来确认它是否可由某规则库和事实库推出： 1） 数据驱动的推理是指从事实库开始，每次试图发现规则库中某条能满足所有条件的规则，并将其结论作为新的事实加入事实库，然后重复此过程，直至发现Q是一个事实或没有任何新的事实可被发现；

12

2） 目标驱动的推理是指从目标假设Q出发，每次试图发现规则库中某条含该假设的规则，然后将该规则的前提作为子目标，确认这些子目标是否和事实库中的事实相匹配，如果没有全部匹配，则重复此过程，直至发现新的子目标都为真或不能再验证子目标是 否为真。 例如，一个规则库为： R1 X & B & E -> Y R2 Y & D -> Z R3 A->X 事实库为： A B C D E 如果想知道命题Z是否为真，数据驱动的推理是从A B C D E开始，依次匹配规则R3（得到新事实X），R1（得到新事实Y）和R2，得到Z为真的事实；目标驱动的推理是从假设目标Z开始，依次匹配规则R2（得到新的子目标Y），R1（得到新的子目标X）和R3，得到假设Z为真的结论。 请编写程序正确、高效的实现这两种推理方式。 输入数据： 程序需要两个命令行参数： 1） <推理方式>：data|goal，分别表示程序应采用数据驱动的推理或目标驱动的推理； 2） <命题>：如Z。 此外，程序还需读入已被命名为rules.txt的规则库和已被命名为facts.txt的事实库。规则库中的规则可能在千量级，按R1,R2,R3…依次按行排列的，每行一条规则，每条规则都以Ri C1 & C2 & … & Cn->A的形式表示，Ri和C1之间有1个或多个空格，Ci和&之 间，Cn和->之间，以及->和A之间可以有0或多个空格。事实库中的各事实之间用1个\\\\n隔开，每行一个事实。 输出数据： 如果Z能被推理为真，则输出： TRUE <推理方式：data或goal> <用空格隔开的规则序列：以在所输入的推理方式下，推 出该命题为真的规则被激活的顺序排列> 例如：TRUE goal R2 R1 R3 如果Z不能被推理为真，输出： UNCERTAIN <3>题目描述： 八方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动。例如，假设一个3x3矩阵的初始状态为： 8 0 3 2 1 4 7 6 5 目标状态为： 1 2 3 8 0 4 7 6 5 则一个合法的移动路径为： 8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3 2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。 请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用C/C++实现。 输入数据： 程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。 输出数据： 如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。 自测用例： 如果输入为：start.txt和goal.txt，则产生的输出应为：

13

5 又例，如果用 7 8 4 3 5 6 1 0 2 替换start.txt中的内容，则产生的输出应为： 21 第14题 矩阵应用 (1).给定一个整数N，生成一个N*N的矩阵，矩阵中元素取值为1至N2，1在左上角，其余各数按顺时针方向旋转前进，依次递增放置。例如，当N=4时，矩阵中的内容如下： 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 (2).给定n(3 £ n £ 50000)个闭区间[ai, bi](1 £ i £ n, ai,bi均为非负整数)，将这些区间合并为不相交的闭区间。输入文件的第一行包含一个整数n，为区间的数目。以下有n行，每行各包括两个空格分隔的整数ai 和 bi，表示一个区间[ai, bi](0 £ ai £ bi £ 1000000)。计算结果写在标准输出上，各区间按照升序排列输出。每一行包含两个用空格分开的整数，分别描述一个区间的上下界。例如，对于下列输入数据： 5 5 6 1 4 10 10 6 9 8 10 输出为： 1 4 5 10 (3)从标准输入中读入N(1 from <原位置> to <新位置> 其中<盘子编号>为a或b，其中是一个小于等于n的正整数，在初始状态下尺寸相同的盘子中a盘在b盘之上，<原位置>和<新位置>均为字母ABC中的一个。例如，移动序列的第一个动作可能是move 1a from A to C。 (5).从标准输入上读入一个由数字和四则运算符组成的后缀表达式，将其转换为中缀表达式。后缀表达式中的运算符不超过15个，数字可以是整数，也可以是带有小数部分的浮点数，数字和运算符之间由空格分隔。转换后的中缀表达式中不应出现不必要的括号和空格，且转换前后各运算数的出现顺序不变。例如，对于后缀表达式： 4 7 - 2.1 5 + * 7.1 9 - / 输出 (4-7)*(2.1+5)/(7.1-9) (6).有大、中、小三个酒桶，分别能装A斤、B斤和C斤酒，其中A、B、C均为整数，A=B+C，B>C>0，且A为偶数。现在大桶装满了酒，另外两个桶都空着。写程序求解用这三个桶将酒平分成为两份的操作序列。当无解时输出字符串“No”。 (7) 读入一个不超过20000000个字符的正文文件，统计其中所有由字母组成的单词及其所在的行号。文件中各个单词之间以空白符或标点分隔，区分大小写。按单词的字典序在标准输出上输出统计结果，输出格式为:

… ，每个单词一行，其中是单词，是行号。行号之间由空格分隔，按升序排列，不得重复，即当一个单词在一行出现多次时，只输出该行号一次。 (8) 写一个程序，列出环境变量PATH中包含的所有目录的路径名。注意，Unix/Linux上PATH中各个路径名之间的分隔符与Windows上的不同。使用条件编译，使你的程序可以适用于这两种系统。 第15题 经典问题 1．将７万元投资到Ａ，Ｂ，Ｃ三项目上， 其利润见下表： 投资额(万元)│ １ ２ ３ ４ ５ ６ ７ ──────┼────────────────────

14

项 Ａ利润 │0.11 0.13 0.15 0.24 0.24 0.30 0.35 Ｂ利润 │0.12 0.16 0.21 0.25 0.25 0.29 0.34 目 Ｃ利润 │0.08 0.12 0.20 0.26 0.26 0.30 0.35 如何分配投资额，使获得的利润最大。 2．将真分数分解为埃及分数（分子为1 的分数称为埃及分数）。 输入一个真分数，请将该分数分解为埃及分数。 如：8/11=1/2+1/5+1/55+1/110 3．在Ｎ行Ｎ列的数阵中, 数Ｋ（１〈＝Ｋ〈＝Ｎ）在每行和每列中出现且仅出现一次，这样的数阵叫Ｎ阶拉丁方阵。例如下图就是一个五阶拉丁方阵。编一程序，从键盘输入Ｎ值后，打印出所有不同的Ｎ阶拉丁方阵，并统计个数。 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 4．十个小孩围成一圈分糖果，老师分给第一个小孩10块，第二个小孩2块，第三个小孩8块，第四个小孩22块，第五个小孩16块，第六个小孩4块，第七个小孩10块，第八个小孩6块，第九个小孩14块，第十个小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？ 第16题 歌手大赛问题 题目：青年歌手参加歌曲大奖赛，有10个评委进行大粪，试编程求这位选手的平均得分。 3种方法：分别要求使用到排序，数组，函数，指针。 分析：这道题的核心程序是排序，将评委打的10个分数利用数组按增序（或降序）排列，计算数组中除了第一个和最后一个分数以外的数以外的数的平均分 答案： #include double Aver(int p[],int count) //求出结果，p为整型数组，count为数组大小 { double result=0; for(int i=0;i

15