深度优先搜索练习题
一、填数字三角形问题
提交文件：numlist.exe /(numlist.pas 或numlist.bas)
问题描述：
将1—15这15个自然数，不重复不遗漏地填入如下给出的15个方框中，使除最上面一层外，每个框中的数字等于上面两个方框中数之差的绝对值，试编一程序找出所有填数的方案。按如下位置格式输出数字三角形。注：全部用输出语句输出结果的不得分。
□ □ □ □ □
□ □ □ □
□ □ □
□ □
□
数据输入输出说明：
本题没有数据输入，结果按如上格式输出到屏幕。
二、王伯买鱼（ FiSh）
提交文件：Fish．exe
输入文件： Fish．dat
输出文件：Fish. out
王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑调，大的、小的，什么都有。这些鱼实在是太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼。哪里有美丽的湖？于是动物公园不得不规定，对于每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。
王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编写一个程序帮助他。如果有多个方案都能买尽可能多的鱼，选择所花资金最多的一个。
输入:
从输入文件读人数据。输入文件的第一行为两个正整数M（M<=100），N（N＜=30），分别表示王伯的资金和鱼的种类。以下 N行，每行有两个正整数S（ l=＜S＜=N），T，分别表示某种鱼的编号以及该鱼的价格。
接着，每行有两个整数P，Q。当P，Q均大于0时，表示P，Q不能共处；当P，Q均等于0时，表示输入文件的结束。
输出
输出文件的第一行为两个正整数X，Y，分别表示所买鱼的条数和总花费。以下X行，每行有一个正整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中的一个。
输入举例
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0
输出举例
4 160
2
4
5
6
三、数学家旅游
文件名：GOLYGON.pas
有一个 城市的道路由规则的方砖组成。有一位数学家来到参观，他可沿方砖的边沿行走，有四种方法：n(0,1), s(0,-1), e(1,0), w(-1,0)，但他是一个很怪的数学家，他会走一段时间休息一会儿，然后继续走。他有几个很特别的特性：
不喜欢休息后走的方向和休息前一样；
第一次休息前走一步，休息后走的距离比休息前的距离长一步；
不喜欢重复走同一个地方；
要走回出发点。
我们称他的路线是一个goline，我们可以将出发的地点记为（0，0），城市有几个地点正在施工，是不可以通行的。为了这位奇怪的科学家可以旅游得开心，我们决定帮他设计旅游的方案，找出城市中有多少个他希望的goline。
输入：第一行是goline最大边的大小（不大于20），第二行是施工地点的个数（不大小50），以下的每行有两个数字，表示施工的地点的坐标。
输出：每一个goline的走法，每个占一行，最后输出goline的个数。
例如：输入：GOLYGON.dat
8
2
-2 0
6 -2
输出： GOLYGON.out
wsenenws
TOTAL=1
四、单词背诵
问题描述：
小小在背单词，她发现当背诵了单词beauty 以后 ，再接着背诵单词beautiful 就会觉得容易许多。由于有很多单词要背，她希望找到一种好的背诵顺序。单词A和它的前驱B的最大公共前缀的长度称为背诵单词A的便利值(例如：B=’beauty’,A=’beautiful’,则A的便利值是len({A,B})=len(’beaut’)=5),我们认为一个背诵单词A的花费是它的长度(例如:’beautiful’的长度len(‘beautiful’)=9)与它的便利值之差（对于上述例子背诵A的花费为9-5=4）。请你求一个背诵顺序，使得背诵这些单词的花费总和最小。假设一开始你什么单词都不记得。
输入格式：
给定一个单词表：第一行N（N < 100）表示单词总数。接下来N行，每行一个单词。每个单词的长度不超过20，均为小写字母组成。
输出格式：
按照背诵顺序输出每个单词，每个单词占一行，不能有多余的字符。
样例：
五、分离单词
提交文件名：DIVWOED. EXE
问题描述：
一个长度为L的双重线形的纵横字串是指由L个小写英文字母排列而成的字串。它至少有两种划分的方法（称为分离法）分解成一组单词的排列，这些单词应该与从给定的单词表中选出来的相同。看下面的例子（L=17）：
| | | |
a n d a t a r e a l l a s t a s k
| | | | |
这些单词是从以下列表选出的：all，an，and, are，area, as，ask，at, data, last, or, read, real， task。
出现在第一种分离法的单词不能在第二种分离法中出现，反之亦然。并且，任何一个单词在任何一个分离法中不能重复出现。一个单词在一种分离法中结束的位置不能和某一个单词在另一种分离法中结束的位置相同（字串结尾的单词除外）。其中一种分离法可以只包含一个单词。
请你编写一个程序构造一个满足以上规则的长度为L的双重线形纵横字串，其组成的单词从一个给定的单词列表中选出。单词列表中的单词已按字典顺序排列好。
输入格式：
从当前目录下的文本文件“ DIVWORD.DAT”中读人数据。
文件中第一行是一个整数L（4=
输出格式：
结果输出到当前目录下的文本文件“ DIVWORD．OUT”中。对于输入的数据集，你的程序须输出任意一个给定长度的双重线形纵横字串。若这种字串不存在，程序须输出一行信息“NOSOLUTION”。
输入输出举例:
输入文件: DIVWORD.DAT 输出文件:DIVWORD.OUT
17 andatareallastask
14
all
an
and
are
area
as
ask
at
data
last
or
read
real
task
六、虫食算(alpha.pas/dpr/c/cpp)【问题描述】 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 43#9865#045 + 8468#6633 44445506978 其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。 现在，我们对问题做两个限制： 首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。 其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。 BADC + CRDA DCCC 上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，【输入文件】 输入文件alpha.in包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。【输出文件】 输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。【样例输入】5ABCEDBDACEEBBAA【样例输出】1 0 3 4 2【数据规模】对于30％的数据，保证有N<＝10；对于50％的数据，保证有N<＝15；对于全部的数据，保证有N<＝26。
本文来源：https://www.2haoxitong.net/k/doc/8219b513a4e9856a561252d380eb6294dd88220a.html
文档为doc格式