深度优先搜索算法.ppt

深度优先搜索算法 深度优先搜索法有两大基本特点 1 对已产生的结点按深度排序 深度大的先得到扩展 即先产生它的子结点 2 深度大的结点是后产生的 但先得到扩展 即 后产生先扩展 因此用堆栈作为该算法的主要数据结构 存储产生的结点 先把产生的数入栈 产生站顶 即深度最大的元素 子结点 子结点产生以后 出栈 再产生栈顶子结点 一 递归算法 递归过程为 procedureTRY i Forr 1tomaxrdo maxr是产生式规则数 beginIf子结点MR符合条件THENbegin产生的子结点MR压入栈 IF子结点MR是目标结点THEN输出ELSETRY I 1 栈顶元素出栈 删去MR end end main programDFS 初始栈 TRY 1 N 子结点mr是目标结点 N Y Try I 二 非递归算法programDFS dep dep 0 repeatdep dep 1 j 0 p false repeatj j 1 if子结点mr符合条件then产生子结点mr并将其记录if子结点是目标then输出并出栈 更新j elsep true elseifj maxjthen回溯elsep false untilp true untildep 0 其中回溯过程如下 procedurebacktracking dep dep 1 ifdep 0then取回栈顶元素elsep true Y N Mr符合条件 子节点是目标 Y N Y N J maxj 如图 A点有一个过河卒 需要走到目标B点 卒行走的规则 可以向下 或者向右 同时在棋盘上的任一点有一个对方的马 如图的C点 该马所在的点和所有串跳跃一步可达的点称为对方马的控制点 例如图中C点上的马可以控制9个点 图中的P1 P2 P8和C 卒不能通过对方马的控制点 棋盘用坐标表示 A点 0 0 B点 n m n m为不超过20的整数 并由键盘输入 同样马的位置坐标是需要给出的 约定 CA 同时CB 现在要求你计算出卒从A点能够到达B点的路径的条数 现有n个数字 n 200 要求把这n个数字划分成K K能整除N 设M N K 个集合S1 S2 S3 Sk 每个集合均有M个数字 集合Si中的数字按某种次序串接 构成一个正整数Li i 1 2 3 k 问怎样划分和排列集合S1 S2 S3 Sk 使得L1 L2 L3 Lk 1 2 3 k INPUT TXT1234567893OUTPUT TXT192384576219438657273546819327654981 用数组B 0 9 来存储N个数字存储规则 B 0 存储N个数字中0的个数B 1 存储N个数字中1的个数B 2 存储N个数字中2的个数 B 8 存储N个数字中8的个数B 9 存储N个数字中9的个数 Input txt B I n个数据K值 have true Made 1 Y N have 输出无解信息 Made s 取第1组的第S个数前提 前S 1个数是合法的S M h g E i bb h 0 Y N exit 输出结果到OUTPUTHave false Pass检验第2组 第K组数是否合格 如合格则输出其中bb是b的拷贝 将Z 1 Z m 中数字计算出值赋给E i 2tok j Mdownto1 gmod10 g gdiv10 bb h bb h 1 Ifg 0thenexit 骑士游历问题 在6 6的国际象棋上的某一位置上放置一 马 然后采用象棋中 马走日字 的规则 要求该 马 能不重复地走完36个格子 试编写程序解决这个问题 数组A 设置8个方向变化 Board 1 1 1 try 1 1 2 q Y N q 输出无解信息 初始化board 输出结果 Try x y i q 表示对 x y 位置作为第i步向前试探的过程 若试探成功 逻辑变量q的值为true 否则为false K k k 1q1 false Not q1 0 Q1OR K 8 u x a 1 k v y a 2 k Y N Board u v i 合格 i n n Try u v i 1 q1 Y N Board u v 0 Q1 true Board 0 Y N Y N Q Q1 试编程将1至N N 10 的自然数序列1 2 N重新排列 使任意相邻两数之和为素数 例如N 3时有两种排列方案123 321满足要求 输入要求 N从键盘输入 输出要求 每行输出一种排列方案 相邻数字之间用空格分隔 最后一行输出排列方案总数 例如输入3输出1233212 数据初始化 have true Made 1 Y N have 输出无解信息 i 1ton Pass1 I t andYN a t 1 b t a t i Y N t n Y N Made t 1 Pass2 t Made t 填写第t个数前提 前t 1个数是合法的t n b t i 填数字有如图所示的九个小方格 在每个方格中填入0 9中的一个数字 每个数字只能用一次 并使每行的数字组成的自然数都是完全平方数 如图的填法就是一种合法的情况 试编程找出所有正确的填法 输出要求 每行输出四个自然数 分别为一位数 二位数 三位数 四位数 表示一种填法 两数之间用空格分隔 例如上图情况输出 1367849025 ForI 1to3求I i 分离各位数字Forj 4to9求j j 分离各位数字Fork 11to31求k k 分离各位数字Forp 32to99求p p 分离各位数字 键盘输入一个仅由小写字母组成的字符串 输出以该串中任取M个字母的所有排列及排列总数 搜索Search 初始化Init 输出总数tot 搜索指针LEV 0 输入STR M ANS 首数列 NUM 频率 总数TOT 0 C a to z LEV M N search Y INC TOT INC LEV 输出A