C语言经典例题大全(4)

输入数据：

程序读入已被命名为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是一个事实或没有任何新的事实可被发现；

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，则产生的输出应为： 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 &pound; n &pound; 50000)个闭区间[ai, bi](1 &pound; i &pound; n, ai,bi均为非负整数)，将这些区间合并为不相交的闭区间。输入文件的第一行包含一个整数n，为区间的数目。以下有n行，每行各包括两个空格分隔的整数ai 和 bi，表示一个区间[ai, bi](0 &pound; ai &pound; bi &pound; 1000000)。计算结果写在标准输出上，各区间按照升序排列输出。每一行包含两个用空格分开的整数，分别描述一个区间的上下界。例如，对于下列输入数据： 5 5 6 1 4 10 10 6 9 8 10

输出为：

1 4 5 10

(3)从标准输入中读入N(1<N<10000)行以换行符结束且长度不超过2048的字符串，并在输入结束后输出其中最长10行的输入序号、长度和内容。当有多行长度相等的最长行时，输出最先输入的行的信息。参考【例2-7】的讨论，分别使用不同的方法实现这一程序，比较各种方法的运行效率。

(4).写出程序求解Hanoi双塔问题。从标准输入上读入正整数n(n < 12)，在标准输出上输出盘子的移动动作。盘子的尺寸由1到n，输出数据格式为：

move <盘子编号> from <原位置> to <新位置>

其中<盘子编号>为<d>a或<d>b，其中<d>是一个小于等于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个字符的正文文件，统计其中所有由字母组成的单词及其所在的行号。文件中各个单词之间以空白符 …… 此处隐藏：2894字，全部文档内容请下载后查看。喜欢就下载吧 ……