信息技术选修1 数据与数据结构4.3.1 树备课ppt课件

这是一份信息技术选修1 数据与数据结构4.3.1 树备课ppt课件，共13页。PPT课件主要包含了重排九宫问题，状态树生成过程，迷宫问题，为什么要画状态树，四皇后问题等内容，欢迎下载使用。
4.1 重排九宫问题及其树表示
有一个3*3的方格棋盘，上面有8个棋子和一个空格，移动与空格相邻的棋子可以生成新的棋盘状态。
Q1：若每步只移动一个棋子，共有几种移法？
注意：同一种棋盘状态不能重复出现
【状态树生成过程】
【状态树的表示方法】
（1）这棵树共有几层？根节点是哪个？
（2）什么是分支？节点B2有几个分支？
（3）请举例说明分支节点、父节点、子节点和叶节点。
下图是一个迷宫，S0是入口，Sg是出口，把入口作为初始节点，出口作为目标节点，通道作为分支，画出从入口S0出发，寻找出口Sg的迷宫问题的状态树。
如果我们想让计算机帮助我们解决生活中遇到的问题，就必须把待解决的问题表示成某种固定的形式。
一个4*4国际象棋盘，依次放入四个皇后。每行、每列及对角线上只允许出现一枚棋子。每次只能将一个棋子放在当前行的下一行。请依据下列规则画出状态树，找到所有合法布局。规则：i表示棋子所在行，j表示棋子所在列（1≤i,j≤4）如（12）表示第一行第二列有一枚棋子。