集训全6套练习题-3月16日练习题
需积分: 4 27 浏览量
2022-11-23
09:27:15
上传
评论
收藏 30KB DOCX 举报
1. Eight (POJ1077) 15 数码问题已经存在 100 多年了，在一个 4*4 的阵列中，填入了 1-15
这 15 个数字，每个方格只填入一个数字，这样便有一个方格没有填入数字。问题的目
标是通过合理的操作，使得 4*4 阵列中的数字变成下面的顺序。
其中，x 表示没有数字的方格。而允许的操作是每次只能将方格 x 上方、右方、下方、
或左方相邻方格内的数字移入方格 x 内。当然，并不是所有 15 数码问题都是可解的，
在 1870 年，Sam Loyd 因设计了一个无解的 15 数码问题而出名，这个问题也难倒了很多
人。这里，你的任务是编程求解 8 数码问题，和 15 数码问题类似，8 数码问题的目标是
通过合理操作使得 3*3 阵列中的数字 1-8 变成如下顺序。
对于不可解问题，你要输出 unsolvable；对于可解问题，你要输出求解问题的操作序列，
用 u、r、d 和 l 分别表示将方格 x 上方、右方、下方、左方相邻方格内的数字移入方格 x
内。例如，如下 8 数码问题的一个解为“ullddrurdllurdruldr”
2. Tiling(POJ2506) 使用 2*1 的矩形和 2*2 的矩形铺砌 2*n 的矩形（下图给出了一个 n=17
的一种铺法。），有多少种方法？
例如，n=100 时，方法种数为 845100400152152934331135470251
3. Colored Stones(POJ2978) 将 m 块小石头排成一排，每块小石头的颜色为 k 种颜色中的一
种。你的任务是，拿走最少块数的小石头，使得剩下的小石头中，所有颜色相同的小石
头都处于相邻的位置。例如，小石头颜色序列为“2 1 2 2 1 1 3 1 3 3”时，所求结果为
2。
4. 某工程公司承担建设从 A 城市连接 B、C、D、E 四个城市公路的工程。各城市间公路建
设费用如下表所示。
序号
起点
终点
费用（亿元人民币）
1
A 城市
B 城市
2
2
A 城市
C 城市
5
3
A 城市
E 城市
3
4
B 城市
D 城市
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
1 2 3
4 5 6
7 8 x
2 3 4
1 5 x
7 6 8
资源评论
