C语言竞赛题目大全(5)

在标准输出上打印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 …… 此处隐藏：3283字，全部文档内容请下载后查看。喜欢就下载吧 ……